On the Expansion of Fibonacci and Lucas Polynomials

Helmut Prodinger Department of Mathematics University of Stellenbosch 7602 Stellenbosch South Africa

                      hproding@sun.ac.za

Abstract Recently, Belbachir and Bencherif have expanded Fibonacci and Lucas polynomials using bases of Fibonacci- and Lucas-like polynomials. Here, we provide simplified proofs for the expansion formulæthat in essence a computer can do. Furthermore, for 2 of the 5 instances, we find q-analogues.

1 Introduction

In [2], Belbachir and Bencherif studied the Fibonacci and Lucas polynomials:

U_{0} = 0, U_{1} = 1, U_{n} = xU_{n−1} + yU_{n−2},
V_{0} = 2, V_{1} = x, V_{n} = xV_{n−1} + yV_{n−2}.

We prefer the modified polynomials

u_{0} = 0, u_{1} = 1, u_{n} = u_{n−1} + zu_{n−2},
v_{0} = 2, v_{1} = 1, v_{n} = v_{n−1} + zv_{n−2},

so that

U_{n}(x, y) = x^{n−1}u_{n}(\frac{y}{x^{2}} ), V_{n}(x, y) = x^{n}v_{n}(\frac{y}{x^{2}} ).

Then, with

λ_{1,2} = \frac{1 ± \sqrt{1 + 4z}}{2} ,

u_{n} = \frac{1}{\sqrt{1 + 4z}} (λ_{1}^{n} − λ_{2}^{n}), v_{n} = λ_{1}^{n} + λ_{2}^{n}.

Substituting z = t/(1 − t)^{2}, these formulæ become particularly nice:

u_{n} = \frac{1 − (−t)^{n}}{(1 + t)(1 − t)^{n−1}} , v_{n} = \frac{1 + (−t)^{n}}{(1 − t)^{n}} .

The main result of [2] are the following 5 formulæ:

2u_{2n+1} = ∑_{k=0}^{n} a_{n,k}v_{2n−k},  a_{n,k} = 2 ∑_{j=0}^{n}(−1)^{j+k}\binom{j}{k} − (−1)^{n+k}\binom{n}{k}.  (1)

u_{2n} = ∑_{k=1}^{n} b_{n,k}u_{2n−k},  b_{n,k} = (−1)^{k+1}\binom{n}{k}.  (2)

v_{2n−1} = ∑_{k=1}^{n} c_{n,k}u_{2n−k},  c_{n,k} = 2(−1)^{k+1}\binom{n}{k} − [k = 1].  (3)

2v_{2n−1} = ∑_{k=1}^{n} d_{n,k}v_{2n−1−k},  d_{n,k} = (−1)^{k+1} \frac{2n − k}{n} \binom{n}{k}.  (4)

2u_{2n} = ∑_{k=1}^{n} e_{n,k}v_{2n−1−k},  (5)

e_{n,k} = (−1)^{k+1} \frac{2n − k}{2n} \binom{n}{k} + ∑_{j=0}^{n−1}(−1)^{j+k−1}\binom{j}{k − 1} − \frac{1}{2}(−1)^{n+k}\binom{n − 1}{k − 1}.

But the proofs of all these, using the simple forms for u_{n} and v_{n}, can be done by a computer! To give the reader an idea, let us do the last one, which seems to be the most complicated:

∑_{k=1}^{n} e_{n,k}v_{2n−1−k} = ∑_{k=1}^{n}(−1)^{k+1} \frac{2n − k}{2n} \binom{n}{k}v_{2n−1−k}

+ ∑_{j=0}^{n−1} ∑_{k=1}^{j+1}(−1)^{j+k−1}\binom{j}{k − 1}v_{2n−1−k} − ∑_{k=1}^{n} \frac{1}{2}(−1)^{n+k}\binom{n − 1}{k − 1}v_{2n−1−k}

= \frac{1 − t^{2n−1}}{(1 − t)^{2n−1}} + \frac{1 + t^{2n−1}}{(1 − t)^{2n−2}(1 + t)} − \frac{(−1)^{n}t^{n−1}}{(1 − t)^{2n−2}} + \frac{(−1)^{n}t^{n−1}}{(1 − t)^{2n−2}}

