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

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.

• have you tried by induction? – user May 24 '18 at 20:07
• @gimusi yes I've tried induction. – N8tron May 24 '18 at 21:15
• and what have you obtained? – user May 24 '18 at 21:17
• @gimusi nothing that I see how to use. – N8tron May 24 '18 at 21:36

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.

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.

• This all looks good, but I don't see why $$\sum_{n\ge k} \binom{n}{k}x^n=\frac{x^k}{(1-x)^{k+1}}$$ any hints? – N8tron May 27 '18 at 19:12
• @N8tron Differentiate $k$ times the identity $\sum_n x^n=\frac1{1-x}$. – user246336 May 27 '18 at 19:14
• Ah so $$\sum_{n\ge k} \frac{n!}{(n-k)!}x^{n-k}=\frac{k!}{(1-x)^{k+1}}$$ and a cheeky multiplication by $\dfrac{x^k}{k!}$ finishes things up. Thanks :) – N8tron May 27 '18 at 19:21
• You're welcome! – user246336 May 27 '18 at 19:28

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![x^n](-F(-x))\\ &=(-1)^{n+1}F_n \end{align} where we have used the identity $$1-\varphi^{-1}=\varphi.$$

• Much of this is new to me, I don't expect you to teach me all of it, but can you tell me what the acronyms are OGF and EGF? – N8tron May 24 '18 at 21:33
• Ordinary Generating Function and Exponential Generating Function – Foobaz John May 24 '18 at 22:01
• As far as I can tell this is effectively undoing the transform I did in the linked article and proving it directly with generating functions. Is that correct? math.stackexchange.com/questions/2794183/… – N8tron May 28 '18 at 18:13