Squaring the terms of an ℓth order linear recurrence

March 12, 2003

Toufik Mansour ^{1}

Department of Mathematics, Chalmers University of Technology, S-412 96 Göteborg, Sweden

                           toufik@math.chalmers.se

1 Introduction and the Main result

An ℓth order linear recurrence is a sequence in which each is a linear combination of the ℓ previous terms. The symbolic representation of an ℓth order linear recurrence defined by

a_{n} = ∑_{j=1}^{ℓ} p_{j}a_{n−j} = p_{1}a_{n−1} + p_{2}a_{n−2} + ⋯ + p_{ℓ}a_{n−ℓ},  (1)

is (a_{n}(c_{0}, …, c_{ℓ−1}; p_{1}, …, p_{ℓ}))_{n≥0}, or briefly (a_{n})_{n≥0}, where the p_{i} are constant coefficients, with given a_{j} = c_{j} for all j = 0, 1, …, ℓ − 1, and n ≥ ℓ; in such a context, (a_{n})_{n≥0} is called an ℓ-sequence.

In the case ℓ = 2, this sequence is called Horadam’s sequence and was introduced, in 1965, by Horadam [4, 5], and it generalizes many sequences (see [1, 6]). Examples of such sequences are the Fibonacci numbers (F_{n})_{n≥0}, the Lucas numbers (L_{n})_{n≥0}, and the Pell numbers (P_{n})_{n≥0}, when one has the following initial conditions: p_{1} = p_{1} = c_{1} = 1, c_{0} = 0; p_{1} = p_{2} = c_{1} = 1, c_{0} = 2; and p_{1} = 2, p_{2} = c_{1} = 1, c_{0} = 0; respectively. In 1962, Riordan [8] found the generating function for powers of Fibonacci numbers. He proved that the generating function F_{k}(x) = ∑_{n≥0} F_{n}^{k}x^{n} satisfies the recurrence relation

(1 − a_{k}x + (−1)^{k}x^{2})F_{k}(x) = 1 + kx ∑_{j=1}^{[k/2]}(−1)^{j} \frac{a_{kj}}{j} F_{k−2j}((−1)^{i}x)

for k ≥ 1, where a_{1} = 1, a_{2} = 3, a_{s} = a_{s−1} + a_{s−2} for s ≥ 3, and (1 − x − x^{2})^{−j} = ∑_{k≥0} a_{kj}x^{k−2j}. Horadam [5] gave a recurrence relation for H_{k}(x) (see also [3]). Haukkanen [2] studied linear combinations of Horadam’s sequences and the generating function of the ordinary product of two of Horadam’s sequences. Recently, Mansour [7] found a formula for the generating functions of powers of Horadam’s sequence. In this paper we interested in studying the generating function for squaring the terms of the ℓ-sequence, that is,

1Research financed by EC’s IHRP Programme, within the Research Training Network ”Algebraic Combinatorics in Europe”, grant HPRN-CT-2001-00272

A_{ℓ}(x) = A_{ℓ}(x; c_{0}, …, c_{ℓ−1}; p_{1}, …, p_{ℓ}) = ∑_{n≥0} a_{n}^{2}(c_{0}, …, c_{ℓ−1}; p_{1}, …, p_{ℓ})x^{n}.

The main result of this paper can be formulated as follows. Let Δ_{ℓ} = (Δ_{ℓ}(i, j))_{0≤i,j≤ℓ−1} be the ℓ × ℓ matrix

