t\rho_{ij}\sigma_{i}\sigma_{j}$ (where by definition $|\rho_{ij}|\leq 1$).
Typically, annualized volatilities are smaller than $100\%$ (i.e.
$\sigma_{i}<1$) and the timestep usually satisfies $\Delta t<1$, meaning the
price of the underlying assets needs to be sampled more frequently than just
yearly. If neither condition is satisfied however, we can choose a smaller
$\Delta t$ to ensure $|\Sigma_{ij}|<1$, at the cost of increasing the number
of timesteps in the calculation.

The contributions to the T-depth and qubit count for loading the paths and
computing the asset prices in the re-parameterization approach for a
derivative defined on $d$ assets $T$ timesteps are

  * •

$T_{R_{y}}(n)\cdot(L+1)$ T-depth for loading the gaussian states in Eq. (37)
using the variational method from Sec. 4.2.1, where each Gaussian is prepared
in parallel and the variational ansatz has depth $L$. This step requires
$T*d*n$ qubits where $n$ qubits are used to prepare each Gaussian state.

  * •

$\text{T}_{\text{add}}*(T-1)$ for calculating all the component-wise sums
$\left(\vec{\bar{R}}(t=1)+\vec{\bar{R}}(t=2)+\cdots+\vec{\bar{R}}(t=t^{\prime})\right)$
for $t^{\prime}\in[2,T]$ in Eq. (99), requiring an extra
$T*d*(n+\lceil\log_{2}T\rceil)$ qubits (see Fig. 5).

  * •

$\text{T}_{\text{mul}}*d$ to compute all contributions to
$\sum_{i=0}^{d-1}L^{\intercal}_{ji}\bar{R}_{i}^{t^{\prime}}$ in Eq. (99) and
$T*d*\lceil\log_{2}d\rceil$ more qubits.

  * •

$\text{T}_{\text{add}}$ to compute the $\mu_{j}t^{\prime}+\ln S_{j}^{t=0}$
contribution in Eq. (99) across assets and timesteps.

  * •

$\text{T}_{\text{exp}}$ to compute the exponential in Eq. (99) across assets
and timesteps, and $q_{\text{exp}}*d*T$ additional qubits with
$q_{\text{exp}}$ given by Eq. (71).

All in all, the total T-depth for path loading using the re-parameterization
method to precision $\epsilon$ for $d$ assets and $T$ timesteps is

$T_{RP}(n,d,T,L,\epsilon)=3n\log_{2}(n/\epsilon)(L+1)+10T+d\bar{n}^{2}+T_{\text{exp}}(\bar{n},\epsilon),$
(100)

with qubit count

$q_{RP}(n,d,T)=\left(n+\bar{n}+q_{\text{exp}}(\bar{n},\epsilon)\right)dT,$
(101)

where $\bar{n}=n+\lceil\log_{2}T\rceil+\lceil\log_{2}d\rceil$.

Figure 5: Circuit that computes $T$ registers containing the cumulative log-
returns $\bar{R}_{i}^{t^{\prime}}$ from Eq. (99) for one asset at each
timestep $t^{\prime}\in[1,T]$. We first apply $T$ $\mathcal{G}$ operators (see
Sec. 4.2.1) to generate states corresponding to standard Gaussian probability
distributions for each timestep, and then serially apply ADD operators which
perform $\ket{x}\ket{y}\ket{0}\rightarrow\ket{x}\ket{y}\ket{x+y}$. The ADD
operator is discussed in more detail in Appendix C. The circuit has
$\mathcal{G}$-depth of 1 and $T_{\text{add}}$-depth of $T-1$ and can be
applied in parallel for each asset in the derivative pricing calculation.
---
Figure 6: Circuits that compute asset prices $\ket{S_{i}^{t}}$ in separate
quantum registers for $d$ assets at timestep $t$ using Eq. (99). The top
figure shows the circuit which takes the cumulative log-returns for each asset
created by the circuit in Fig. 5 as input states and computes
$\ket{\sum_{i=0}^{d-1}L^{\intercal}_{ji}\bar{R}_{i}^{t}}$ for each asset
$j\in[0,d-1]$. There are $d$ layers of multiplications where each MUL operator
performs $\ket{x}\ket{y}\ket{z}\rightarrow\ket{x}\ket{y}\ket{z+xy}$. Note that
the MUL operators in each box can be performed in parallel and therefore the
entire circuit has depth of $T_{\text{mul}}*d$. Then, each computed register
$\ket{\sum_{i=0}^{d-1}L^{\intercal}_{ji}\bar{R}_{i}^{t}}$ requires one extra
addition and exponentiation to compute the asset price $\ket{S_{i}^{t}}$
(bottom figure), which can also be applied in parallel for each asset. Both
circuits can be applied in parallel across all timesteps $T$ of the
calculation. For more details on the ADD/MUL/EXP operators, see Appendix C.

##  Appendix F Method for Gaussian Loader Training

In this section we illustrate an approximate method to initialize the quantum
register using the Variational Quantum Eigensolver (VQE) approach [22]. This
algorithm features a parametrized circuit which in turn produces a
parametrized state $|\psi(\\{\theta\\})\rangle$ that approximately represents
the target state $|\phi_{0}\rangle$ and updates its parameters $\\{\theta\\}$
to optimize the expectation value of a suitable cost function. Here we show
that the choice of the cost function to optimize is crucial for the success of
the training.

Energy based training As a first method, we adopt a physics-based approach and
define an operator $H$, such that its expectation value $E$ assumes its lowest
possible value, $E_{0}$, when evaluated on the target state,

$E_{0}=\langle\psi_{0}|H|\psi_{0}\rangle.$ (102)

In physics applications, the operator $H$ is usually called the Hamiltonian,
$E$ the energy, and $|\phi_{0}\rangle$ the ground state. It is well known the
Gaussian function

$\phi_{0}(x)=\left(\frac{m}{\pi}\right)^{1/4}e^{-m(x-x_{0})^{2}}$ (103)

is the ground state of the quantum harmonic oscillator Hamiltonian

$H={P^{2}\over 2m}+{m~{}(X-x_{0})^{2}\over 2},$ (104)

where $X$ is the position operator in real space, and $P=-i{d\over dx}$ is the
momentum operator [41, 42]. $m$ is a parameter that determines the _variance_
of the desired Gaussian distribution, and $x_{0}$ is the center of gaussian
distribution. In this case, as we seek to find a state $\phi_{0}(x)$ such that
$\phi_{0}^{2}(x)=\mathcal{N}(x_{0},\sigma)$, we have to set
$m=1/(2\sigma^{2})$. We notice that it is always possible to find a generating
Hamiltonian function such that its ground state is the square root of the
smooth distribution function that we aim to load.

To translate these considerations into an operational workflow we just have to
define a way to compute the expectation value of Eq. (104) using a quantum
computer. To this end we observe that the operator $X^{2}$ is diagonal in the
computational basis, so it can be measured directly from the bit-string
histogram counts $N_{\text{counts}}(j)$ generated by the repeated wavefunction
collapses. The operator $P^{2}$ is diagonal in the momentum basis. This
implies the addition of a centered Quantum Fourier Transform (QFT) circuit
after the state preparation block. We use the centered Fourier transform to
allow for negative momenta [23]. As introduced in the main text, we work in
discrete position space $x_{i}=-w+i~{}\Delta x$, with $i=0,\cdots 2^{n}-1$,
and $\Delta x=2w/2^{n}$. Without loss of generality we choose the domain to be
centered at zero. The energy, $E=E_{X^{2}}+E_{P^{2}}$, can be computed in the
following way,

$\displaystyle
E_{X^{2}}=\frac{1}{N_{\text{shots}}}\sum_{j=0}^{\mathcal{N}}\frac{m}{2}N_{\text{counts}}(j)(j\times\Delta
x-x_{0})^{2}$ (105) $\displaystyle
E_{P^{2}}=\frac{1}{N_{\text{shots}}}\sum_{j=0}^{\mathcal{N}}\frac{1}{2m}N_{\text{counts}}(j)(j\times\Delta
p)^{2}$ (106)

where $N_{\text{shots}}$ is the total number circuit repetitions for the
spacial and momentum basis. $N_{\text{counts}}(j)$ (with $0\leq
N_{\text{counts}}(j)\leq N_{\text{shots}}$,
$\sum_{j}N_{\text{counts}}(j)=N_{\text{shots}}$) is the number of measurements
that collapsed onto the qubit basis state corresponding to the binary
representation of integer $j$. This strategy bypasses the need to obtain a
Pauli representation of Eq. (104), which would include an exponentially
increasing number of Pauli strings to be measured with the qubit register
size.

The first step of our program is to verify numerically the possibility to
prepare a state that systematically converges to Eq. (103), using a quantum
circuit. Adopting a variational approach will circumvent the need of costly
quantum arithmetic operations at the expense of introducing sources of error
which are always present in numerical variational approaches. The most trivial
one concerns the possibility of getting trapped in local minima during the
(classical) optimization procedure. The second, and more profound one, is
linked with the representational power of trial states produced by the
(shallow) quantum circuits.

Our main choice for the ansatz is the so-called $R_{y}$-CNOT circuit [43]. The
initial state, defined on an $n$-qubit register which we set to
$\ket{0}^{\otimes n}$, is evolved under the action of a unitary
$U(\vec{\theta})$ to give the trial wave function $\ket{\psi(\vec{\theta})}$.

The circuit is made of a series of $L$ blocks built from single-qubit
rotations $U_{R}(\vec{\theta}^{k})$, followed by an entangler
$U_{\text{ENT}}$, that spans the required length of the qubit register. In our
tests, we used the simplest choice of a ladder of CNOT gates with linear
connectivity, such that qubit $q_{i}$ is target of qubit $q_{i-1}$ and
controls qubit $q_{i+1}$, with $i=1,\cdots,n-2$. One additional layer of
$U_{R}$ gates is applied at the end, such that the number of variational
parameters is $n\times(L+1)$.

