SOME POLYNOMIALS RELATED TO

THE FIBONACCI POLYNOMIALS

Helmut Prodinger

Department of Algebra and Discrete Mathematics Technical University of Vienna, Austria

In my old paper [3], while analyzing an algorithm to construct “Fibonacci partitions of a set”, I used the following formula, which is the consequence of an appropriate combinatorial decomposition that will not be repeated here;

x^{n} = ∑_{1≤k<n} \binom{n − 1 − k}{k − 1}x^{k}(x − 1)^{n−2k} + ∑_{0≤k<n} \binom{n − 1 − k}{k}x^{k+1}(x − 1)^{n−1−2k}.

The polynomials involved are closely related to the Fibonacci polynomials

\begin{aligned}u_{n}(z) & = ∑_{0≤k≤n} \binom{n − k}{k}z^{k} \\ & = \frac{1}{\sqrt{1 + 4z}} [(\frac{1 + \sqrt{1 + 4z}}{2} )^{n+1} − (\frac{1 − \sqrt{1 + 4z}}{2} )^{n+1}] . \end{aligned}

Observe that u_{n}(1) is a Fibonacci number.

Set z = x/(1 − x)^{2}, then the formula from above may be rewritten as

x^{n} = x(x − 1)^{n−2}u_{n−2}(z) + x(x − 1)^{n−1}u_{n−1}(z).

To get some expectations and variances, I had to compute

∑_{1≤k<n}(k)_{s}\binom{n − 1 − k}{k − 1}x^{k}(x − 1)^{n−2k} + ∑_{0≤k<n}(k)_{s}\binom{n − 1 − k}{k}x^{k+1}(x − 1)^{n−1−2k}

for s = 1 and s = 2.

I observed that I could get these values by appropriate differentiation(s) of the explicit form of the Fibonacci polynomials:

(x − 1)^{n}z^{s}(\frac{d}{dz} )^{s}zu_{n−2}(z) + x(x − 1)^{n−1}z^{s}(\frac{d}{dz} )^{s}u_{n−1}(z).

Performing these computations by hand I finally got

∑_{1≤k≤n−1}(−1)^{n+1−k}kx^{k} for s = 1

and

∑_{2≤k≤n−2}(−1)^{n−k}(n − 1 − k)k(k − 1)x^{k} for s = 2.

I realized that the computations for higher values of s would be quite messy. While experimenting these days with Maple, I thought again about the old polynomials and conjectured the general formula (for s ≥ 1):

∑_{1≤k<n} \binom{k}{s}\binom{n − 1 − k}{k − 1}x^{k}(x − 1)^{n−2k}

+ ∑_{0≤k<n} \binom{k}{s}\binom{n − 1 − k}{k}x^{k+1}(x − 1)^{n−1−2k}

= ∑_{0≤k<n}(−1)^{s+n−k}\binom{n − 1 − k}{s − 1}\binom{k}{s}x^{k}.

In terms of the coefficient of x^{m} (0 < m < n) this means

∑_{1≤k<n}(−1)^{k}\binom{k}{s}\binom{n − 1 − k}{k − 1}\binom{n − 2k}{m − k}

+ ∑_{0≤k<n}(−1)^{k}\binom{k}{s}\binom{n − 1 − k}{k}\binom{n − 1 − 2k}{m − 1 − k}

= \binom{n − 1 − m}{s − 1}\binom{m}{s}(−1)^{s}.

Then I thought about how to prove this and finally found the following quite elementary computation that I am going to present now.

Since s ≥ 1, we can assume the same range 1 ≤ k < n in both sums. The kth term is then

(−1)^{k}\binom{k}{s}\binom{n − 1 − k}{k − 1}\binom{n − 2k}{m − k} + (−1)^{k}\binom{k}{s}\binom{n − 1 − k}{k}\binom{n − 1 − 2k}{m − 1 − k}

= (−1)^{k}\binom{k}{s}\binom{n − 1 − k}{m − 1}\binom{m − 1}{k − 1} + (−1)^{k}\binom{k}{s}\binom{n − 1 − k}{m − 1}\binom{m − 1}{k}

= (−1)^{k}\binom{k}{s}\binom{n − 1 − k}{m − 1}\binom{m}{k}

= (−1)^{k}\binom{m}{s}\binom{m − s}{k − s}\binom{n − 1 − k}{m − 1}.

The sum on k of this expression can be simplified due the equation (5.25) in [1] that I repeat now for convenience:

∑_{k≤l} \binom{l − k}{m}\binom{s}{k − n}(−1)^{k} = (−1)^{l+m}\binom{s − m − 1}{l − m − n}, integers l, m, n ≥ 0.

Polynomials related to the Fibonacci polynomials 3

It is a disguised form of the Vandermonde convolution.

Therefore

∑_{k}(−1)^{k}\binom{m}{s}\binom{m − s}{k − s}\binom{n − 1 − k}{m − 1}

= \binom{m}{s}(−1)^{n+m}\binom{−s}{n − m − s}

= \binom{m}{s}(−1)^{s}\binom{n − m − 1}{s − 1},

and the proof is finished.

What can we learn from it? Computer experiments can be useful; they lead you to conjecture the result. And sometimes an elementary computation does a better job than a more sophisticated one.

References

1. R.L. Graham, D.E. Knuth, and O. Patashnik, Concrete Mathematics, Addison Wesley, 1989.

2. H. Prodinger, On the Number of Fibonacci Partitions of a Set, The Fibonacci Quarterly 19 (1981), 463–466.

3. H. Prodinger, Analysis of an Algorithm to Construct Fibonacci Partitions, RAIRO Informatique Théorique et Applications 18 (1984), 387–394.

Helmut Prodinger Department of Algebra and Discrete Mathematics TU Vienna Wiedner Hauptstrasse 8-10 A-1040 Vienna Austria