Two proofs of Filipponi’s formula for Lucas numbers of odd index

Alois Panholzer and Helmut Prodinger Department for Algebra and Discrete Mathematics TU Wien Wiedner Hauptstrasse 8–10/118 A-1040 Wien Austria email: alois.panholzer+e1182@tuwien.ac.at, Helmut.Prodinger@tuwien.ac.at May 19, 1998

In the recent paper [1], Filipponi presented the following formula without proof:

L_{2n+1} = ∑_{0≤j≤ \frac{n}{2}}(−1)^{j}\binom{n − 1 − j}{j}3^{n−1−2j} \frac{4n − 5j}{n − 2j} .

In this form, the term j = \frac{n}{2} for even n has to be interpreted as a limit. However, we can avoid this trouble when we use the standard forms

G_{n}(w) = ∑_{0≤k≤n} \binom{n − k}{k}w^{k}.

They are studied very well in [2], and we have for n ≥ 0

∑_{0≤j≤ \frac{n}{2}}(−1)^{j}\binom{n − 1 − j}{j}3^{n−1−2j} \frac{4n − 5j}{n − 2j} = 3^{n}G_{n}(−\frac{1}{9}) + 3^{n−1}G_{n−1}(−\frac{1}{9}).

In exercise 7.34 of [2] we find also the generating function

G(z, w) = ∑_{n≥0} G_{n}(w)z^{n} = \frac{1}{1 − z − wz^{2}} .

Hence

∑_{n≥0}(3^{n}G_{n}(−\frac{1}{9}) + 3^{n−1}G_{n−1}(−\frac{1}{9}))z^{n}

= ∑_{n≥0} G_{n}(−\frac{1}{9})(3z)^{n} + z ∑_{n≥0} G_{n}(−\frac{1}{9})(3z)^{n}

= \frac{1 + z}{1 − 3z + z^{2}} .

Since a trivial computation gives

∑_{n≥0} L_{2n+1}z^{n} = \frac{1 + z}{1 − 3z + z^{2}} ,

the proof is finished.

We can even get a general formula for L_{sn+t} with nonnegative integers 0 ≤ t < s; for that, we set up generating functions:

F_{s,t}(z) = ∑_{n≥0} F_{sn+t}z^{n} = α^{t} ∑_{n≥0} (α^{s}z)^{n} + β^{t} ∑_{n≥0} (β^{s}z)^{n} = α^{t} \frac{1}{1 − α^{s}z} + β^{t} \frac{1}{1 − β^{s}z}

= \frac{α^{t} (1 − β^{s}z) + β^{t} (1 − α^{s}z)}{(1 − α^{s}z) (1 − β^{s}z)} = \frac{α^{t} + β^{t} − ((−1)^{t}α^{s−t} + (−1)^{t}β^{s−t}) z}{1 − (α^{s} + β^{s}) z + (−1)^{s} z}

= \frac{L_{t} − (−1)^{t}L_{s−t}z}{1 − L_{s}z + (−1)^{s} z^{2}} .

With the above defined function G(z, w) this can be written as

F_{s,t}(z) = (L_{t} − (−1)^{t}L_{s−t})G(L_{s}z, \frac{(−1)^{s−1}}{L_{s}^{2}} )

and therefore we get the formula

\begin{aligned}L_{sn+t} & = L_{t} ∑_{0≤k≤n} \binom{n − k}{k}(−1)^{(s−1)k}L_{s}^{n−2k} \\ & − (−1)^{t}L_{s−t} ∑_{0≤k≤n−1} \binom{n − 1 − k}{k}(−1)^{(s−1)k}L_{s}^{n−1−2k}. \end{aligned}

We don’t know whether this formula is new, but it is easy to prove and generates infinitely many “Filipponi formulæ.”

For the second (mechanical) proof, (“Zeilberger’s algorithm”) we note the following (see [3] and [2] for the underlying theory): Set f(n, k) := (−1)^{k}\binom{n−1−k}{k}3^{n−1−2k} \frac{4n−5k}{n−2k} and F (n) := ∑_{k} f(n, k). Furthermore, set

g(n, k) := −\frac{9k(n − k)(4n − 5k + 5)}{(n − 2k + 2)(n − 2k + 1)(4n − 5k)}f(n, k),

then

f(n + 2, k) − 3f(n + 1, k) + f(n, k) = g(n, k + 1) − g(n, k)

(check!!), thus we get, on summing over k, F (n + 2) − 3F (n + 1) + F (n) = 0. Since the odd Lucas numbers also satisfy the recursion L_{2n+5} − 3L_{2n+3} + L_{2n+1} = 0 and two initial values match as well, the proof is finished.

References

[1] P. Filipponi. Combinatorial expressions for Lucas numbers. The Fibonacci Quarterly, 36:63–65, 1998.

[2] R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics (Second Edition). Addison Wesley, 1994.

[3] M. Petkovšek, H. Wilf, and D. Zeilberger. A = B. A.K. Peters, Ltd., 1996.

AMS Classification Numbers: 05A19, 11B39