Since the single-qubit rotations are all local operations,
$U_{R}(\vec{\theta}^{k})$ can be written as a tensor product of rotations of a
single qubit:

$U_{R}(\vec{\theta}^{k})=\bigotimes_{i=0}^{n-1}R_{Y}({\vartheta}_{q_{i}}^{k}),$
(107)

where $R_{y}({\vartheta}^{k}_{q_{i}})$ is a rotation on the Y-axis on the
Bloch sphere of qubit $q_{i}$, and $k=1,\cdots,L+1$. The full unitary circuit
operation is described by

$U(\vec{\theta})=U_{R}(\vec{\theta}^{L+1})~{}\overbrace{U_{\rm
ENT}U_{R}(\vec{\theta}^{L})\ldots U_{\rm
ENT}U_{R}(\vec{\theta}^{1})}^{\rm{L-times}},$ (108)

and the parametrized state is

$\ket{\psi(\vec{\theta})}=U(\vec{\theta})\ket{0}^{\otimes n}.$ (109)

Note that the unitary $U(\vec{\theta})$ describes the full circuit, but not
the pre-measurement change of basis required to collapse the wavefunction in
momentum space as explained above.

For each value of parameters $n$ and $L$, we repeat the optimization runs
eight times in order to gather sufficient statistics, as it may happen that
the optimizations remain stuck in suboptimal minima. Since we use classical
emulation of the quantum circuits the only source of error in the
optimizations originates from the classical optimizer. In our runs we first
perform a warm up run with the COBYLA optimizer, followed by a longer run
using the BFGS optimizer. To enhance the efficiency of the optimizations, the
starting point for the VQE run at depth $L$, uses the optimal parameters found
at previous optimization at depth of $L-2$ or $L-1$ when available. We notice
that the part of the algorithm that concerns the classical optimization
feedback can be greatly improved, for example using gradient based methods
[44] or imaginary-time inspired update schemes [45].

$L_{\infty}$ training refinements As discussed in the main text we use pre-
optimized circuits obtained using the energy optimization method as a starting
guess, and then re-optimize using the $L_{\infty}$ as the cost function. In
Fig. 7 we show indeed how the direct $L_{\infty}$ optimization consistently
fails to provide accurate results.

Figure 7: Optimization runs obtained with the energy-based method (green), the
direct $L_{\infty}$ optimization (red) and the mixed strategy where the energy
based optimization is further refined using the $L_{\infty}$ optimization
(blue). We run eight independent runs for different values of the parameters
$n$ (number of qubits) and $L$ (ansatz depth).

We show the complete outcome of the optimizations in Fig. 8. This careful
numerical study shows that the convergence to the exact ground state is
exponential in the depth, and therefore the number of gate operations.

Figure 8: Left figure: $L_{\infty}$ norm difference between the prepared and
the target distribution as a function of the circuit depth $L$ for different
qubit register sizes $n$. We plot here the best of the eight independent
optimizations for each parameter. Empty symbols correspond to optimizations
performed using the energy of the quantum harmonic oscillator as a cost
function, while solid symbols denote the refined optimizations using the
$L_{\infty}$ as cost function. Right figure: we plot the difference in energy
of the associated quantum harmonic oscillator model. As expected the
refinement targeting the $L_{\infty}$ does not improve this quantity.

Failure of the $L_{\infty}$ norm direct optimization We provide an empirical
explanation concerning the observed failure of the direct norm optimization
technique. To this end we probe the cost function landscape for both methods,
the energy-based and the direct $L_{\infty}$ optimization, We start from an
optimized parameter configuration $\vec{\theta}_{0}$ and we perform a _cut_ in
the parameter space, using

$\vec{\theta}=\vec{\theta}_{0}+\lambda\vec{\eta}$ (110)

where $\vec{\eta}$ is an vector containing uniformly distributed random
numbers in the range $[-1,1]$, and $\lambda\in[-\pi,\pi]$ is a scalar which
parametrizes the deviation from the optimal solution.

Figure 9: Cost function landscapes for the energy $E$ (above), and the
$L_{\infty}$ norm (below) computed using three different cuts (red, blue and
green colors) along the parameter space, and for two different setup $n=5,7$
and depths $L=6,10$ respectively.

In Fig. 9 we probe the cost function landscape for three different cut
direction (e.g. three different realizations of the vector $\vec{\eta}$). We
observe indeed that the cost function defined by the $L_{\infty}$ norm is much
more corrugated than the one defined by the energy $E$ of the associate
quantum mechanical toy problem, which instead displays a smoother surface.
Crucially the basins of attraction of the energy cost-function and the
$L_{\infty}$ cost-function are overlapping (this happens because the ground
state of the physical problem is very close to the Gaussian function we want
to achieve), therefore the second optimization with the $L_{\infty}$ norm does
not remain stuck in high-cost local minima outside such basin.

Variational parameters digitization. While our numerical results provide
evidence for a rather efficient Gaussian state preparation in terms of circuit
depths for a parametrized circuit, an additional step has to be made in view
of a fault-tolerant implementation of such circuits. In this new-framework,
the continuous rotation $R_{y}$ gate needs to be expanded as a finite product
of discrete operations. Following again the Solovay-Kitaev theorem, or more
specialized results [25], it is possible to also have an efficient
representation of any $SU(2)$ operator with a sequence of Clifford + T gates
that scale logarithmically with the threshold error $\epsilon$. We investigate
how the results obtained before can be transferred in this regime where
rotation angles can only take discretized values. We therefore assume that
each parameter ${\vartheta}^{k}_{q_{i}}$ can only be represented in the format
$i*2\pi/M_{digit}$, where $i$ is an integer.

We adopt a simple protocol to optimize the parameters on an a grid. First we
project the original continuous parameter values on the grid, choosing the
closest grid point for each parameter. Subsequently, we perform a local search
on the grid to find a better combination of the digitized parameters which
minimize the $L_{\infty}$ norm difference compared to the target distribution.
We numerically show that the error introduced by such digitization decreases
systematically with the mesh size. Interestingly, if we consider the error in
the $L_{\infty}$ norm difference introduced by this digitization, it decreases
as $O(1/M_{digit})$. We observe that in all cases, we are able to obtain
values comparable, or better, with the continuous solution, when the mesh size
reaches $M_{digit}\sim 10^{5}$, which is equivalent to discretizing the space
using $2\pi/M_{digit}\approx 0.0001$ rad.

Figure 10: $L_{\infty}$ norm difference between the prepared and the target
distribution as a function of the digitization mesh size $M_{digit}$ for two
different circuit depths $L$ (blue and red), for the $n=4$ qubit case. For
each $M_{digit}$ we _digitize_ the eight parameter sets obtained by the
previous independent optimizations (which were performed considering a
continuous domain for the values of the rotation angles). Empty symbols refer
to the full dataset, while the solid symbols highlight only minimum values in
the set. Colored horizontal lines denote the best values obtained in the
previous optimizations with a continuous domain of rotation angles for each
$L$ parameter. Interestingly, in some cases the digitization helps in escaping
local minima and achieve slightly better solutions. Black diagonal lines are a
guide-to-the-eye and represent the functions $1/M_{digit}$ and
$0.1/M_{digit}$. Figure 11: Same as Fig. 10 but with $n=5$ Figure 12: Same as
Fig. 10 but with $n=6$


Decomposable forms generated by linear recurrences

K. Győry111University of Debrecen (Hungary), A. Pethő222University of Debrecen
(Hungary), L. Szalay333University of Sopron (Hungary), and J. Selye University
(Slovakia)

###### Abstract

Consider $k\geq 2$ distinct, linearly independent, homogeneous linear
recurrences of order $k$ satisfying the same recurrence relation. We prove
that the recurrences are related to a decomposable form of degree $k$, and
there is a very broad general identity with a suitable exponential expression
depending on the recurrences. This identity is a common and wide
generalization of several known identities. Further, if the recurrences are
integer sequences, then the diophantine equation associated to the
decomposable form and the exponential term has infinitely many integer
solutions generated by the terms of the recurrences. We describe a method for
the complete factorization of the decomposable form. Both the form and its
decomposition are explicitly given if $k=2$, and we present a typical example
for $k=3$. The basic tool we use is the matrix method.

2010 Mathematics Subject Classification: 11B37, 11D61, 11D72.

Keywords: linear recurrence, decomposable form, general identity, diophantine
equation, matrix method.

##  1 Introduction

Let $k\geq 2$ be an integer. A sequence $(G_{n})$ of complex numbers is called
linear recurrence of order $k$ if there exist
$\gamma_{0},\dots,\gamma_{k-1}\in\mathbb{C}$ such that

$G_{n+k}=\gamma_{k-1}G_{n+k-1}+\dots+\gamma_{0}G_{n}$ (1)

holds for all $n\geq 0$, moreover $k$ is minimal with this property. The
polynomial

$P(X)=X^{k}-\gamma_{k-1}X^{k-1}-\dots-\gamma_{0}$ (2)

is the characteristic polynomial of $(G_{n})$. Note that the definition of the
order yields $\gamma_{0}\not=0$. We will return to this question later, in
Section 2.

Dividing (1) by $\gamma_{0}\not=0$ and rearranging the equality we obtain

$G_{n}=-\frac{\gamma_{1}}{\gamma_{0}}G_{n+1}-\dots-\frac{\gamma_{k-1}}{\gamma_{0}}G_{n+k-1}+\frac{1}{\gamma_{0}}G_{n+k}.$

Now performing the substitution $n\mapsto-n-k$ it gives

$G_{-(n+k)}=-\frac{\gamma_{1}}{\gamma_{0}}G_{-(n+k-1)}-\dots-\frac{\gamma_{k-1}}{\gamma_{0}}G_{-(n+1)}+\frac{1}{\gamma_{0}}G_{-n},$

which is a linear recursion for the negative branch of $(G_{n})$. The results
of the present paper hold for this two side infinite sequence what we can
consider also as a number theoretic function
$G_{n}\,:\,\mathbb{Z}\mapsto\mathbb{C}$.

