A formula for the generating functions of powers of

Horadam’s sequence

March 7, 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

The second-order linear recurrence sequence (w_{n}(a, b; p, q))_{n≥0}, or briefly (w_{n})_{n≥0}, is defined by

w_{n+2} = pw_{n+1} + qw_{n},  (1)

with given w_{0} = a, w_{1} = b and n ≥ 0. This sequence was introduced, in 1965, by Horadam [3, 4], and it generalizes many sequences (see [1, 5]). Examples of such sequences are Fibonacci numbers sequence (F_{n})_{n≥0}, Lucas numbers sequence (L_{n})_{n≥0}, and Pell numbers sequence (P_{n})_{n≥0}, when one has p = q = b = 1, a = 0; p = q = b = 1, a = 2; and p = 2, q = b = 1, a = 0; respectively. In this paper we interested in studying the generating function for powers of Horadam’s sequence, that is, H_{k}(x; a, b, p, q) = H_{k}(x) = ∑_{n≥0} w_{n}^{k}x^{n}. In 1962, Riordan [7] 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

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

(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 [4] gave a recurrence relation for H_{k}(x) (see also [6]). Recently, Haukkanen [2] studied linear combinations of Horadam’s sequences and the generating function of the ordinary product of two of Horadam’s sequences. The main result of this paper can be formulated as follows. Let Δ_{k} = (Δ_{k}(i, j))_{1≤i,j≤k} = Δ_{k}(p, q) be the k × k matrix

( \begin{matrix}1 − p^{k}x − q^{k}x^{2} & −xp^{k−1}q^{1}\binom{k}{1} & −xp^{k−2}q^{2}\binom{k}{2} & ⋯ & −xp^{2}q^{k−2}\binom{k}{k−2} & −xpq^{k−1}\binom{k}{k−1} \\ −p^{k−1}x & 1 − xp^{k−2}q^{1}\binom{k−1}{1} & −xp^{k−3}q^{2}\binom{k−1}{2} & ⋯ & −xpq^{k−2}\binom{k−1}{k−2} & −xq^{k−1}\binom{k−1}{k−1} \\ −p^{k−2}x & −xp^{k−3}q^{1}\binom{k−2}{1} & 1 − xp^{k−4}q^{2}\binom{k−2}{2} & ⋯ & −xq^{k−2}\binom{k−2}{k−2} & 0 \\ −p^{k−3}x & −xp^{k−4}q^{1}\binom{k−3}{1} & −xp^{k−5}q^{2}\binom{k−3}{2} & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & & ⋮ & ⋮ \\ −p^{2}x & −xpq^{1}\binom{2}{1} & −xq^{2}\binom{2}{2} & ⋯ & 1 & 0 \\ −p^{1}x & −xq^{1}\binom{1}{1} & 0 & ⋯ & 0 & 1 \end{matrix} ) ,

and let δ_{k} = δ_{k}(p, q, a, b) be the k × k matrix

( \begin{matrix}a^{k} + g_{k}x & −xp^{k−1}q^{1}\binom{k}{1} & −xp^{k−2}q^{2}\binom{k}{2} & ⋯ & −xp^{2}q^{k−2}\binom{k}{k−2} & −xpq^{k−1}\binom{k}{k−1} \\ g_{k−1}x & 1 − xp^{k−2}q^{1}\binom{k−1}{1} & −xp^{k−3}q^{2}\binom{k−1}{2} & ⋯ & −xpq^{k−2}\binom{k−1}{k−2} & −xq^{k−1}\binom{k−1}{k−1} \\ g_{k−2}x & −xp^{k−3}q^{1}\binom{k−2}{1} & 1 − xp^{k−4}q^{2}\binom{k−2}{2} & ⋯ & −xq^{k−2}\binom{k−2}{k−2} & 0 \\ g_{k−3}x & −xp^{k−4}q^{1}\binom{k−3}{1} & −xp^{k−5}q^{2}\binom{k−3}{2} & ⋯ & 0 & 0 \\ ⋮ & ⋮ & ⋮ & & ⋮ & ⋮ \\ g_{2}x & −xpq^{1}\binom{2}{1} & −xq^{2}\binom{2}{2} & ⋯ & 1 & 0 \\ g_{1}x & −xq^{1}\binom{1}{1} & 0 & ⋯ & 0 & 1 \end{matrix} ) ,

where g_{j} = (b^{j} − a^{j}p^{j})a^{k−j} for all j = 1, 2, …, k.

Theorem 1.1 The generating function H_{k}(x) is given by \frac{det(δ_{k})}{det(Δ_{k})}.

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 (w_{n})_{n≥0} be a sequence satisfying Relation (1) and k be any positive integer. We define a family {A_{k,d}}_{d=1}^{k} of generating functions by

A_{k,d}(x) = ∑_{n≥0} w_{n}^{k−d}w_{n+1}^{d}x^{n+1}.  (2)

Now we introduce two relations (Lemma 2.1 and Lemma 2.2) between the generating functions A_{k,d}(x) and H_{k}(x) that play the crucial roles in the proof of Theorem 1.1.

Lemma 2.1 For any k ≥ 1,

(1 − p^{k}x − q^{k}x^{2})H_{k}(x) − x ∑_{j=1}^{k−1} \binom{k}{j}p^{k−j}q^{j}A_{k,k−j}(x) = a^{k} + x(b^{k} − a^{k}p^{k}).

Proof. Using the binomial theorem we get

w_{n+2}^{k} = (pw_{n+1} + qw_{n})^{k} = p^{k}w_{n+1}^{k} + ∑_{j=1}^{k−1} \binom{k}{j}p^{k−j}q^{j}w_{n+1}^{k−j}w_{n}^{j} + q^{k}w_{n}^{k}.

Multiplying by x^{n+2} and summing over all n ≥ 0 with using Definition (2) we have

H_{k}(x) − b^{k}x − a^{k} = p^{k}x(H_{k}(x) − a^{k}) + x ∑_{j=1}^{k−1} \binom{k}{j}p^{k−j}q^{j}A_{k,k−j}(x) + q^{k}x^{2}H_{k}(x),

as requested. □ Lemma 2.2 For any k − 1 ≥ d ≥ 1,

A_{k,d}(x) − a^{k−d}b^{d}x = p^{d}x(H_{k}(x) − a^{k}) + x ∑_{j=1}^{d} \binom{d}{j}p^{d−j}q^{j}A_{k,k−j}(x).

Proof. Using the binomial theorem we have

w_{n}^{k−d}w_{n+1}^{d} = w_{n}^{k−d}(pw_{n} + qw_{n−1})^{d} = w_{n}^{k−d} ∑_{j=0}^{d} \binom{d}{j}p^{d−j}q^{j}w_{n}^{d−j}w_{n−1}^{j}.

Multiplying by x^{n+1} and summing over all n ≥ 1 we get

A_{k,d}(x) − a^{k−d}b^{d}x = p^{d}x(H_{k}(x) − a^{k}) + x ∑_{j=1}^{d} \binom{d}{j}p^{d−j}q^{j}A_{k,k−j}(x),

as requested □ Proof. (Theorem 1.1) By using the above lemmas together with definitions we get

Δ_{k} · [H_{k}(x), A_{k,k−1}(x), A_{k,k−2}(x), …, A_{k,1}(x)]T = v_{k},

where v_{k} is given by [a^{k} + x(b^{k} − a^{k}p^{k}), (a^{1}b^{k−1} − p^{k−1}a^{k})x, (a^{2}b^{k−2} − p^{k−2}a^{k})x, …, (a^{k−1}b^{1} − p^{1}xa^{k})x]T . Hence, the solution of the above equation gives the generating function H_{k}(x) = \frac{det(δ_{k})}{det(Δ_{k})}, as claimed in Theorem 1.1. □

3 Applications

In this section we present some applications for Theorem 1.1. Fibonacci numbers. If a = 0 and p = q = b = 1, then Theorem 1.1 for k = 1, 2, 3, 4, 5, 6 yields Table 1.

k The generating function H_{k}(x; 0, 1, 1, 1)
1 \frac{x}{1−x−x^{2}}
2 \frac{x(1−x)}{(1+x)(1−3x+x^{2})}
3 \frac{x(1−2x−x^{2})}{(1+x−x^{2})(1−4x−x^{2})}
4 \frac{x(1+x)(1−5x+x^{2})}{(1−x)(1+3x+x^{2})(1−7x+x^{2})}
5 \frac{x(1−7x−16x^{2}+7x^{3}+x^{4})}{(1−x−x^{2})(1+4x−x^{2})(1−11x−x^{2})}
6 \frac{x(1−x)(1−11x−64x^{2}−11x^{3}+x^{4})}{(1+x)(1−3x+x^{2})(1+7x+x^{2})(1−18x+x^{2})}

Table 1. The generating function for the powers of Fibonacci numbers Lucas numbers. If a = 2 and p = q = b = 1, then Theorem 1.1 for k = 1, 2, 3, 4, 5, 6 yields Table 2.

k The generating function H_{k}(x; 2, 1, 1, 1)
1 \frac{2−x}{1−x−x^{2}}
2 \frac{4−7x−x^{2}}{(1+x)(1−3x+x^{2})}
3 \frac{8−13x−24x^{2}+x^{3}}{(1+x−x^{2})(1−4x−x^{2})}
4 \frac{16−79x−164x^{2}+76x^{3}+x^{4}}{(1−x)(1+3x+x^{2})(1−7x+x^{2})}
5 \frac{32−255x−1045x^{2}+960x^{3}+235x^{4}−x^{5}}{(1−x−x^{2})(1+4x−x^{2})(1−11x−x^{2})}
6 \frac{64−831x−5940x^{2}+11155x^{3}+5485x^{4}−716x^{5}−x^{6}}{(1+x)(1−3x+x^{2})(1+7x+x^{2})(1−18x+x^{2})}

Table 2. The generating function for the powers of Lucas numbers

Pell numbers. If a = 0, b = q = 1 and p = 2, then Theorem 1.1 for k = 1, 2, 3, 4, 5, 6 yields Table 3.

k The generating function H_{k}(x; 0, 1, 2, 1)
1 \frac{x}{1−2x−x^{2}}
2 \frac{x(1−x)}{(1+x)(1−6x+x^{2})}
3 \frac{x(1−4x−x^{2})}{(1+2x−x^{2})(1−14x−x^{2})}
4 \frac{x(1+x)(1−14x+x^{2})}{(1−x)(1+6x+x^{2})(1−34x−x^{2})}
5 \frac{x(1−38x−130x^{2}+38x^{3}+x^{4})}{(1−2x−x^{2})(1−82x−x^{2})(1+14x−x^{2})}
6 \frac{x(1−x)(1−104x−1210x^{2}−104x^{3}+x^{4})}{(1+x)(1+34x+x^{2})(1−6x+x^{2})(1−198x+x^{2})}

Table 3. The generating function for the powers of Pell numbers

Chebyshev polynomials of the second kind. If a = 1, b = p = 2t and q = −1, then Theorem 1.1 for k = 1, 2, 3, 4, 5, 6 yields Table 4. More generally, if applying Theorem 1.1 for k = 1, 2, 3, 4, then we get the following corollary.

Corollary 3.1 Let k = 1, 2, 3, 4. Then the generating function H_{k}(x) is given by \frac{A_{k}(x)}{B_{k}(x)} where

k The generating function H_{k}(x; 1, 2t, 2t, −1)
1 \frac{1}{1−2tx+x^{2}}
2 \frac{1+x}{(1−x)((1+x)^{2}−4xt^{2})}
3 \frac{1+4tx+x^{2}}{(1−2tx+x^{2})(1+2t(3−4t^{2})x+x^{2})}
4 \frac{(1+x)((1−x)^{2}+12t^{2}x)}{(1−x)((1+x)^{2}−4t^{2}x)(16t^{2}(1−t^{2})x+(1−x)^{2}))}
5 \frac{1−6tx+2x^{2}+32t^{3}x+96t^{4}x^{2}+32t^{3}x^{3}−32t^{2}x^{2}−6x^{3}t+x^{4}}{(1+2t(3−4t^{2})x+x^{2})(1−2tx+x^{2})(1−8t^{3}(4t^{2}−5)x−10tx+x^{2})}
6 \frac{(1+x)(x^{4}+80t^{4}x^{3}−24x^{3}t^{2}−2x^{2}−480t^{4}x^{2}+640t^{6}x^{2}+88t^{2}x^{2}+80t^{4}x−24t^{2}x+1)}{(1−x)((1+x)^{2}−4t^{2}x)((1−x)^{2}+16t^{2}(1−t^{2})x)((1+x)^{2}−4t^{2}(4t^{2}−3)^{2}x)}

