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.

  • 1
    $\begingroup$ have you tried by induction? $\endgroup$ – user May 24 '18 at 20:07
  • $\begingroup$ @gimusi yes I've tried induction. $\endgroup$ – N8tron May 24 '18 at 21:15
  • $\begingroup$ and what have you obtained? $\endgroup$ – user May 24 '18 at 21:17
  • $\begingroup$ @gimusi nothing that I see how to use. $\endgroup$ – 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.

| cite | improve this answer | |

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}.$$


$$\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.

| cite | improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – N8tron May 27 '18 at 19:12
  • 2
    $\begingroup$ @N8tron Differentiate $k$ times the identity $\sum_n x^n=\frac1{1-x}$. $\endgroup$ – user246336 May 27 '18 at 19:14
  • $\begingroup$ 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 :) $\endgroup$ – N8tron May 27 '18 at 19:21
  • $\begingroup$ You're welcome! $\endgroup$ – 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.$$

| cite | improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – N8tron May 24 '18 at 21:33
  • 1
    $\begingroup$ Ordinary Generating Function and Exponential Generating Function $\endgroup$ – Foobaz John May 24 '18 at 22:01
  • $\begingroup$ 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/… $\endgroup$ – N8tron May 28 '18 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.