There exist a huge number of relations involving linear recurrences in the
corresponding literature, in particular for $k=2$. Identities with Fibonacci
$(F_{n})$, or Lucas $(L_{n})$ numbers play distinguished role among them. The
Fibonacci Quarterly is devoted mainly for such works. Sequences
$(F_{n}),(L_{n})$ have the initial terms $F_{0}=0,L_{0}=2,F_{1}=L_{1}=1$, and
both satisfy the recursion

$x_{n}=Ax_{n-1}+Bx_{n-2}$ (3)

with $A=B=1$. From this rich variety of identities we quote three ones, namely

$\displaystyle L_{n}^{2}-5F_{n}^{2}$ $\displaystyle=$
$\displaystyle(L_{n}-\sqrt{5}F_{n})(L_{n}+\sqrt{5}F_{n})=4(-1)^{n},$ (4)
$\displaystyle F_{n+1}^{2}-F_{n}F_{n+1}-F_{n}^{2}$ $\displaystyle=$
$\displaystyle\left(F_{n+1}-\frac{1+\sqrt{5}}{2}F_{n}\right)\left(F_{n+1}-\frac{1-\sqrt{5}}{2}F_{n}\right)=(-1)^{n},$
(5) $\displaystyle F_{n-1}F_{n+1}-F_{n}^{2}$ $\displaystyle=$
$\displaystyle(-1)^{n}.$ (6)

All three belong to the folklore and can be easily generalized to any second
order recurrences. Indeed, assume that $(G_{n})$, and $(\widehat{G}_{n})$
satisfy the recursion (3). If their initial terms are
$G_{0},G_{1},\widehat{G}_{0}=2G_{1}-AG_{0},\widehat{G}_{1}=AG_{1}+2BG_{0}$,
then we say that $(\widehat{G}_{n})$ is associated to $(G_{n})$. Here
$A,B,G_{0},G_{1}$ denote complex numbers with the conditions $B\not=0$ and
$|G_{0}|+|G_{1}|\not=0$. Assume that $\alpha$ and $\beta$ are the not
necessarily different roots of the characteristic polynomial
$P(X)=X^{2}-AX-B$. Put $D=A^{2}+4B$, which is the discriminant of $P$, and let
$C_{G}=G_{1}^{2}-AG_{0}G_{1}-BG_{0}^{2}$. Then the identities

$\displaystyle\widehat{G}_{n}^{2}-DG_{n}^{2}$ $\displaystyle=$
$\displaystyle(\widehat{G}_{n}-\sqrt{D}G_{n})(\widehat{G}_{n}+\sqrt{D}G_{n})=4C_{G}(-B)^{n},$
(7) $\displaystyle G_{n+1}^{2}-AG_{n}G_{n+1}-BG_{n}^{2}$ $\displaystyle=$
$\displaystyle\left(G_{n+1}-\alpha G_{n}\right)\left(G_{n+1}-\beta
G_{n}\right)=C_{G}(-B)^{n},$ (8) $\displaystyle G_{n-1}G_{n+1}-G_{n}^{2}$
$\displaystyle=$ $\displaystyle-C_{G}(-B)^{n-1}$ (9)

hold, and it is a simple exercise to see that they are direct generalizations
of (4)-(6), respectively. Note that the second one is equivalent to the third
one by $(G_{n+1}-AG_{n})G_{n+1}-BG_{n}^{2}=BG_{n-1}G_{n+1}-BG_{n}^{2}$, and
this phenomenon is obviously true for (5) and (6), too.

Assuming $|B|=1$ and using (7), Pethő [10] characterized the polynomials whose
values appear infinitely many times in $(G_{n})$. One can reverse identity (5)
such that the only positive integer solutions to the equation

$x^{2}-xy-y^{2}=\pm 1$

are $(F_{n},F_{n+1})$. J. P. Jones [5] gave a good overview on this equation
and its relation to the solution of Hilbert’s tenth problem.

For recurrences of higher order there are only a few and complicated
identities available. Especially, we do not know any generalization of (7).
Recently, Craveiro et al. [2] explored a nice generalization of the so-called
Cassini identity (6) for recurrences of arbitrary order $k$. They investigated
also analytical and combinatorial properties of their result. Corollary 1 of
Theorem 1 of this paper provides a new contribution to this question, in fact
we consider the problem with any set of initial values apart from singular
cases. Corollary 1 via Theorem 1 makes it possible to determine a Cassini-like
identity if the basic recurrence of order $k$ is given. However such an
identity is expected to be rather compound.

The main result of this article is a common and wide extension of (7), (8),
and other identities to $k\geq 2$ linear recurrences of order $k$ satisfying
the same recursive rule, including their connection with decomposable forms
and diophantine equations.

##  2 New results

We shall prove some general results. Note that the basic field we work in is
the set $\mathbb{C}$ of complex numbers, but the machinery works even for any
fields.

######  Theorem 1.

Let $(G_{n}^{(j)}),j=1,\dots,k$ be linear recursive sequences of complex
numbers of order $k$ with the same characteristic polynomial (2) having
constant term $-\gamma_{0}\not=0$. If the sequences are $\mathbb{C}$-linearly
independent, then there exists a homogeneous polynomial
$F\in\mathbb{C}[X_{1},X_{2},\dots,X_{k}]$ of degree $k$ such that

$F(G_{n}^{(1)},G_{n}^{(2)},\dots,G_{n}^{(k)})=((-1)^{k+1}\gamma_{0})^{n}$

holds for all $n\in\mathbb{Z}$.

A homogeneous polynomial $Q\in\mathbb{C}[X_{1},X_{2},\dots,X_{k}]$ is called
decomposable if it splits completely into linear factors. Hence a decomposable
form is necessarily homogeneous, but for $k\geq 3$ the converse is not true in
general. The next theorem is a remarkable completion of Theorem 1.

######  Theorem 2.

Under the assumptions of Theorem 1 the homogeneous polynomial $F$ is
decomposable.

Clearly, Theorem 2 is a continuation of Theorem 1, and we could have presented
them together. However their proofs differ significantly, which explains their
separation.

We emphasize that the proofs are constructive, and following their arguments
one can compute the polynomial ${F}$ and its decomposition into linear
factors, too. Unfortunately, $F$ has no nice general form if $k\geq 3$, so we
will omit its explicit constitution. On the other hand, $F$ is given precisely
when $k=2$ (see Theorem 5 and the description after). Furthermore, we will
show some representative examples in Section 6.

A simple consequence of the main theorems is the following generalization of
(8).

######  Corollary 1.

Let $(G_{n})$ be a linear recursive sequence of complex numbers of order $k$
satisfying (1). If the vectors
$\bar{g}_{j}=(G_{j},G_{j+1},\dots,G_{j+k-1}),j=0,\dots,k-1$ are
$\mathbb{C}$-linearly independent, then there exists a decomposable form
$F\in\mathbb{C}[X_{1},X_{2},\dots,X_{k}]$ of degree $k$ such that

$F(G_{n},G_{n+1},\dots,G_{n+k-1})=((-1)^{k+1}\gamma_{0})^{n}$

holds for all $n\in\mathbb{Z}$.

The linear recursive sequences with initial values
$G_{0}=\dots=G_{k-2}=0,G_{k-1}=1$ satisfy always the assumption of this
corollary, hence the statement too. The $k$-generalized Fibonacci sequences
$(F_{n}^{(k)})$ (or, in other words, $k$-step Fibonacci numbers), which are
defined by the initial values
$F_{0}^{(k)}=\dots=F_{k-2}^{(k)}=0,F_{k-1}^{(k)}=1$ and by the recursion
$F_{n+k}^{(k)}=F_{n+k-1}^{(k)}+\dots+F_{n}^{(k)}$ are important examples. Here
the upper index $(k)$ in $F_{n}^{(k)}$ means traditionally the parameter $k$,
while in Theorem 1 the upper index $(j)$ denotes the $j$th from the $k$ given
sequences. Clearly, the case $k=2$ is the Fibonacci sequence.

In fact, sequence $(G_{n})$ is a complex valued number theoretical function.
Another direct consequence of Theorem 1 is as follows. The conditions of
Theorem 1 are valid here, too.

######  Corollary 2.

Let $(G_{n}^{(j)}),j=1,\dots,k$ be linear recursive sequences of complex
numbers of order $k$ with the same characteristic polynomial (2). Then they
and the sequence $(\gamma_{0}^{n})$ are algebraically dependent.

It is possible to extend $(G_{n})$ to a complex function $G(z)$ such that
$G_{n}=G(n)$ for all $n\in\mathbb{Z}$. Indeed, assume that $P(X)$ in (2) has
the factorization

$P(X)=(X-\alpha_{1})^{m_{1}}(X-\alpha_{2})^{m_{2}}\cdots(X-\alpha_{h})^{m_{h}},$

where $\alpha_{1},\dots,\alpha_{h}$ denote pairwise distinct complex numbers
and $m_{j}$, $j=1,\dots,h$ are positive integers. Then, see e.g. [12], there
exist polynomials $g_{j}\in\mathbb{C}[X]$ of degree at most $m_{j}-1$ such
that

$G_{n}=g_{1}(n)\alpha_{1}^{n}+g_{2}(n)\alpha_{2}^{n}+\dots+g_{h}(n)\alpha_{h}^{n}$

holds for all $n\in\mathbb{Z}$. Hence
$G(z)=g_{1}(z)\alpha_{1}^{z}+g_{2}(z)\alpha_{2}^{z}+\dots+g_{h}(z)\alpha_{h}^{z}$
is a complex function with $G(n)=G_{n}$ for all $n\in\mathbb{Z}$. For example,
the extensions of the Fibonacci and the Lucas sequences are the complex
functions

$F(z)=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{z}-\left(\frac{1-\sqrt{5}}{2}\right)^{z}\right),\quad
L(z)=\left(\frac{1+\sqrt{5}}{2}\right)^{z}+\left(\frac{1-\sqrt{5}}{2}\right)^{z},$