Table 4. The generating function for the powers of Chebyshev polynomials of the second kind

A_{1}(x) = a + x(b − ap), A_{2}(x) = (a^{2} + xb^{2})(xq − 1)a^{2} + a^{2}p^{2}x(xq + 1) − 2x^{2}pqab, A_{3}(x) = (a^{3} + b^{3}x − a^{3}p^{3}x)(1 − q^{3}x^{2}) − 2xpq(a^{3} + b^{3}x) − x^{2}a^{3}p^{4}q + 3ab^{2}x^{2}p^{2}q

+3ab^{2}x^{3}pq^{3} − 3a^{2}bx^{3}p^{2}q^{3} + 3a^{2}bx^{2}pq^{2} − 3p^{2}x^{2}a^{3}q^{2}, A_{4}(x) = a^{4} + (b^{4} − a^{4}(p^{4} + 3p^{2}q + q^{2}))x − q(5qa^{4}p^{4} + b^{4}q + a^{4}q^{3} + a^{4}p^{6} + 7q^{2}a^{4}p^{2}

−6qb^{2}a^{2}p^{2} − 4b^{3}ap^{3} − 4q^{2}ba^{3}p + 3b^{4}p^{2})x^{2} + q^{3}(−8qba^{3}p^{3} − 3b^{4}p^{2} + a^{4}q^{3}

+5qa^{4}p^{4} − 6b^{2}a^{2}p^{4} − b^{4}q + a^{4}p^{6} − 4q^{2}ba^{3}p + 8b^{3}ap^{3} + 4q^{2}a^{4}p^{2} + 4qb^{3}ap)x^{3}
+q^{6}(ap − b)^{4}x^{4}

and

B_{1}(x) = 1 − px − x^{2}q,
B_{2}(x) = (1 + xq)(p^{2}x − (xq − 1)^{2}),
B_{3}(x) = (1 + pqx − q^{3}x^{2})(1 − 3pqx − p^{3}x − q^{3}x^{2}),
B_{4}(x) = (1 − q^{2}x)((1 + q^{2}x)^{2} + p^{2}qx)((1 − q^{2}x)^{2} − p^{2}x(p^{2} + 4q)).

Acknowledgments. The final version of this paper was written while the author was visiting University of Haifa, Israel in January 2003. He thanks the HIACS Research Center and the Caesarea Edmond Benjamin de Rothschild Foundation Institute for Interdisciplinary Applications of Computer Science for financial support, and professor Alek Vainshtein for his generosity. Finally, the author is grateful to the referees for the careful reading of the manuscript.

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] A.F Horadam, Basic properties of a certain generalized sequence of numbers, The Fibonacci Quarterly 3 (1965) 161–176.

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

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

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

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

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