"A combinatorial proof for the non-recursive expression of the Fibonacci polynomial"

One of the well-known extension of the Fibonacci sequence is the Fibonacci polynomial which is defined by the
following recurrence relation
$$
F_n(x)=xF_{n-1}(x)+F_{n-2}(x)\, .
$$
A non-recursive expression for $F_n(x)$, given in the following form

$$
F_n(x)=\sum_{j=0}^{\lfloor \frac{n-1}{2} \rfloor}
\left(
\begin{array}{c}
n-j-1 \\
j
\end{array}
\right)
x^{n-2j-1} \, .
$$
Now, i want to prove the above formula with the combinatorial method. Assume the following matrix
$$
A_2=\left(
\begin{array}{cc}
x & 1 \\
1 & 0
\end{array}
\right) \, .
$$
With the induction on $n$, we can prove that the $n$th power of the matrix $A_2$ is as follows
$$
A_2^n=\left(
\begin{array}{cc}
F_{n+1}(x) & F_{n}(x) \\
\\
F_{n}(x) & F_{n-1}(x)
\end{array}
\right) \, .
$$
Assume the matrix $A_p$ of order $p$, be in the following form

$$
A_p=\left(
\begin{array}{cccccc}
u_1 &u_2 &\cdots& \cdots &u_{p-1} &u_p \\
1 &0 &\cdots &\cdots &\cdots &0 \\
0 &\ddots &\ddots &\ddots &\ddots &\vdots \\
\vdots &\ddots &\ddots &\ddots &\ddots &\vdots \\
\vdots &\ddots &\ddots &\ddots &\ddots &\vdots \\
0 &\cdots &\cdots &0 &1 &0 \\
\end{array}
\right)_{p \times p} \, .
$$
We have the following combinatorial theorem by Chen about the $(i,j)$ entry of the $n$th power of matrix $A_p$, as shown

Let the $(i,j)$ entry of the $n$th power of matrix $A_p$ called $a_{ij}^n$, then the combinatorial closed-form of $a_{ij}^n$,
is in the following form
$$
a_{ij}^n=\sum_{(k_1,k_2,\cdots,k_p)} \frac{k_j+k_{j+1}+\cdots+k_p}{k_1+k_2+\cdots+k_p}\times
\left(
\begin{array}{c}
k_1+\cdots+k_p \\
k_1,\cdots , k_p
\end{array}
\right)
u_1^{k_1}\cdots u_p^{k_p} \, .
$$
where the summation is over non-negative integers satisfying
$$
k_1+2\, k_2+3\, k_3+\cdots + p\, k_p=n-i+j \, .
$$
and the coefficients $k_i$ are defined $1$ when $n=i-j$.
$$

Based on the Chen theorem
the combinatorial closed-form of $F_n(x)$, is in the following form(notice that to the position of $F_n(x)$ in
the matrix $A_2^n$)

$$
F_n(x)=\sum_{(k_1,k_2)}
\left(
\begin{array}{c}
k_1+k_2 \\
k_1, k_2
\end{array}
\right)
x^{k_1} \, .
$$

where the summation is over non-negative integers satisfying
$$
k_1+2\, k_2=n-1\, .
$$

from the last relation, we get the two following equations

$$
k_1+2\, k_2=n-1 \quad
\Longrightarrow
\left\{
\begin{array}{cc}
1) & k_1+k_2=n-k_2-1 \, ,\\
\\
2) & k_1=n-2k_2-1 \, .
\end{array}
\right.
$$

using the two above equations, we have

$$
F_n(x)=\sum_{k_2}
\left(
\begin{array}{c}
n-k_2-1 \\
n-2k_2-1, k_2
\end{array}
\right)
x^{n-2k_2-1} \, .
$$

for simplicity, denote $k_2$ by $j$, then we rewrite the above relation, as follows

$$
F_n(x)=
\sum_{j=0}^{\lfloor \frac{n-1}{2} \rfloor}
\left(
\begin{array}{c}
n-j-1 \\
n-2j-1 , j
\end{array}
\right)
x^{n-2j-1}
=\sum_{j=0}^{\lfloor \frac{n-1}{2} \rfloor}
\left(
\begin{array}{c}
n-j-1 \\
j
\end{array}
\right)
x^{n-2j-1} \, .
$$

Chen article: http://www.sciencedirect.com/science/article/pii/0024379595901639

6more comments