respectively. One can easily verify that identities (4)-(6) remain true if we
replace $n$, $F_{n}$, $L_{n}$, $(-1)^{n}$ by $z$, $F(z)$, $L(z)$, $(-1)^{z}$,
respectively. An interpretation of the generalized identities is the fact that
the corresponding complex functions are algebraically dependent.

It is well known, see e.g. [7], that a function $f(z)$ satisfies the linear
differential equation with characteristic polynomial $P(X)$ if and only if it
is identical with one of the above defined $G(z)$. Our next theorem is a
generalization of Corollary 2.

######  Theorem 3.

Let $P(X)\in\mathbb{C}[X]$ be a polynomial of degree $k$ with simple roots,
and assume $P(0)\not=0$. Let $k_{0}\geq k$ and denote $G_{j}(z)$, $1\leq j\leq
k_{0}$ pairwise different solutions of a homogeneous linear differential
equation with characteristic polynomial $P(X)$. Then $G_{j}(z)$, $1\leq j\leq
k_{0}$ and the function $((-1)^{k}P(0))^{z}$ are algebraically dependent.

As we noted Theorem 2 and its constructive proof have a remarkable consequence
in the theory of diophantine equations. This is presented as Theorem 4 in
Section 3, where it is more suitable to formulate the precise statement.
Indeed, if $(G_{n}^{(j)})$’s are integer sequences, then it makes possible to
have infinitely many integer solutions to the polynomial-exponential
diophantine equation

$\tilde{F}(x_{1},x_{2},\dots,x_{k})=pq^{n}$ (10)

in the integers $x_{1},x_{2},\dots,x_{k}$ and $n\geq 0$, where $\tilde{F}$ is
a decomposable form of degree $k$ depending on the parameters of the
sequences, further $p$, $q$ are suitable integers (see (24) below). If
$\tilde{F}$ is irreducible over $\mathbb{Q}[X_{1},\dots,X_{k}]$, then we may
assume that $\tilde{F}$ is, up to a constant factor, a full norm form. It
follows from a result of Borevich and Safarevich [1] that if the splitting
field of $\tilde{F}$ differs from $\mathbb{Q}$ and from the imaginary
quadratic number fields, then (10) has infinitely many solutions for $q=1$ and
for some integer $p$. More generally, by a celebrated theorem of W. M. Schmidt
[11] on norm form equations the set of solutions is a union of a finite set
and finitely many families of solutions. For a further generalization for
arbitrary decomposable form equations see Győry [4]. The families mentioned
are sums of product of powers of appropriate algebraic numbers. Fixing all but
one exponent and let run the remaining exponents through non-negative integers
we see that each family includes linear recursive sequences.

Our result shows that (10) may have infinitely many solutions in the case when
$\tilde{F}$ is reducible over $\mathbb{Q}[X_{1},\dots,X_{k}]$, too.

In our paper, we apply linear algebraic approach. We were also motivated to
contribute to the development of so-called matrix method often used in the
theory of linear recurrences. At the early 80’s H. W. Gould [3] presented a
survey on the $Q$-matrices, and he refers to R. Simson who first gave the
formula (6). This identity, together with its generalization (9) is an easy
consequence of our Theorem 5 in Section 6 with the notation $H_{n}=G_{n+1}$
(for $H_{n}$ see again Theorem 5). Theorem 5 is a common extension of
identities (7)-(9), and provides the background for the case of $k\geq 2$
linear recurrences of order $k$ in general appearing in Theorem 1.

We mention that recently Craviero et al. [2] have given a generalization of
Cassini identity for the $k$-generalized Fibonacci numbers with specific
initial vector set. The basic approach of [2] coincides with the idea of Lemma
2.1 of [9], and we exploit the advantages of this argument in the present
paper.

The paper is organized as follows. In Section 3, we give two proofs for
Theorem 1. In the next section, we prove Theorem 2, while Section 5 is devoted
to the proof of corollaries 1 and 2 and of Theorem 3. Section 6 specializes
the results of Theorem 1 and 2 to the cases $k=2$ and $k=3$. In Subsection
6.1, we present explicit formula in full generality if $k=2$, while in
Subsection 6.2, we compute the appropriate formula only for three given third
order recursive sequence. Other examples for larger $k$ values might be easily
presented by following the method of the proofs.

##  3 The homogeneous polynomials

Before starting the first proof of Theorem 1 we introduce some notation and
summarize well known facts.

Recall that $k\geq 2$ is an integer, furthermore
$\gamma_{0},\gamma_{1},\dots,\gamma_{k-1}$ denote arbitrary complex numbers.
Consider the set of recurrent sequences

$\Gamma_{k}^{(\gamma_{0},\gamma_{1},\dots,\gamma_{k-1})}=\left\\{(x_{n})_{n\in\mathbb{Z}}\in\mathbb{C}^{\infty}\mid
x_{n}=\gamma_{k-1}x_{n-1}+\gamma_{k-2}x_{n-2}+\cdots+\gamma_{0}x_{n-k}\right\\}.$
(11)

Clearly, sequences (11) satisfy a common recurrence rule, but they differ in
their initial values. They constitute a $\mathbb{C}$-vector space with respect
to the coordinate-wise addition and multiplication by scalar if and only if
$\gamma_{0}\not=0$, and in this case the dimension of the vector space is $k$.
To be able to apply linear algebraic tools we assume $\gamma_{0}\not=0$ in the
sequel. Throughout this paper we deal with vector spaces over the field of
complex numbers $\mathbb{C}$, therefore we do not mention always the ground
field.

###  3.1 First proof of Theorem 1

Assume that the recurrences

$(G_{n}^{(1)}),(G_{n}^{(2)}),\dots,(G_{n}^{(k)})\in\Gamma_{k}^{(\gamma_{0},\gamma_{1},\dots,\gamma_{k-1})}$
(12)

are $\mathbb{C}$-linearly independent. Then, equivalently, the vectors

$\bar{g}_{0}=\left[\begin{array}[]{c}G_{0}^{(1)}\\\ \vdots\\\ G_{0}^{(k)}\\\
\end{array}\right],\;\bar{g}_{1}=\left[\begin{array}[]{c}G_{1}^{(1)}\\\
\vdots\\\ G_{1}^{(k)}\\\
\end{array}\right],\dots,\;\bar{g}_{k-1}=\left[\begin{array}[]{c}G_{k-1}^{(1)}\\\
\vdots\\\ G_{k-1}^{(k)}\\\ \end{array}\right]$ (13)

are also linearly independent. Define the matrices
$\mathbf{G},\mathbf{G}^{\star}\in\mathbb{C}^{k\times k}$ as follows. The
column vectors of $\mathbf{G}$ are
$\bar{g}_{0},\bar{g}_{1},\dots,\bar{g}_{k-1}$, respectively, while
$\bar{g}_{1},\bar{g}_{2},\dots,\bar{g}_{k}$ admit the column vectors of
$\mathbf{G}^{\star}$ in this order. The $k$ recurrences in (12), together with
their initial values build up the vector recurrence

$\bar{g}_{n}=\gamma_{k-1}\bar{g}_{n-1}+\gamma_{k-2}\bar{g}_{n-2}+\cdots+\gamma_{0}\bar{g}_{n-k},\quad
n\geq k$ (14)

with initial vectors (13). In particular, (14) provides the last column vector
$\bar{g}_{k}$ of $\mathbf{G}^{\star}$. The linear independence of the column
vectors of $\mathbf{G}$ guarantees that

$\Delta=\det(\mathbf{G})\neq 0.$ (15)

Let $\bar{r}_{i}$ denote the $i$th column vector of the transposition
$\mathbf{G}^{\top}$ of $\mathbf{G}$ for each $i=1,2,\dots,k$. That is
$\bar{r}_{i}=[G_{0}^{(i)},G_{1}^{(i)},\dots,G_{k-1}^{(i)}]^{\top}$, the
entries are exactly the initial values of the $i$th sequence we fixed in (12).
Clearly, the vectors

$\bar{r}_{1},\bar{r}_{1}\dots,\bar{r}_{k}$ (16)

form a basis of the vector space $\mathbb{C}^{k}$.

Put

$\mathbf{M}=\mathbf{G}^{\star}\mathbf{G}^{-1}=\frac{1}{\Delta}\cdot\mathbf{G}^{\star}\cdot{\rm
adj}(\mathbf{G}).$

The extension of Lemma 2.1 of [9] from $\mathbb{R}$ to $\mathbb{C}$ shows that
the vector sequence $(\bar{g}_{n})$ generated by the initial vectors (13) and
by the vector recurrence (14) satisfies

$\bar{g}_{n+1}=\mathbf{M}\bar{g}_{n},\qquad n\geq 0.$ (17)

The proof of this lemma provides even that the characteristic polynomial of
matrix $\mathbf{M}$ is

$k_{\mathbf{M}}(x)=\det(x\mathbf{I}-\mathbf{M})=x^{k}-\gamma_{k-1}x^{k-1}-\cdots-\gamma_{1}x-\gamma_{0},$
(18)

which is also the characteristic polynomial of any recurrence of
$\Gamma_{k}^{(\gamma_{0},\gamma_{1},\dots,\gamma_{k-1})}$ ($\mathbf{I}$
denotes the $k\times k$ unit matrix). Thus
$k_{\mathbf{M}}(0)=\det(-\mathbf{M})=-\gamma_{0}$, and then
$\det(\mathbf{M})=(-1)^{k}(-\gamma_{0})$, is denoted in the sequel by
$\delta$. Hence

$\det(\mathbf{M}^{n})=\left(\det(\mathbf{M})\right)^{n}=\delta^{n}.$ (19)

This observation gives later the right-hand side of the principal identity of
this article (with a suitable homogeneous polynomial of degree $k$ on the
left-hand side).

Now turn our attention to the matrices

$\mathbf{M}^{n}=\left[m_{i,j}^{(n)}\right]_{i,j=1,2,\dots,k},\qquad
n\in\mathbb{N}.$

