Showing $ F_{n}=\sum_{k=0}^n\binom{n}{k}F_{k}(-1)^{k+1}$ without Binet's formula

Question

In the post below I used the multiplication theorem of infinite series to reduce the problem to the identity below. Where $F_0=0, F_1=1$ and $F_n=F_{n-1}+F_{n-2}$ is the Fibonacci sequence.

Experimental identities with Fibonacci series

$$ F_{n}=\sum_{k=0}^n\binom{n}{k}F_{k}(-1)^{k+1} $$

Unfortunately I was unable to prove this without Binet's Formula which you could prove the problem with directly: $F_k=\dfrac{\varphi^k-\varphi^{-k}}{\varphi-\varphi^{-1}}$ .

$$ \begin{align} \sum_{k=0}^n\binom{n}{k}F_{k}(-1)^{k+1} &=\sum_{k=0}^n\binom{n}{k}(-1)^{k+1}\frac{\varphi^k-\varphi^{-k}}{\varphi-\varphi^{-1}}\\ &=\frac{1}{\varphi-\varphi^{-1}}\sum_{k=0}^n\binom{n}{k}(-1)^{k+1}\varphi^k-\sum_{k=0}^n\binom{n}{k}(-1)^{k+1}\varphi^{-k}\\ &=\frac{1}{\varphi-\varphi^{-1}}\sum_{k=0}^n\binom{n}{k}(-\varphi^{-1})^k-\sum_{k=0}^n\binom{n}{k}(-\varphi)^{k}\\ &= \frac{1}{\varphi-\varphi^{-1}}[(1-\varphi^{-1})^n-(1-\varphi)^n]\\ &= \frac{1}{\varphi-\varphi^{-1}}[(\varphi)^n-(\varphi^{-1})^n]\\ &= F_n \end{align} $$

That second to last line is because for the golden ratio $\varphi$, we have $1-\varphi=\varphi^{-1}$ similarly $1-\varphi^{-1}=\varphi$.

How can you prove this without Binet's Formula? I tried several things without success.

Answer 1

If $Q = \begin{pmatrix}1&1\\1&0\end{pmatrix}$ is the Fibonacci matrix, then $Q^n = \begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}$ for $n \in \mathbb Z$ and $Q^2=Q+1$.

Now write $$Q^{-n} = (Q^{-1})^{n} = (Q-1)^{n} = \sum_{k=0}^n\binom nk Q^k(-1)^{n-k}$$ conclude by comparing the anti-diagonal entires and using $F_{-n} = (-1)^{n+1}F_n$ in the LHS.

Note the similarity with the proof you have, except we work on the level of matrices instead of the level of eigenvalues.

Answer 2

Using the recurrence $F_{n}=F_{n-1}+F_{n-2}$ it is easy to see that the generating function for the Fibonacci numbers is

$$F(x)=\sum_{k\geq0}F_nx^n=\frac x{1-x-x^2}.$$

Now,

$$\sum_{n\geq0}x^n\sum_{k=0}^n\binom nkF_k(-1)^{k-1} =\sum_{k\geq0}F_k(-1)^{k-1}\underbrace{\sum_{n\geq k}\binom{n}{k}x^n}_{x^k/(1-x)^{k+1}} =\frac1{1-x}\sum_{k\geq0}F_k(-1)^{k-1}\left(\frac x{1-x}\right)^k =\frac1{x-1}F\left(\frac x{x-1}\right)$$

and simple algebra yields

$$\frac1{x-1}F\left(\frac x{x-1}\right)=F(x)$$

hence the claim.

Answer 3

Use exponential generating functions and binomial inversion. By binomial inversion it sufficies to prove the identity $$ F_n(-1)^{n+1}=\sum_{k=0}^n\binom{n}{k}(-1)^{n-k}F_k $$ Let $F(x)=\sum_{n\geq0} F_n x^n/n!=\frac{1}{\varphi-\varphi^{-1}}(e^{\varphi x}-e^{\varphi^{-1} x})$. The previous result can be derived in a similar way to obtaining the OGF for the Fibonacci numbers (except you solve a differential equation instead). If $A(x)=\sum_{n\geq 0}a_nx^n$, let $[x^n](A(x))=a_n$ extract the coefficient of $x^n$. Then by convolution of EGFs we have that $$ \begin{align} \sum_{k=0}^n\binom{n}{k}(-1)^{n-k}F_k &=n![x^n]\left( F(x)e^{-x} \right)\\ &=n![x^n]\left(\frac{1}{\varphi-\varphi^{-1}}(e^{(\varphi-1) x}-e^{(\varphi^{-1}-1) x})\right)\\ &=n![x^n]\left(\frac{1}{\varphi-\varphi^{-1}}(e^{-\varphi^{-1} x}-e^{-\varphi x})\right)\\ &=n)\\ &=(-1)^{n+1}F_n \end{align} $$ where we have used the identity $$1-\varphi^{-1}=\varphi.$$