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!
 A: 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}.$$
A: 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]