Since
$\mathbf{M}^{n}=\gamma_{k-1}\mathbf{M}^{n-1}+\gamma_{k-2}\mathbf{M}^{n-2}+\cdots+\gamma_{0}\mathbf{M}^{n-k}$
holds for $n\geq k$, therefore the same recurrence rule is valid for each
element-wise sequence $(m_{i,j}^{(n)})$ of the matrix sequence
$(\mathbf{M}^{n})$. That is

$m_{i,j}^{(n)}=\gamma_{k-1}m_{i,j}^{(n-1)}+\gamma_{k-2}m_{i,j}^{(n-2)}+\cdots+\gamma_{0}m_{i,j}^{(n-k)}.$

Such a sequence is determined by the initial values
$m_{i,j}^{(0)},m_{i,j}^{(1)},\dots,m_{i,j}^{(k-1)}$. Collect them into the
initial column vector $\overline{m}_{i,j}\in\mathbb{C}^{k}$ (look at (20)),
which can be given as a linear combination of the basis vectors (16). More
precisely, there exist uniquely determined coordinates
$c_{i,j}^{(u)}\in\mathbb{C}$, $u=1,2,\dots,k$, such that

$\overline{m}_{i,j}=\left[\begin{array}[]{c}m_{i,j}^{(0)}\\\ m_{i,j}^{(1)}\\\
\vdots\\\ m_{i,j}^{(k-1)}\\\
\end{array}\right]=\sum_{u=1}^{k}c_{i,j}^{(u)}\bar{r}_{u}.$ (20)

This is a system of $k$ linear equations in the $k$ unknowns
$c_{i,j}^{(1)},c_{i,j}^{(2)},\dots,c_{i,j}^{(k)}$ (if $i,j$ are fixed), and
the system can be solved, for instance, by Cramer’s rule. Assume that
$\mathbf{G}_{u}$ is the matrix derived by replacing the $u$th column vector of
$\mathbf{G}^{\top}$ by the vector $\overline{m}_{i,j}$. Then, using
$\det(\mathbf{M}^{\top})=\det(\mathbf{M})=\Delta$, clearly

$c_{i,j}^{(u)}=\frac{\det(\mathbf{G}_{u})}{\Delta}.$ (21)

Since the initial values determine a complete sequence of
$\Gamma_{k}^{(\gamma_{0},\gamma_{1},\dots,\gamma_{k-1})}$, the coefficients
(21) appearing in (20) descend for the whole sequence $(m_{i,j}^{(n)})$. Thus
the main consequence of the previous arguments is the equality

$m_{i,j}^{(n)}=\sum_{u=1}^{k}c_{i,j}^{(u)}G_{n}^{(u)}.$

In this manner, we are able to represent any entry of matrix $\mathbf{M}^{n}$
as a linear combination of the $n$th terms of the linear recurrences
$(G_{n}^{(1)}),(G_{n}^{(2)}),\dots,(G_{n}^{(k)})\in\Gamma_{k}^{(\gamma_{0},\gamma_{1},\dots,\gamma_{k-1})}$.
Subsequently, the determinant of $\mathbf{M}^{n}$ is a homogeneous polynomial
of degree $k$ in $G_{n}^{(1)},G_{n}^{(2)},\dots,G_{n}^{(k)}$. Denote this form
by $F$. Combining it with (19) we obtain

$F(G_{n}^{(1)},G_{n}^{(2)},\dots,G_{n}^{(k)})=\delta^{n},$ (22)

and the proof is complete. $\Box$

Assume now that the coefficients $\gamma_{i}$, and the initial terms of the
sequences $G_{n}^{(j)}$ are integers. Then $(G_{n}^{(j)})$ is a sequence of
integers ($j$ is fixed). Multiply both sides of (22) by $\Delta^{k}$, because
(21) is now a rational number with denominator dividing $\Delta$. Then
$\tilde{F}=\Delta^{k}F$ has integer coefficients. Consequently, the
polynomial-exponential diophantine equation

$\tilde{F}(x_{1},x_{2},\dots,x_{k})=\Delta^{k}\delta^{n}$ (23)

possesses infinitely many integer solutions in integers
$x_{1},x_{2},\dots,x_{k}$ and $n$. Now we record the results in

######  Theorem 4.

Given the recursive sequences (12) of integers with initial values (13) such
that (15) holds. Then for any $n\geq 0$

$(x_{1},x_{2},\dots,x_{k})=(G_{n}^{(1)},G_{n}^{(2)},\dots,G_{n}^{(k)})$

is the solution to the diophantine equation

$\tilde{F}(x_{1},x_{2},\dots,x_{k})=\Delta^{k}\delta^{n},$ (24)

where the coefficients of the homogeneous form $\tilde{F}$ depend on the
parameters of the sequences.

###### Proof.

The proof is given before the enunciation of the theorem. ∎

Note that the proof is constructive in the sense that following the method we
can compute $\tilde{F}$, $\Delta$, and $\delta$ if the initial values and the
recurrence rule is fixed. This will be illustrated later, in Section 6 for
binary recurrences in general, and for a triple of ternary recurrences.

###  3.2 Alternative proof of Theorem 1

We provide here an alternative proof for the existence of the form ${F}$ on
the left-hand side of (22). The notation is taken from the preceding parts of
Section 3. Observe first that

${\bf G}^{*}={\bf G}{\bf T}$

with the matrix

${\mathbf{T}}=\left[\begin{array}[]{ccccc}0&0&\cdots&0&\gamma_{0}\\\
1&0&\cdots&0&\gamma_{1}\\\ \vdots&\vdots&\ddots&\vdots&\vdots\\\
0&0&\cdots&0&\gamma_{k-2}\\\ 0&0&\cdots&1&\gamma_{k-1}\end{array}\right].$

Thus we have

${\bf M}={\bf G}^{*}{\bf G}^{-1}={\bf G}{\bf T}{\bf G}^{-1}.$

This matrix equality immediately implies

  * •

$\det({\bf M})=\det({\bf T})=(-1)^{k-1}\gamma_{0}$, and

  * •

${\bf M}^{n}={\bf G}{\bf T}^{n}{\bf G}^{-1}$ for $n\geq 0$.

Here ${\bf G}{\bf T}^{n}$ is a matrix with the column vectors
$\bar{g}_{n},\bar{g}_{n+1},\ldots,\bar{g}_{n+k-1}$. On the other hand, from
(17) we know $\bar{g}_{n+j}={\bf M}^{j}\bar{g}_{n}$. Hence all entries of
${\bf G}{\bf T}^{n}$ are linear combinations of the terms
$G_{n}^{(1)},G_{n}^{(2)},\ldots,G_{n}^{(k)}$, where the coefficients are the
elements of ${\bf M}^{j},j=0,\ldots,k-1$, and they are independent from $n$.
Subsequently, the determinant of ${\bf G}{\bf T}^{n}$ is a signed sum of the
products of $k$ linear forms in $G_{n}^{(1)},G_{n}^{(2)},\ldots,G_{n}^{(k)}$
i.e. a homogeneous form of degree $k$. Multiplying this by $\det({\bf
G}^{-1})$, which is the determinant of a constant matrix we obtain that
$\det({\bf M}^{n})$ is also a homogeneous form of degree $k$. $\Box$

##  4 Decomposability of $\mathbf{F}$

This section is devoted to study, and prove the decomposability of the
homogeneous polynomial $F$ provided in Section 3. Recall that
$F(x_{1},x_{2},\dots,x_{k})=\tilde{F}(x_{1},x_{2},\dots,x_{k})/\Delta^{k}$
(see (22) and (23)).

Proof of Theorem 2. The proof consists of two main parts. In the first step,
we show that a specific homogeneous polynomial, say $F_{S}$ is decomposable if
the initial $k$ sequences from
$\Gamma_{k}^{(\gamma_{0},\gamma_{1},\dots,\gamma_{k-1})}$ are chosen
advantageously. Then, in the second part, we find a connection between these
favorable sequences and arbitrary package of $k$ sequences.

Part 1. Recall that the characteristic polynomial $k_{\mathbf{M}}(x)$ of the
family $\Gamma_{k}^{(\gamma_{0},\gamma_{1},\dots,\gamma_{k-1})}$ of
homogeneous linear recurrences (11) we investigate is (18). Assume that it has
decomposition

$k_{\mathbf{M}}(x)=(x-\alpha_{1})^{m_{1}}(x-\alpha_{2})^{m_{2}}\cdots(x-\alpha_{h})^{m_{h}}$
(25)

into linear factors, where $\alpha_{i}\in\mathbb{C}$ ($i=1,2,\dots,h$) are
distinct, and $m_{1}+m_{2}+\cdots+m_{h}=k$. For each pair $(i,j)$, where
$i\in\\{1,2,\dots,h\\}$ and $j\in\\{0,1,\dots,m_{i}-1\\}$ consider the
sequences

$S_{n}^{(i,j)}=n^{j}\alpha_{i}^{n},\quad(n\geq 0).$ (26)

Note that the range for $j$ depends on the value of $i$, but we do not
indicate this fact in the notation.

Sequences (26) are belonging to
$\Gamma_{k}^{(\gamma_{0},\gamma_{1},\dots,\gamma_{k-1})}$, this fact is based
on the following two observations, or simply we may refer to the theory of
difference equations, see e.g. the classical book of Milne-Thomson [8, Chapter
XIII]. Firstly, if the multiplicity of an $\alpha_{i}$ is $m_{i}$, then
$\alpha_{i}$ is also a root of the derivatives $k^{(j)}_{\mathbf{M}}(x)$ for
$j=0,1,\dots,m_{i}-1$. Secondly, from the theory of Stirling number of second
kind we know that $n^{j}=\sum_{v=0}^{j}{j\brace v}(n)_{v}$, where ${j\brace
v}$ denotes a Stirling number of second kind, and
$(n)_{v}=n(n-1)\cdots(n-v+1)$ is a falling factorial.

Another important argument is that the sequences in (26) are
$\mathbb{C}$-linearly independent, consequently they form a basis of
$\Gamma_{k}^{(\gamma_{0},\gamma_{1},\dots,\gamma_{k-1})}$. This follows again
from [8, Chapter XIII]. (A similar result is given in [6].)

