# Fibonacci Recursion with Binomial Coefficients

While experimenting with Fibonacci numbers and Pascal's triangle, I found this: take any row of Pascal's triangle (say, $n = 7$): $$1, 7, 21, 35, 35, 21, 7, 1$$ and write under it the Fibonacci numbers, with $F_0=0$ going under the second number (of course, we assume $F_{-1} = F_1 - F_0 = 1$). Then, write a third row of $\pm1$'s: $$\begin{array}{ccc}1&7&21&35&35&21&7&1\\1&0&1&1&2&3&5&8\\1&-1&1&-1&1&-1&1&-1\\\end{array}$$ Multiply down the columns: $$\begin{array}{ccc}1&0&21&-35&70&-63&35&-8\\\end{array}$$ and now add the row to get $21$, which is the ($n+1$)th Fibonacci number! This seems to work for all $n$.

To prove this would be to prove the following Fibonacci recursion with binomial coefficients: $$F_{n+1} = \sum_{k=0}^n {\left(\left(-1\right)^k {n\choose k} F_{k-1}\right)}$$ I'm not sure how to continue from here; any hints? Thanks!

• Induction would probably be the tool of choice here! – flawr Feb 13 '17 at 23:41
• The easiest way to prove this is probably generating functions; you can take advantage of the fact that ${n\choose k}={n\choose n-k}$ to write this as $F_{n+1}=\sum_k a_kb_{n-k}$ for suitable terms $a_i$ and $b_i$; the sum on the right hand side is then just the product of the generating functions for the two sequences $a_n$ and $b_n$, so it's easy to compare and confirm the identity. There's also probably a super-slick combinatorial proof, but I'm not seeing it offhand... – Steven Stadnicki Feb 13 '17 at 23:41
• The really cool thing about this is that you can use this representation to end up showing that any positive integer $n$ can be written of the form $\sum_{k=1}^{n}c_{n}F_{n}$ for some sequnce $c_n$ of binomial coefficients. – Plopperzz Feb 14 '17 at 0:02

Remember that $F_n = \frac{1}{\sqrt5}\left(\varphi^n - (-\varphi)^{-n}\right)$ and $\varphi - 1 = \frac{1}{\varphi}$. Now we can substitue it into your sum: $$\sum_{k = 0}^n \left((-1)^k \binom{n}{k}F_{k - 1}\right)\\ = \frac{1}{\sqrt5}\sum_{k = 0}^n \left((-1)^k \binom{n}{k} (\varphi^{k - 1} - (-\varphi)^{1 - k})\right)\\ = \frac{1}{\sqrt5}\left(\frac{1}{\varphi}(1 - \varphi)^n + \varphi\left(1 + \frac{1}{\varphi}\right)^n\right)\\ = \frac{1}{\sqrt5}\left(-(-\varphi)^{-n - 1} + \varphi^{n + 1}\right) \\ = F_{n + 1}.$$
• Minor nitpickery: you have a typo in the penultimate line; the $(-\varphi)^{n+1}$ term should have a negative exponent, not a positive one. – Steven Stadnicki Feb 14 '17 at 1:24
A dynamical systems approach: Let $\sigma$ denote the "right-shift" on the space of sequences $(x_n)_{n\in {\Bbb Z}}$, i.e.: $$(\sigma x)_n = x_{n+1}, \ \ {n\in {\Bbb Z}}$$ Then the Fibonacci sequence, $(F_n)_{n\in {\Bbb Z}}$, verifies: $$\sigma^2 F = \sigma F + F = (\sigma +1) F$$ or, equivalently, $$\sigma^{-1}F = \sigma F - F = (\sigma -1) F$$ The first identity implies: $$\sigma^{2n} F = (\sigma +1)^n F = \sum_{k=0}^n \binom{n}{k}\sigma^k F$$ and the second: $$\sigma^{-n} F = (\sigma -1)^n F = \sum_{k=0}^n (-1)^{n-k}\binom{n}{k}\sigma^k F = (-1)^{n+1} \sum_{k=0}^{n-1} (-1)^{k-1}\binom{n}{k}\sigma^k F$$ Evaluating the latter at the index $-1$, i.e.: $$F_{-n-1}=(\sigma^{-n} F)_{-1} = (-1)^{n} \sum_{k=0}^n (-1)^{k}\binom{n}{k}\sigma^k F_{k-1}$$ we see that your identity really corresponds to evaluating $(-1)^{n} F_{-n-1}$ and not $F_{n+1}$. They just happen to be identical, due to the symmetry in the initial conditions that define $(F_n)_{n\in {\Bbb Z}}$ [The sequence $F_n + (-1)^n F_{-n}, \ {n\in {\Bbb Z}}$ is identically zero]