Δ_{ℓ}(i, j) = \{ \begin{matrix}1 − ∑_{s=1}^{ℓ} p_{j}^{2}x^{j}, & i = j = 0 \\ −2xv_{j}, & i = 0 and 1 ≤ j ≤ ℓ − 1 \\ −p_{i}x^{i}, & 1 ≤ i ≤ ℓ − 1 and j = 0 \\ δ_{i,j} − p_{i−j}x^{i−j} − p_{i+j}x^{i}, & 1 ≤ i ≤ ℓ − 1 and 1 ≤ j ≤ ℓ − i \\ δ_{i,j}, & 1 ≤ i ≤ ℓ − 1 and ℓ + 1 − i ≤ j ≤ ℓ − 1 \end{matrix}

where v_{j} is given by

v_{j} = p_{1}p_{j+1} + p_{2}p_{j+2}x + ⋯ + p_{ℓ−j}p_{ℓ}x^{ℓ−j−1},

for all j = 1, 2, …, ℓ − 1, we define p_{i} = 0 for i ≤ 0, and δ_{i,j} = \{ \begin{matrix}1, & if i = j \\ 0, & if i ≠ j \end{matrix} .

Let Γ_{ℓ} = (Γ_{ℓ}(i, j))_{0≤i,j≤ℓ−1} be the ℓ × ℓ matrix

Γ_{ℓ}(i, j) = \{ \begin{matrix}x ∑_{s=0}^{ℓ−1}(c_{s}^{2} − w_{s−1}^{2})x^{j}, & i = j = 0 \\ x^{i+1} ∑_{s=0}^{ℓ−1−i} c_{s}(c_{s+i} − w_{s+i−1})x^{s}, & j = 0 and 1 ≤ i ≤ ℓ − 1 \\ Δ_{ℓ}(i, j), & 0 ≤ i ≤ ℓ − 1 and 1 ≤ j ≤ ℓ − 1 \end{matrix}

where w_{j} is given by

w_{j} = p_{1}c_{j} + p_{2}c_{j−1} + ⋯ + p_{j+1}c_{0} = ∑_{s=1}^{j+1} p_{s}c_{j+1−s},

for j = 0, 1, …, ℓ − 2 with w_{−1} = 0.

Theorem 1.1 The generating function A_{ℓ}(x) is given by

\frac{det(Γ_{ℓ})}{x det(Δ_{ℓ})}.

The paper is organized as follows. In Section 2 we give the proof of Theorem 1.1 and in Section 3 we give some applications for Theorem 1.1.

2 Proofs

Let (a_{n})_{n≥0} be a sequence satisfying Relation (1) and ℓ be any positive integer. We define a family {f_{d}(n)}_{d=0}^{ℓ−1} of sequences by

f_{d}(n) = a_{n−1}a_{n−1−s},

and a family {F_{d}(x)}_{d=0}^{ℓ−1} of generating functions by

F_{d}(x) = ∑_{n≥1} a_{n−1}a_{n−1−d}x^{n}.  (2)

Now we state two relations (Lemma 2.1 and Lemma 2.2) between the generating functions F_{d}(x) and F_{0}(x) = xA_{ℓ}(x) that play the crucial roles in the proof of Theorem 1.1. Lemma 2.1 We have

F_{0}(x) = F_{0}(x) ∑_{j=1}^{ℓ} p_{j}^{2}x^{j} + 2x ∑_{j=1}^{ℓ−1} v_{j}F_{j}(x) + x ∑_{j=0}^{ℓ−1}(c_{j}^{2} − w_{j−1}^{2})x^{j}.

Proof. Since the sequence (a_{n})_{n≥0} satisfying Relation (1) we get that

a_{n}^{2} = ∑_{j=1}^{ℓ} p_{j}^{2}a_{n−j}^{2} + 2 ∑_{1≤i<j≤ℓ} p_{i}p_{j}a_{n−i}a_{n−j},

for all n ≥ ℓ. Multiplying by x^{n} and summing over n ≥ ℓ together with the following facts:

1. ∑_{n≥ℓ} a_{n}^{2}x^{n} = \frac{1}{x} ∑_{n≥ℓ} f_{0}(n + 1)x^{n+1} = \frac{1}{x} (F_{0}(x) − ∑_{j=1}^{ℓ} a_{j−1}^{2}x^{j}),

2. ∑_{n≥ℓ} a_{n−j}^{2}x^{n} = ∑_{n≥ℓ} f_{0}(n − j + 1)x^{n} = x^{j−1} (F_{0}(x) − ∑_{t=1}^{ℓ−j} a_{t−1}^{2}x^{t}),

3. ∑_{n≥ℓ} a_{n−i}a_{n−j}x^{n} = \frac{1}{x} ∑_{n≥ℓ+1} f_{j−i}(n − i)x^{n} = x^{i−1} (F_{j−i}(x) − ∑_{d=j−i+1}^{ℓ−i} a_{d−1}a_{d−j+i−1}x^{d}),

we have that

F_{0}(x) = F_{0}(x) ∑_{j=1}^{ℓ} p_{j}^{2}x^{j} + 2 ∑_{1≤i<j≤ℓ} p_{i}p_{j}x^{i}F_{j−i}(x)

+ ∑_{j=1}^{ℓ} a_{j−1}^{2}x^{j} − ∑_{j=1}^{ℓ} ∑_{i=1}^{ℓ−j} p_{j}^{2}a_{i−1}^{2}x^{j+i} − 2 ∑_{1≤i<j≤ℓ} ∑_{d=j−i+1}^{ℓ−i} p_{i}p_{j}a_{d−1}a_{d−(j−i)−1}x^{i+d}

= F_{0}(x) ∑_{j=1}^{ℓ} p_{j}^{2}x^{j} + 2x ∑_{j=1}^{ℓ−1} v_{j}F_{j}(x) + x ∑_{j=0}^{ℓ−1}(a_{j}^{2} − w_{j−1}^{2})x^{j}.

Hence,using the fact that a_{j} = c_{j} for j = 0, 1, …, ℓ − 1 we obtain the desired result. □ Lemma 2.2 For any i = 1, 2, …, ℓ − 1,

F_{i}(x) = p_{i}x^{i}F_{0}(x) + ∑_{j=1}^{ℓ−i}(p_{i−j}x^{i−j} + p_{i+j}x^{i})F_{j}(x) + x^{i+1} ∑_{j=0}^{ℓ−1−i} c_{j}(c_{i+j} − w_{i+j−1})x^{j}.

Proof. By direct calculations we have for n ≥ ℓ + 1,

f_{i}(n) = a_{n−1}a_{n−1−i} = ∑_{j=1}^{ℓ} p_{j}a_{n−1−j}a_{n−1−i};

equivalently,

\begin{matrix}f_{i}(n) \\ = p_{1}f_{i−1}(n − 1) + p_{2}f_{i−2}(n − 2) + ⋯ + p_{i}f_{0}(n − i) + p_{i+1}f_{1}(n − i) + ⋯ + p_{ℓ}f_{ℓ−i}(n − i). \end{matrix}

As in Lemma 2.1, multiplying by x^{n} and summing over n ≥ ℓ + 1 we get

\begin{matrix}F_{i}(x) − ∑_{j=i+1}^{ℓ} a_{j−1}a_{j−1−i}x^{j} = ∑_{j=1}^{i} p_{j}x^{j} (F_{i−j}(x) − ∑_{d=i−j+1}^{ℓ−j} a_{d−1}a_{d−(i−j)−1}x^{d}) \\ + ∑_{j=i+1}^{ℓ} p_{j}x^{i} (F_{j−i}(x) − ∑_{d=j−i+1}^{ℓ−i} a_{d−1}a_{d−(j−i)−1}x^{d}) \end{matrix}

The rest is easy to check from the definitions. □ Proof. (Theorem 1.1) Using the above lemmas together with the definitions we have

Δ_{k} · [F_{0}(x), F_{1}(x), F_{2}(x), …, F_{ℓ−1}(x)]T = wT,

where the vector w is given by

[ x ∑_{j=0}^{ℓ−1}(c_{j}^{2} − w_{j−1})x^{j} ; x^{2} ∑_{j=0}^{ℓ−2} c_{j}(c_{j+1} − w_{j})x^{j} ; x^{3} ∑_{j=0}^{ℓ−3} c_{j}(c_{j+2} − w_{j+1})x^{j} ; ⋮ ; x^{ℓ−1} ∑_{j=0}^{0} c_{j}(c_{j+ℓ−1} − w_{j+ℓ−2})x^{j} ] .

Hence, the solution of the above equation gives the generating function F_{0}(x) = \frac{det(Γ_{ℓ})}{det(Δ_{ℓ})}; equivalently, A_{ℓ}(x) = \frac{det(Γ_{ℓ})}{x det(Δ_{ℓ})}, as claimed in Theorem 1.1. □

3 Applications

In this section we present some applications of Theorem 1.1. Fibonacci numbers. Let F_{k,n} be the nth k-Fibonacci number which is given by

F_{k,n} = ∑_{j=1}^{k} F_{k,n−j},

for n ≥ k, with F_{k,0} = 0 and F_{k,j} = 1 for j = 1, 2, …, k − 1; in such a context, F_{2,n}, F_{3,n}, and F_{4,n} are usually called the nth Fibonacci numbers, tribonacci numbers, and tetranacci numbers; respectively. Using Theorem 1.1 with c_{0} = 0 and

c_{1} = c_{2} = ⋯ = c_{k−1} = p_{1} = p_{2} = ⋯ = p_{k} = 1

k The generating function ∑_{n≥0} F_{k,n}^{2}x^{n}
2 \frac{x(1−x)}{(1+x)(1−3x+x^{2})}
3 \frac{x(1−x−x^{2}−x^{3})}{(1+x+x^{2}−x^{3})(1−3x−x^{2}−x^{3})}
4 \frac{x(1−x−5x^{2}−2x^{3}−x^{4}−2x^{5}+3x^{7}+x^{8})}{1−2x−4x^{2}−5x^{3}−8x^{4}+4x^{5}+6x^{6}+x^{8}−x^{10}}
5 \frac{x(1−x−5x^{2}−12x^{3}−8x^{4}−10x^{5}−7x^{6}−17x^{7}−8x^{8}+13x^{9}+10x^{10}+3x^{11}+9x^{12}+4x^{13})}{1−2x−4x^{2}−7x^{3}−11x^{4}−16x^{5}+4x^{6}+7x^{7}+4x^{8}+4x^{9}+7x^{10}−x^{12}−x^{13}−x^{15}}

Table 1: The generating function for the square of the kth-Fibonacci numbers

gives the generating function ∑_{n≥0} F_{k,n}^{2}x^{n} (see Table 1).

From Table 1, for k = 3 we obtain

∑_{n≥0} nF_{3,n}^{2}x^{n} = \frac{x(1 − 2x + 2x^{2} + 12x^{3} + 8x^{5} + 2x^{6} + 4x^{7} + 3x^{8} + 2x^{9})}{(x^{3} − x^{2} − x − 1)^{2}(x^{3} + x^{2} + 3x − 1)^{2}}.

Pell numbers. Let P_{k,n} be the nth k-Pell number which is given by

P_{k,n} = 2P_{k,n−1} + ∑_{j=2}^{k} P_{k,n−j},

for n ≥ k, with P_{k,j} = 1 for j = 0, 1, …, k − 1; in such a context, P_{2,n} is usually called the nth Pell number. Using Theorem 1.1 with c_{j} = 1 for j = 0, 1, …, k − 1 and p_{j} = 1 for j = 1, 2, …, k gives the generating function ∑_{n≥0} P_{k,n}^{2}x^{n} (see Table 2).

k The generating function ∑_{n≥0} P_{k,n}^{2}x^{n}
2 \frac{1−4x−x^{2}}{(1+x)(1−6x+x^{2})}
3 \frac{1−4x−11x^{2}−13x^{3}−5x^{4}−4x^{5}}{(1−6x−3x^{2}−x^{3})(1−x+2x^{2}−x^{3})}
4 \frac{1−4x−12x^{2}−25x^{3}−29x^{4}−3x^{5}−9x^{6}−12x^{7}+13x^{8}+9x^{9}}{(1−5x−8x^{2}−13x^{3}−20x^{4}+2x^{5}+14x^{6}+x^{7}+x^{8}−x^{10})}
5 \frac{(1+x)(9x^{13}+4x^{12}+2x^{11}+13x^{10}+6x^{9}−26x^{8}−6x^{7}−2x^{6}−5x^{5}−14x^{4}−9x^{3}−3x^{2}−2x+1)}{1−2x−4x^{2}−7x^{3}−11x^{4}−16x^{5}+4x^{6}+7x^{7}+4x^{8}+4x^{9}+7x^{10}−x^{12}−x^{13}−x^{15}}

Table 2: The generating function for the square of the kth-Pell numbers

From Table 2, for k = 2 we have

∑_{n≥0} nP_{2,n}^{2}x^{n} = \frac{x(1 − 2x + 10x^{2} − 2x^{3} + x^{4})}{(x + 1)^{2}(x^{2} − 6x + 1)^{2}}.

References

[1] G.H. Hardy and E.M. Wright, An introduction to the Theory of Numbers, 4th ed. London, Oxford University Press, 1962.

[2] P. Haukkanen, A note on Horadam’s sequence, The Fibonacci Quarterly 40:4 (2002) 358–361.

[3] P. Haukkanen and J. Rutkowski, On generating functions for powers of recurrence sequences, The Fibonacii Quarterly 29:4 (1991) 329–332.

[4] A.F Horadam, Basic properties of a certain generalized sequence of numbers, The Fibonacci Quarterly 3 (1965) 161–176.

[5] A.F Horadam, Generating functions for powers of a certain generalized sequence of numbers, Duke Math. J. 32 (1965) 437–446.

[6] A.F. Horadam and J.M. Mahon, Pell and Pell-Lucas Polynomials, The Fibonacci Quarterly 23:1 (1985) 7–20.

[7] T. Mansour, A formula for the generating functions of powers of Horadam’s sequence, Australasian Journal of Combinatorics, to appear (2003), preprint math.CO/0302015.

[8] J. Riordan, Generating function for powers of Fibonacci numbers, Duke Math.J. 29 (1962) 5–12.

2000 Mathematics Subject Classification: Primary 11B39; Secondary 05A15