Analogously to $\mathbf{G}$ we define the matrix $\mathbf{G}_{S}$ by the
initial values of the sequences $S_{n}^{(i,j)}$ such that the first row
contains the initial values of $S_{n}^{(1,0)}$, etc. The matrix
$\mathbf{G}_{S}$ can be split into horizontal stripes such that stripe
$i\in\\{1,2,\dots,h\\}$ contains $m_{i}$ rows. The enumeration of stripes
begins on the top of the matrix, and the entries of stripe $i$ are given as
follows:

$\mathbf{G}_{S}=\left[\begin{array}[]{cccccccc}&&&&&\vdots&&\\\
\hdashline&&&&&\vdots&&\\\ \hdashline
1&\alpha_{i}&\alpha_{i}^{2}&\alpha_{i}^{3}&\dots&&\dots&\alpha_{i}^{k-1}\\\
0&\alpha_{i}&2\alpha_{i}^{2}&3\alpha_{i}^{3}&\dots&&\dots&(k-1)\alpha_{i}^{k-1}\\\
0&\alpha_{i}&2^{2}\alpha_{i}^{2}&3^{2}\alpha_{i}^{3}&\dots&&\dots&(k-1)^{2}\alpha_{i}^{k-1}\\\
\vdots&\vdots&\vdots&\vdots&&\ddots&&\vdots\\\
0&\alpha_{i}&2^{m_{i}-1}\alpha_{i}^{2}&3^{m_{i}-1}\alpha_{i}^{3}&\dots&&\dots&(k-1)^{m_{i}-1}\alpha_{i}^{k-1}\\\
\hdashline&&&&&\vdots&&\\\ \hdashline&&&&&\vdots&&\\\ \end{array}\right].$

Let $M_{i}=m_{1}+m_{2}+\cdots+m_{i-1}$. The numbering of rows of stripe $i$
are $M_{i}+(j+1)$, where $j=0,\dots,m_{i}-1$. The matrix
$\mathbf{G}_{S}^{\star}$ is analogous to $\mathbf{G}^{\star}$, too. We define
even the block diagonal matrix

$\mathbf{B}=\left[\begin{array}[]{cccc}\mathbf{B}_{1}&\mathbf{O}&\cdots&\mathbf{O}\\\
\mathbf{O}&\mathbf{B}_{2}&\cdots&\mathbf{O}\\\ \vdots&\vdots&\ddots&\vdots\\\
\mathbf{O}&\mathbf{O}&\cdots&\mathbf{B}_{h}\end{array}\right]\in\mathbb{C}^{k\times
k}\;{\rm
with}\;\mathbf{B}_{i}=\left[\begin{array}[]{cccccc}\alpha_{i}&0&\cdots&0&\cdots&0\\\
\alpha_{i}&\alpha_{i}&\cdots&0&\cdots&0\\\
\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\\
\alpha_{i}&\cdots&\cdots&\alpha_{i}&\cdots&0\\\
\vdots&\vdots&b_{u,v}^{(i)}&\vdots&\ddots&\vdots\\\
\alpha_{i}&\cdots&\cdots&\cdots&\cdots&\alpha_{i}\end{array}\right]\in\mathbb{C}^{m_{i}\times
m_{i}}$

for $i=1,2,\dots,h$ such that the general term
$b_{u,v}^{(i)}=\binom{u}{v}\alpha_{i}$ is the entry of the $(u+1)$th row and
$(v+1)$th column of $\mathbf{B}_{i}$ with the conditions $0\leq v\leq u\leq
m_{i}-1$. Here the minors $\mathbf{O}$ are suitable zero matrices. Since
$\mathbf{B}_{i}$ is a lower diagonal matrix then $\mathbf{B}$ is so.

Using the notation above we will show that

$\mathbf{G}_{S}^{*}=\mathbf{B}\mathbf{G}_{S}.$

Note that block $\mathbf{B}_{i}$ has influence only on stripe $i$ of
$\mathbf{G}_{S}$ during carrying out the matrix multiplication
$\mathbf{B}\mathbf{G}_{S}$. In stripe $i$ we have exactly the rows
$M_{i}+1+u$, where $u=0,1,\dots,m_{i}-1$. Our deal is to calculate the dot
product444The dot product of the vectors $\bar{\mu}=[\mu_{1},\ldots,\mu_{k}]$
and $\bar{\nu}^{\top}=[\nu_{1},\ldots,\nu_{k}]^{\top}$ is the complex number
$\sum_{j=1}^{k}\mu_{j}\nu_{j}$. of row $M_{i}+1+u$ from $\mathbf{B}$ and
column $\ell$ from $\mathbf{G}_{S}$, where $\ell=1,2,\dots,k$. This is given
in details by

$\left[\begin{array}[]{cccccccccc}0&\cdots&0&\binom{u}{0}\alpha_{i}&\binom{u}{1}\alpha_{i}&\cdots&\binom{u}{u}\alpha_{i}&0&\cdots&0\\\
\end{array}\right]\cdot\left[\begin{array}[]{c}\vdots\\\
\hdashline\alpha_{i}^{\ell-1}\\\ (\ell-1)\alpha_{i}^{\ell-1}\\\ \vdots\\\
(\ell-1)^{u}\alpha_{i}^{\ell-1}\\\ \vdots\\\
(\ell-1)^{m_{i}-1}\alpha_{i}^{\ell-1}\\\ \hdashline\vdots\end{array}\right].$

Hence the dot product equals

$\binom{u}{0}\alpha_{i}^{\ell}+\binom{u}{1}(\ell-1)\alpha_{i}^{\ell}+\cdots+\binom{u}{u}(\ell-1)^{u}\alpha_{i}^{\ell}=\left((l-1)+1\right)^{u}\alpha_{i}^{\ell}=\ell^{u}\alpha_{i}^{\ell}=S_{\ell}^{(i,u)}.$

Recall that $S_{\ell}^{(i,u)}$ is the general term of the matrix
$\mathbf{G}_{S}^{*}$ such that it is the element of the $(u+1)$th row of
stripe $i$ in the column $\ell$ ($\ell=1,2,\dots,k$).

Subsequently, we have

$\mathbf{M}_{S}=\mathbf{G}_{S}^{*}\mathbf{G}_{S}^{-1}=\left(\mathbf{B}\mathbf{G}_{S}\right)\mathbf{G}_{S}^{-1}=\mathbf{B},$

and then $\mathbf{M}_{S}^{n}=\mathbf{B}^{n}$ follows. We know that
$\mathbf{B}$ is a lower diagonal matrix. Thus $\det(\mathbf{B})$ is the
product of the elements lying in the main diagonal, i.e.

$\det(\mathbf{B})=\alpha_{1}^{m_{1}}\alpha_{2}^{m_{2}}\cdots\alpha_{h}^{m_{h}}.$

Finally,

$\det\left(\mathbf{M}_{S}^{n}\right)=\left(\det(\mathbf{B})\right)^{n}=\alpha_{1}^{m_{1}n}\alpha_{2}^{m_{2}n}\cdots\alpha_{h}^{m_{h}n}=\left(S_{n}^{(1,0)}\right)^{m_{1}}\left(S_{n}^{(2,0)}\right)^{m_{2}}\cdots\left(S_{n}^{(h,0)}\right)^{m_{h}}.$

So we have found that $\det\left(\mathbf{M}_{S}^{n}\right)$ is a corresponding
value of the decomposable form

$F_{S}(y_{1},y_{2},\dots,y_{h})=y_{1}^{m_{1}}y_{2}^{m_{2}}\cdots
y_{h}^{m_{h}}$

at the point
$\left((S_{n}^{(1,0)}),(S_{n}^{(2,0)}),\cdots,(S_{n}^{(h,0)})\right)$. Thus
the assertion of the theorem holds for this particular choice of the
recurrences.

Part 2. Recall that sequences (12) form a basis in
$\Gamma_{k}^{(\gamma_{0},\gamma_{1},\dots,\gamma_{k-1})}$ because $\Delta\neq
0$. Hence there uniquely exists a matrix
$\mathbf{A}=[a_{i,j}]\in\mathbb{C}^{h\times k}$ such that

$\left[\begin{array}[]{cccc}S_{n}^{(1,0)}&S_{n}^{(2,0)}&\cdots&S_{n}^{(h,0)}\end{array}\right]^{\top}=\mathbf{A}\left[\begin{array}[]{cccc}G_{n}^{(1)}&G_{n}^{(2)}&\cdots&G_{n}^{(k)}\end{array}\right]^{\top}.$
(27)

Consider now the substitution
$\bar{y}=[y_{1},y_{2},\ldots,y_{h}]^{\top}={\mathbf{A}}[x_{1},x_{2},\ldots,x_{k}]^{T}={\mathbf{A}}\bar{x}$.
Denoting by $\bar{a}_{i}$ the $i$th row vector of $\mathbf{A}$ we compute the
dot product

$y_{i}=\bar{a}_{i}[x_{1},x_{2},\ldots,x_{k}]^{\top}$

for every $i=1,2,\ldots,h$. Now we can define
$F(x_{1},\ldots,x_{k})=F(\bar{x})$ as follows:

$F_{S}(\bar{y})=y_{1}^{m_{1}}y_{2}^{m_{2}}\cdots
y_{h}^{m_{h}}=\prod_{i=1}^{h}\left(\bar{a}_{i}[x_{1},x_{2}\ldots,x_{k}]^{\top}\right)^{m_{i}}=F(\bar{x}).$

Obviously, $F$ is a decomposable form of degree $k$ with the property

$F(G_{n}^{(1)},\ldots,G_{n}^{(k)})=((-1)^{k}k_{\mathbf{M}}(0))^{n}=\delta^{n},\quad(n=0,1,\ldots).$

Thus the proof is complete. $\Box$

######  Remark 1.

If every zero of the characteristic polynomial $k_{\mathbf{M}}(x)$ is simple
(i.e. $h=k$), then the matrix ${\mathbf{G}}_{S}$ is simplified to