= \frac{2(1 − t^{2n})}{(1 − t)^{2n−1}(1 + t)} = 2u_{2n}.

The other proofs are similar/easier:

∑_{k=0}^{n} a_{n,k}v_{2n−k} = \frac{2[(−t)^{n}(1 + t) + 1 + t^{2n+1}]}{(1 − t)^{2n}(1 + t)} − \frac{2(−t)^{n}}{(1 − t)^{2n}}

= \frac{2[1 + t^{2n+1}]}{(1 − t)^{2n}(1 + t)} = 2u_{2n+1}.

∑_{k=1}^{n} c_{n,k}u_{2n−k} = \frac{2(1 − t^{2n})}{(1 − t)^{2n−1}(1 + t)} − \frac{1 + t^{2n−1}}{(1 + t)(1 − t)^{2n−2}}

= \frac{1 − t^{2n−1}}{(1 − t)^{2n−1}} = v_{2n−1}.

Remark 1. The polynomials u_{n}(x) and v_{n}(x) are essentially Chebyshev polynomials. The authors of [2] have also published a companion paper [3]; according to a remark in [2], the results in [2] are more general than the ones in [3].

2 q-analogues

Now we are interested in q-analogues. For this, we replace u_{n} by

Fib_{n} = ∑_{0≤k≤ \frac{n−1}{2}} q^{\binom{k+1}{2}}\left[{n − k − 1 \atop k}\right]_{q}z^{k}

and v_{n} by

Luc_{n} = ∑_{0≤k≤ \frac{n}{2}} q^{\binom{k}{2}}\left[{n − k \atop k}\right]_{q} \frac{[n]_{q}}{[n − k]_{q}} z^{k},

as suggested by Cigler [4]. We use standard q-notation here:

[n]_{q} := 1 + q + ⋯ + q^{n−1}, [n]_{q}! := [1]_{q}[2]_{q} … [n]_{q}, \left[{n \atop k}\right]_{q} := \frac{[n]_{q}!}{[k]_{q}![n − k]_{q}!},

compare [1]; the notions of the Introduction are the special instance q = 1.

Theorem 2.

Luc_{2n−1} = ∑_{k=1}^{n} d_{n,k}Luc_{2n−1−k},

with

d_{n,k} = (−1)^{k−1} \frac{q^{\binom{k}{2}}}{1 + q^{n−1}} (\left[{n − 1 \atop k}\right]_{q} + q^{n−1}\left[{n \atop k}\right]_{q}).

Proof. We must prove that

∑_{0≤k≤n−1} q^{\binom{k}{2}}\left[{2n − 1 − k \atop k}\right]_{q} \frac{[2n − 1]_{q}}{[2n − 1 − k]_{q}} z^{k}

= ∑_{j=1}^{n}(−1)^{j−1} \frac{q^{\binom{j}{2}}}{1 + q^{n−1}} (\left[{n − 1 \atop j}\right]_{q} + q^{n−1}\left[{n \atop j}\right]_{q})

× ∑_{0≤k≤ \frac{2n−j−1}{2}} q^{\binom{k}{2}}\left[{2n − j − 1 − k \atop k}\right]_{q} \frac{[2n − j − 1]_{q}}{[2n − j − 1 − k]_{q}} z^{k}.

Comparing coefficients, we have to prove that

q^{\binom{k}{2}}\left[{2n − 1 − k \atop k}\right]_{q} \frac{[2n − 1]_{q}}{[2n − 1 − k]_{q}}

= ∑_{j=1}^{n}(−1)^{j−1} \frac{q^{\binom{j}{2}}}{1 + q^{n−1}} (\left[{n − 1 \atop j}\right]_{q} + q^{n−1}\left[{n \atop j}\right]_{q})q^{\binom{k}{2}}\left[{2n − j − 1 − k \atop k}\right]_{q} \frac{[2n − j − 1]_{q}}{[2n − j − 1 − k]_{q}} .

Simplifying, we must prove that

