%Bulletin EATCS

\input amstex
\documentstyle{amsppt}


\headline=               
{\ifnum\pageno=1\hfil
 \else\vbox{\line {\tenit 
Polynomials related to the Fibonacci polynomials
 \hfil\tenrm\number\pageno}
\vskip 2pt\hrule}\fi}
\footline={\hfil}
\catcode`\@=11
\redefine\logo@{}
\firstpage@false
\catcode`\@=13

%\input graphic



%\NoBlackBoxes
\TagsOnRight
\topmatter
\redefine\L{\log 2}

\title 
Some polynomials related to the Fibonacci polynomials
\endtitle
\author Helmut Prodinger \endauthor
\affil 
Department of Algebra and Discrete Mathematics 
Technical University of Vienna, Austria
\endaffil
\address
Helmut Prodinger\newline
Department of Algebra and Discrete Mathematics \newline
 TU Vienna\newline
 Wiedner Hauptstrasse 8-10\newline A-1040 Vienna\newline Austria
\endaddress 

\endtopmatter

\document

In my old paper \cite3,
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=\sum_{1\le k<n}\binom{n-1-k}{k-1}
x^k(x-1)^{n-2k}+
\sum_{0\le k<n}\binom{n-1-k}{k}
x^{k+1}(x-1)^{n-1-2k}.
$$

The polynomials involved are closely related to the {\sl Fibonacci polynomials}
$$\aligned
u_n(z)&=\sum_{0\le k\le n} \binom{n-k}{k}z^k\\&
=\frac{1}{\sqrt{1+4z}}\left[\left(\frac{1+\sqrt{1+4z}}{2}\, \right)^{n+1}-
\left(\frac{1-\sqrt{1+4z}}{2}\, \right)^{n+1}\right].
\endaligned
$$
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

$$
\sum_{1\le k<n}(k)_s\binom{n-1-k}{k-1}
x^k(x-1)^{n-2k}+
\sum_{0\le 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)^nz^s\Big(\frac{d}{dz}\Big)^szu_{n-2}(z)+
x(x-1)^{n-1}z^s\Big(\frac{d}{dz}\Big)^su_{n-1}(z).
$$
Performing these computations by hand I finally got
$$
\sum_{1\le k\le n-1}(-1)^{n+1-k}kx^k\qquad\text{for $s=1$}
$$
and
$$
\sum_{2\le k\le n-2}(-1)^{n-k}(n-1-k)k(k-1)x^k\qquad\text{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\ge1$):
$$\aligned
&\sum_{1\le k <n}\binom ks\binom{n-1-k}{k-1}x^k(x-1)^{n-2k}\\ & +
\sum_{0\le k <n}\binom ks\binom{n-1-k}{k}x^{k+1}(x-1)^{n-1-2k}\\
&=\sum_{0\le k< n}(-1)^{s+n-k}\binom{n-1-k}{s-1}\binom ksx^k.
\endaligned
$$
In terms of the coefficient of $x^m$ ($0<m<n$) this means

$$
\aligned
&\sum_{1\le k <n}(-1)^k\binom ks\binom{n-1-k}{k-1}\binom{n-2k}{m-k}\\ & +
\sum_{0\le k <n}(-1)^k\binom ks\binom{n-1-k}{k}\binom{n-1-2k}{m-1-k}\\
&=\binom{n-1-m}{s-1}\binom ms(-1)^s.\endaligned
$$

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\ge1$, we can assume the same range $1\le k< n$ in both sums.
The $k$th term is then
$$
\aligned
&(-1)^k\binom ks\binom{n-1-k}{k-1}\binom{n-2k}{m-k}+
(-1)^k\binom ks\binom{n-1-k}{k}\binom{n-1-2k}{m-1-k}\\
&=(-1)^k\binom ks\binom{n-1-k}{m-1}\binom{m-1}{k-1}+
(-1)^k\binom ks\binom{n-1-k}{m-1}\binom{m-1}{k}\\
&=(-1)^k\binom ks\binom{n-1-k}{m-1}\binom{m}{k}\\
&=(-1)^k\binom ms\binom{m-s}{k-s}\binom{n-1-k}{m-1}.
\endaligned
$$
The sum on $k$  of this expression can be simplified due the equation
(5.25) in \cite{1} that I repeat now for convenience:
$$
\sum_{k\le l}\binom{l-k}{m}\binom{s}{k-n}(-1)^k=(-1)^{l+m}
\binom{s-m-1}{l-m-n}, \quad\text {integers $l,m,n\ge0$}.
$$
It is a disguised form of the Vandermonde convolution.

Therefore
$$
\aligned
&\sum_{k}(-1)^k\binom ms\binom{m-s}{k-s}\binom{n-1-k}{m-1}\\
&=\binom ms(-1)^{n+m}\binom{-s}{n-m-s}\\
&=\binom ms(-1)^{s}\binom{n-m-1}{s-1},
\endaligned
$$
and the proof is finished.

\medskip

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.





\Refs

\ref \no 1 \by R.L. Graham, D.E. Knuth, and
O. Patashnik \book Concrete Mathematics
\yr 1989 \publ Addison Wesley \endref




\ref \no 2 \by H. Prodinger\paper 
On the Number of Fibonacci Partitions of a Set
\jour The Fibonacci Quarterly
\vol 19 \yr 1981 \pages 463--466 \endref

\ref \no 3 \by H. Prodinger\paper 
Analysis of an Algorithm to Construct Fibonacci Partitions
\jour RAIRO Informatique Th\'eorique
et Applications \vol 18 \yr 1984 \pages 387--394 \endref


\endRefs


\enddocument