${\mathbf{G}}_{S}=\left[\begin{array}[]{cccc}1&\alpha_{1}&\cdots&\alpha_{1}^{k-1}\\\
1&\alpha_{2}&\cdots&\alpha_{2}^{k-1}\\\ \vdots&\vdots&\ddots&\vdots\\\
1&\alpha_{k}&\cdots&\alpha_{k}^{k-1}\end{array}\right]=\mathbf{A}\mathbf{G}$

(the second equality is implied by (27)). Consequently,
$\mathbf{A}=\mathbf{G}_{S}\mathbf{G}^{-1}$, and then

$\bar{y}=\mathbf{G}_{S}\mathbf{G}^{-1}\bar{x},$

Finally, we obtain
$F_{S}(\bar{y})=F_{S}(\mathbf{G}_{S}\mathbf{G}^{-1}\bar{x})=F(\bar{x})$.

At the end of this section, we show a general example to demonstrate the power
of our results.

Example. Consider the sequences of (12) such that the characteristic
polynomial has factorization (25). Assume that we have the specific initial
vectors

$\bar{g}_{0}=\left[\begin{array}[]{c}1\\\ 0\\\ \vdots\\\ 0\\\
\end{array}\right],\;\bar{g}_{1}=\left[\begin{array}[]{c}0\\\ 1\\\ \vdots\\\
0\\\ \end{array}\right],\dots,\;\bar{g}_{k-1}=\left[\begin{array}[]{c}0\\\
0\\\ \vdots\\\ 1\\\ \end{array}\right].$ (28)

Using the advantageous properties of this orthonormal basis, we can easily
show that

$S_{n}^{(j,0)}=1\cdot G_{n}^{(1)}+\alpha_{j}\cdot
G_{n}^{(2)}+\cdots+\alpha_{j}^{k-1}\cdot G_{n}^{(k)},\quad(j=1,2,\dots,h).$

Consequently,

$y_{j}=x_{1}+\alpha_{j}x_{2}+\cdots+\alpha_{j}^{k-1}x_{k},\quad(j=1,2,\dots,h),$

and then

${F}(x_{1},x_{2},\dots,x_{k})=\prod_{i=1}^{h}(x_{1}+\alpha_{j}x_{2}+\cdots+\alpha_{j}^{k-1}x_{k})^{m_{j}}$

follows. Hence the complete factorization of the form ${F}$ is determined.
Note that the simplicity depends on the features of the orthonormal basis
(28).

##  5 Proof of the corollaries and of Theorem 3

Proof of Corollary 1. The entries of the vectors $\bar{g}_{j}$,
$j=0,\dots,k-1$ are the initial values of the sequences $(G_{n+j})$,
$j=0,\dots,k-1$. At the beginning of the proof of Theorem 1 we pointed out
that the linear independence of the vectors $\bar{g}_{j}$ and the linear
independence of the sequences $(G_{n+j})$ is equivalent. Thus the sequences
$(G_{n+j})$, $j=0,\dots,k-1$ are linearly independent and Theorem 1 implies
the existence of a homogeneous form $F$, while Theorem 2 justifies the
decomposability of $F$. $\Box$

Proof of Corollary 2. If the sequences $(G_{n}^{(j)})$, $j=1,\dots,k$ are
linearly dependent, then enlarging their set with the sequence
$(\gamma_{0}^{n})$ the linear dependent property remains true, and this is a
very special algebraic dependence. Otherwise, if $(G_{n}^{(j)}),j=1,\dots,k$
are linearly independent, then Theorem 1, more precisely equation (22)
verifies the algebraic dependence. $\Box$

Proof of Theorem 3. Assume that $P(X)=z_{k}X^{k}+z_{k-1}X^{k-1}+\ldots+z_{0}$,
where $z_{0}\not=0$. The differential equation with characteristic polynomial
$P(X)$ has the form

$z_{k}f(z)^{(k)}+z_{k-1}f(z)^{(k-1)}+\ldots+z_{0}=0.$ (29)

Here $f^{(\ell)}$ denotes the $\ell$th derivative of $f$. The pair-wisely
distinct zeros of $P(X)$ are assigned by
$\alpha_{1},\alpha_{2},\dots,\alpha_{k}$. The function $f(z)$ is a solution of
(29) if and only if it has the form

$f(z)=f_{1}\alpha_{1}^{z}+f_{2}\alpha_{2}^{z}+\ldots+f_{k}\alpha_{k}^{z},$

with complex numbers $f_{1},f_{2},\dots,f_{k}$.

The set of solutions of (29) form a $\mathbb{C}$-vector space with respect to
the addition of functions and multiplication with complex numbers. We denote
it by $S(P)$. The functions
$\alpha_{1}^{z},\alpha_{2}^{z},\dots,\alpha_{k}^{z}$ are linearly independent,
thus the dimension of $S(P)$ is $k$.

Assume that $G_{j}(z),j\leq k_{0}$ are pairwise different solutions of (29).
If they are $\mathbb{C}$-linearly dependent, which holds always when
$k_{0}>k$, then the same is true if we enlarge their set with the function
$((-1)^{k}P(0))^{z}$. It remains to examine the case when $k_{0}=k$ and the
functions $G_{j}(z),j\leq k_{0}$ are linearly independent. Then they form a
bases of $S(P)$. The functions
$\alpha_{1}^{z},\alpha_{2}^{z},\dots,\alpha_{k}^{z}$ belong to $S(P)$, thus
there exist complex numbers $a_{ij},1\leq i,j\leq k$ such that

$\alpha_{i}^{z}=\sum_{j=1}^{k}a_{ij}G_{j}(z).$ (30)

On the other hand

$\alpha_{1}^{z}\alpha_{2}^{z}\cdots\alpha_{k}^{z}=(\alpha_{1}\alpha_{2}\cdots\alpha_{k})^{z}=((-1)^{k}P(0))^{z}.$

Inserting here the linear relations (30) we obtain the statement. $\Box$

##  6 Binary and ternary recurrences

###  6.1 Binary recurrences, a general identity

This subsection is devoted to present the general identity (33) below with two
binary recurrences satisfying the same recurrence relation. This is a special
case of (22). On the other hand it provides a common generalization of
(7)-(9). At the end of this subsection a few examples will illustrate (33). In
the computations, we will follow the arguments of the previous sections.

Assume $k=2$. For simplicity suppose that the two recurrent sequences are
$(G_{n})$ and $(H_{n})$, their initial values are $G_{0},G_{1}$ and
$H_{0},H_{1}$, respectively, furthermore put $\gamma_{1}=A$, $\gamma_{0}=B$.
Then the two sequences above belong to

$\Gamma_{2}^{(B,A)}=\left\\{(x_{n})_{n\in\mathbb{Z}}\in\mathbb{C}^{\infty}\mid
x_{n}=Ax_{n-1}+Bx_{n-2},\;n\geq 2\right\\}.$

Now

$\mathbf{G}=\left[\begin{array}[]{cc}G_{0}&G_{1}\\\
H_{0}&H_{1}\end{array}\right],\quad\quad\mathbf{G}^{\star}=\left[\begin{array}[]{cc}G_{1}&AG_{1}+BG_{0}\\\
H_{1}&AH_{1}+BH_{0}\end{array}\right],$

and assume that $\Delta=\det(\mathbf{G})=G_{0}H_{1}-G_{1}H_{0}\neq 0$. Then

$\mathbf{G}^{-1}=\frac{1}{\Delta}\left[\begin{array}[]{cc}{H_{1}}&-{G_{1}}\\\
-{H_{0}}&{G_{0}}\end{array}\right].$

Introduce the notation $C_{G}=G_{1}^{2}-AG_{0}G_{1}-BG_{0}^{2}$ (see also
before the equations (7)-(9)), and analogously
$C_{H}=H_{1}^{2}-AH_{0}H_{1}-BH_{0}^{2}$. We even define
$E_{10}=G_{1}H_{1}-AG_{1}H_{0}-BG_{0}H_{0}$, and
$E_{01}=G_{1}H_{1}-AG_{0}H_{1}-BG_{0}H_{0}$. One can easily see that

$\mathbf{M}=\mathbf{G}^{\star}\mathbf{G}^{-1}=\frac{1}{\Delta}\left[\begin{array}[]{cc}{E_{10}}&{-C_{G}}\\\
{C_{H}}&{-E_{01}}\end{array}\right].$ (31)

Clearly, $k_{\mathbf{M}}(x)=x^{2}-Ax-B=(x-\alpha)(x-\beta)$,
$\det(\mathbf{M})=-B$. Obviously, $\det(\mathbf{M}^{n})=(-B)^{n}$,
$A=\alpha+\beta$ and $B=-\alpha\beta$. (Note that $\alpha$ and $\beta$ are not
necessarily distinct.)

The element sequences of the powers of matrix $\mathbf{M}$ satisfy

$m_{i,j}^{(n)}=Am_{i,j}^{(n-1)}+Bm_{i,j}^{(n-2)},\qquad(n\geq 2;\;1\leq
i,j\leq 2),$

the initial values are clear from $\mathbf{M}^{0}=\mathbf{I}$ and from
$\mathbf{M}$ (here $\mathbf{I}$ is the $2\times 2$ unit matrix). Now

$\left[\begin{array}[]{c}{m_{i,j}^{(0)}}\\\
{m_{i,j}^{(1)}}\end{array}\right]=c_{i,j}^{(1)}\left[\begin{array}[]{c}G_{0}\\\
G_{1}\end{array}\right]+c_{i,j}^{(2)}\left[\begin{array}[]{c}H_{0}\\\
H_{1}\end{array}\right],\quad\quad(1\leq i,j\leq 2).$ (32)

Once we have the solutions to (32) in $c_{i,j}^{(1)}$ and $c_{i,j}^{(2)}$,
then $m_{i,j}^{(n)}=c_{i,j}^{(1)}G_{n}+c_{i,j}^{(2)}H_{n}$ holds. A
straightforward calculation shows that