∑_{j=0}^{n}(−1)^{j}q^{\binom{j}{2}}(\left[{n − 1 \atop j}\right]_{q} + q^{n−1}\left[{n \atop j}\right]_{q})\left[{2n − j − 2 − k \atop k − 1}\right]_{q}[2n − j − 1]_{q} = 0.

Another form of this is

∑_{j=0}^{n}(−1)^{j}q^{\binom{j}{2}}(1 − q^{2n−1} − q^{n−j} + q^{n−1})(1 − q^{2n−j−1})\left[{n \atop j}\right]_{q}\left[{2n − j − 2 − k \atop k − 1}\right]_{q} = 0.

Notice that

∑_{j=0}^{n}(−1)^{j}q^{\binom{j}{2}}\left[{n \atop j}\right]_{q}q^{−aj} = 0

for 0 ≤ a ≤ n − 1. This follows from Rothe’s formula [1, p. 490]

∑_{j=0}^{n}(−1)^{j}q^{\binom{j}{2}}\left[{n \atop j}\right]_{q}x^{j} = (1 − x)(1 − xq) … (1 − q^{n−1}).

We write the desired identity as

∑_{j=0}^{n}(−1)^{j}q^{\binom{j}{2}}(A + Bq^{−j} + Cq^{−2j})\left[{n \atop j}\right]_{q}(D_{0}q^{−0} + ⋯ + D_{k−1}q^{−j(k−1)}) = 0.

Therefore, for k ≤ n − 2, the identity holds. For k = n − 1,

∑_{j=0}^{1}(−1)^{j}q^{\binom{j}{2}}(1 − q^{2n−1} − q^{n−j} + q^{n−1})(1 − q^{2n−j−1})\left[{n \atop j}\right]_{q}\left[{n − j − 1 \atop n − 2}\right]_{q} = 0

can be shown by inspection, and for k = n, the identity holds, since the sum is empty. Theorem 3.

Fib_{2n} = ∑_{k=1}^{n} b_{n,k}Fib_{2n−k}

with

b_{n,k} = (−1)^{k−1}q^{\binom{k}{2}}\left[{n \atop k}\right]_{q}.

Proof. We must prove that

∑_{0≤k≤n−1} q^{\binom{k+1}{2}}\left[{2n − k − 1 \atop k}\right]_{q}z^{k}

= ∑_{j=1}^{n}(−1)^{j−1}q^{\binom{j}{2}}\left[{n \atop j}\right]_{q} ∑_{0≤k≤ \frac{2n−j−1}{2}} q^{\binom{k+1}{2}}\left[{2n − j − k − 1 \atop k}\right]_{q}z^{k}.

Comparing coefficients, this means

∑_{j=0}^{n}(−1)^{j}q^{\binom{j}{2}}\left[{n \atop j}\right]_{q}\left[{2n − j − k − 1 \atop k}\right]_{q} = 0,

which follows by a similar but simpler argument than before.

3 Conclusion

We found 2 q-analogues; for the remaining 3 instances we were not successful and leave this as a challenge for anybody who is interested.

References

[1] G. E. Andrews, R. Askey and R. Roy, Special Functions, Cambridge University Press, 2000.

[2] H. Belbachir and F. Bencherif, On some properties of bivariate Fibonacci and Lucas polynomials, J. Integer Sequences 11 (2008), Article 08.2.6.

[3] H. Belbachir and F. Bencherif, On some properties of Chebyshev polynomials, Discuss. Math. Gen. Algebra Appl. 28 (2008), 121–133.

[4] J. Cigler, A new class of q-Fibonacci polynomials, Electronic J. Combinatorics 10 (2003), Article R19. Text available at

    http://www.combinatorics.org/Volume 10/Abstracts/v10i1r19.html.

2000 Mathematics Subject Classification: Primary 11B39; Secondary 11B37. Keywords: Fibonacci polynomials, Lucas polynomials, generating functions, q-analogues.

(Concerned with sequences \underline{A007318}, \underline{A029653} and \underline{A112468}.)

Received October 6 2008; revised version received December 15 2008. Published in Journal of Integer Sequences, December 17 2008.

Return to Journal of Integer Sequences home page.