Fibonacci Recursion with Binomial Coefficients

Question

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!

Answer 1

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

Answer 2

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]