$\mathbf{M}^{n}=\frac{1}{\Delta}\left[\begin{array}[]{lr}(-H_{0}m_{1,1}^{(1)}+H_{1})G_{n}+(G_{0}m_{1,1}^{(1)}-G_{1})H_{n}&-H_{0}m_{1,2}^{(1)}G_{n}+G_{0}m_{1,2}^{(1)}H_{n}\\\
-H_{0}m_{2,1}^{(1)}G_{n}+G_{0}m_{2,1}^{(1)}H_{n}&(-H_{0}m_{2,2}^{(1)}+H_{1})G_{n}+(G_{0}m_{2,2}^{(1)}-G_{1})H_{n}\end{array}\right],$

where we used the values $m_{1,1}^{(0)}=m_{2,2}^{(0)}=1$,
$m_{1,2}^{(0)}=m_{2,1}^{(0)}=0$. In fact, to determine $\det(\mathbf{M}^{n})$
we do not need the exact values $m_{i,j}^{(1)}$ given in (31), only the
identities
$m_{1,1}^{(1)}m_{2,2}^{(1)}-m_{1,2}^{(1)}m_{2,1}^{(1)}=\det(\mathbf{M})=-B$
and $m_{1,1}^{(1)}+m_{2,2}^{(1)}={\rm tr}(\mathbf{M})=A$. Indeed, if we figure
out simply the determinant of the matrix $\mathbf{M}^{n}$, and collect the
coefficient of the terms $G_{n}^{2}$, $G_{n}H_{n}$, and $H_{n}^{2}$,
respectively, then the key moment of the simplification is the application of
these identities. Finally, the computations lead to

$(-B)^{n}=\det\left(\mathbf{M}^{n}\right)=\frac{C_{H}}{\Delta^{2}}G_{n}^{2}+\frac{C_{GH}}{\Delta^{2}}G_{n}H_{n}+\frac{C_{G}}{\Delta^{2}}H_{n}^{2},$

where $C_{GH}=-(E_{10}+E_{01})$. Moreover one can show that $C_{GH}$ can be
given by using the corresponding associate sequences:
$C_{GH}=G_{0}\widehat{H}_{1}-G_{1}\widehat{H}_{0}=H_{0}\widehat{G}_{1}-H_{1}\widehat{G}_{0}$.
Then we have the desired equality given in

######  Theorem 5.

The terms of the recurrences above satisfy

$C_{H}G_{n}^{2}+C_{GH}G_{n}H_{n}+C_{G}H_{n}^{2}=(-B)^{n}\Delta^{2}.$ (33)

This is a nice common generalization of (7)-(9). Indeed, observe that Theorem
5 leads to (7) whenever $(H)$ is the associate sequence of $(G)$. Really, it
is easy to show that $C_{\widehat{G}}=-DC_{G}$, $C_{G\widehat{G}}=0$ (i.e.
$C_{GH}$ vanishes if $(H)=(\widehat{G})$), and in this particular case
$\Delta=-2C_{G}$ holds. Insert these values into (33) to get immediately (7).
For (9) let $H_{n}=G_{n+1}$, the details here are omitted.

The binary quadratic form on left-hand side of (33) is trivially decomposable.
The decomposition is formulated by

$\left((H_{1}-\alpha H_{0})G_{n}-(G_{1}-\alpha
G_{0})H_{n}\right))\cdot\left((H_{1}-\beta H_{0})G_{n}-(G_{1}-\beta
G_{0})H_{n}\right)=(-B)^{n}\Delta^{2}.$

We now illustrate Theorem 5 by five examples given in Table 1.

$(A,B)$ | $\mathbf{G}$ | $\mathbf{M}$ | $(-B)^{n}\Delta^{2}=C_{H}G_{n}^{2}+C_{GH}G_{n}H_{n}+C_{G}H_{n}^{2}$
---|---|---|---
$(0,4)$ | $\left[\begin{array}[]{cc}1&2\\\ 2&3\end{array}\right]$ | $\left[\begin{array}[]{cc}2&0\\\ 7&-2\end{array}\right]$ | $(-4)^{n}(-1)^{2}=-7G_{n}^{2}+4G_{n}H_{n}=G_{n}(4H_{n}-7G_{n})$
$(2,-1)$ | $\left[\begin{array}[]{cc}2&3\\\ 4&5\end{array}\right]$ | $\left[\begin{array}[]{cc}1/2&1/2\\\ -1/2&3/2\end{array}\right]$ | $1^{n}(-2)^{2}=G_{n}^{2}-2G_{n}H_{n}+H_{n}^{2}=(G_{n}-H_{n})^{2}$
$(7,-10)$ | $\left[\begin{array}[]{cc}0&1\\\ 2&7\end{array}\right]$ | $\left[\begin{array}[]{cc}7/2&1/2\\\ 9/2&7/2\end{array}\right]$ | $10^{n}(-2)^{2}=-9G_{n}^{2}+H_{n}^{2}$
$(7,-10)$ | $\left[\begin{array}[]{cc}1&2\\\ 1&5\end{array}\right]$ | $\left[\begin{array}[]{cc}2&0\\\ 0&5\end{array}\right]$ | $10^{n}3^{2}=9G_{n}H_{n}$
$(4,-1)$ | $\left[\begin{array}[]{cc}1&2\\\ 3&4\end{array}\right]$ | $\left[\begin{array}[]{cc}13/2&-3/2\\\ 23/2&-5/2\end{array}\right]$ | $1^{n}(-2)^{2}=-23G_{n}^{2}+18G_{n}H_{n}-3H_{n}^{2}$
Table 1: Binary recurrence examples.

One or two coefficients from $\\{C_{G},C_{H},C_{GH}\\}$ may vanish in (33),
which provides a large variety of identities.

###  6.2 Ternary recurrences

Instead of pointing on the complicated general formula it is better to present
an example which is typical of the ternary forms we are studying. Examples for
higher order linear recurrences can be analogously produced.

There are only a few papers in the literature which work with three different
ternary recurrences satisfying the same recurrence rule. An example is [13],
which studies Narayana sequence $(A_{n})$, Narayana-Lucas sequence $(B_{n})$,
and Narayana-Perrin sequence $(C_{n})$. These recurrences satisfy

$x_{n}=x_{n-1}+x_{n-3}$

with initial values given by

$A_{0}=0,A_{1}=1,A_{2}=1;\quad B_{0}=3,B_{1}=1,B_{2}=1;\quad
C_{0}=3,C_{1}=0,C_{2}=2,$

respectively. Let $\alpha_{i}$ ($i=1,2,3$) denote the simple zeros of the
characteristic polynomial $k(x)=x^{3}-x^{2}-1$ such that
$\alpha_{1}\in\mathbb{R}$ and $\alpha_{3}$ is the complex conjugate of
$\alpha_{2}$. Following the the method we described in details it leads to the
diophantine equation

$-187x^{3}+159x^{2}y-45x^{2}z-189xy^{2}+306xyz-117xz^{2}+y^{3}-45y^{2}z+63yz^{2}-27z^{3}=-216$
(34)

possessing infinitely many integer solutions $x=A_{n}$, $y=B_{n}$, $z=C_{n}$.
In this case, $\Delta=-6$, and the base of the exponential term is $1$. Note
that all the 10 coefficients in the corresponding $\tilde{F}$ are non-zero.
The ternary form of (34) can be decomposed in the algebraic number field
$\mathbb{Q}[\alpha_{1},\alpha_{2}]$ as

$-\prod_{i=1}^{3}\left((3\alpha_{i}^{2}+3\alpha_{i}-2)x+(-3\alpha_{i}^{2}+3\alpha_{i}+2)y+(3\alpha_{i}^{2}-3\alpha_{i})z\right).$

### Acknowledgments

We thank Robert Tichy for his help in the formulation of Theorem 3. K. Győry
and L. Szalay were supported by the Hungarian National Foundation for
Scientific Research Grant No. 128088, and No. 130909. For L. Szalay this
research was supported by the Slovak Scientific Grant Agency VEGA 1/0776/21.

## References

  * [1] Z. I. Borevic̆ and I. R. S̆afarevic̆, Number Theory (Russian), Izdat. Nauka, Moscow, 1964. English translation: A. I. Borevich and I. R. Shafarevich, Number Theory, Pure and Applied Mathematics, Vol. 20, Academic Press, New York-London, 1966.
  * [2] I. M. Craveiro, E. V. Pereira Spreafico, and M. Rachidi, Generalized Cassini identities via the generalized Fibonacci fundamental system. Applications, Indian J. Pure Appl. Math., (2023), https://doi.org/10.1007/s13226-023-00430-1.
  * [3] H. W. Gould, A history of the Fibonacci $Q$-matrix and a higher-dimensional problem, Fibonacci Quart., 19 (1981), 250-257.
  * [4] K. Győry, On the numbers of families os solutions of systems of decomposable form equations, Publ. Math. Debrecen, 42 (1993), 65-101.
  * [5] J. P. Jones, Diophantine representation of the Fibonacci numbers, Fibonacci Quart., 13 (1975), 84-88.
  * [6] D. Kalman, The generalized Vandermonde matrix, Math. Mag., 57 (1984), 15-21.
  * [7] K. Königsberger. Analysis 1, 6. edition, Springer Berlin Heidelberg, 2003.
  * [8] L. M. Milne-Thomson, The Calculus of Finite Differences, Macmillan, 1933.
  * [9] L. Németh and L. Szalay, Power sums in hyperbolic Pascal triangles, An. Şt. Univ. Ovidius Constanţa, 26 (2018), 189-203.
  * [10] A. Pethő, On the solution of the equation $G_{n}=P(x)$, in Fibonacci Numbers and Their Applications, D. Reidel Publ. Comp. 1986, 193-201.
  * [11] W. M. Schmidt, Norm form equations, Ann. Math., 96 (1972), 526-551.
  * [12] T. N. Shorey and R. Tijdeman, Exponential Diophantine Equations, Cambridge Tracts in Mathematics, 87. Cambridge Univ. Press 1986.
  * [13] Y. Soykan, On generalized Narayana numbers, Int. J. Adv. Appl. Math. Mech., 7 (2020), 43-56.