Fibonacci Identity with Binomial Coefficients A friend showed me this cool trick: Take any row of Pascal's triangle (say, $n = 7$):
$$1, 7, 21, 35, 35, 21, 7, 1$$
Leave out every other number, starting with the first one:
$$7, 35, 21, 1$$
Then these are backwards base-5 "digits", so calculate:
$$7 + 35 \cdot 5 + 21 \cdot 5^2 + 1 \cdot 5^3 = 7 + 175 + 525 + 125 = 832$$
and divide by $2^{7-1} = 2^6 = 64$:
$$\frac{832}{64} = 13$$
and $F_7 = 13$ (the seventh Fibonacci number)!
He said it works for any $n$. I have worked out that this would be to prove that:
$$\frac{1}{2^{n-1}}\sum_{k = 0}^{\lfloor{\frac{n}{2}}\rfloor}{\left(5^k {n \choose 2k + 1} \right)} = F_n $$
I'm not sure how to proceed from here. Is there a neat combinatoric or easy algebraic proof I am missing? Thanks!
 A: Easy algebraic proof. Just use Binet's formula:
$$F_n = \frac{1}{\sqrt{5}} \left( \left(\frac{1 + \sqrt{5}}{2} \right)^n - \left(\frac{1 - \sqrt{5}}{2} \right)^n \right) $$
If you expand the powers using binomial coefficients and simplify, you will see that terms with $\sqrt{5}$ cancel and you should get your desired result exactly!
A: Suppose we seek to show that
$$\frac{1}{2^{n-1}} \sum_{k=0}^{\lfloor n/2\rfloor}
5^k {n\choose 2k+1} = F_n$$
a Fibonacci number. Introduce
$${n\choose 2k+1} = {n\choose n-2k-1} =
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n-2k}} (1+z)^n \; dz.$$
Observe  that the  largest index  $k$  producing a  non-zero value  is
$\lfloor n/2\rfloor-1$ when $n$  is even and $\lfloor n/2\rfloor$ when
$n$    is    odd.    The    integral    correctly   represents    this
behavior. Extending  the range of $k$  to infinity we  thus obtain for
the sum
$$\frac{1}{2^{n-1}} \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n}} 
(1+z)^n \sum_{k\ge 0} 5^k z^{2k} \; dz
\\ = \frac{1}{2^{n-1}} \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n}} (1+z)^n
\frac{1}{1-5z^2} \; dz.$$
Now put $z/(1+z) = w$ so that $z = w/(1-w)$ and $dz = 1/(1-w)^2 dw$
to get 
$$\frac{1}{2^{n-1}} \frac{1}{2\pi i}
\int_{|w|=\gamma} \frac{1}{w^n}
\frac{1}{1-5w^2/(1-w)^2} \frac{1}{(1-w)^2} \; dw
\\ = \frac{1}{2^{n-1}} \frac{1}{2\pi i}
\int_{|w|=\gamma} \frac{1}{w^n}
\frac{1}{1-2w-4w^2} \; dw.$$
Extracting coefficients we find
$$\frac{1}{2^{n-1}} [w^{n-1}] \frac{1}{1-2w-4w^2}
= [w^{n-1}] \frac{1}{1-2(w/2)-4(w/2)^2}
\\ = [w^{n-1}] \frac{1}{1-w-w^2}
\\ = [w^{n}] \frac{w}{1-w-w^2}.$$
This is precisely the generating function of the Fibonacci numbers and
we are done.
A: Starting with Binet's Formula:
$$F_n = \frac{1}{\sqrt{5}} \left( \left(\frac{1 + \sqrt{5}}{2} \right)^n - \left(\frac{1 - \sqrt{5}}{2} \right)^n \right) $$
Expand using Binomial Formula:
$$F_n = \frac{1}{2^n\sqrt{5}} \left( \sum_{k=0}^n \left({n \choose k} \left( \sqrt{5} \right)^k\right) - \sum_{k=0}^n \left({n \choose k} \left( \sqrt{5} \right)^k \left(-1\right)^k\right) \right) $$
Combine:
$$F_n = \frac{1}{2^n\sqrt{5}} \left( \sum_{k=0}^n \left({n \choose k} \left( \sqrt{5} \right)^k\left(1-\left(-1\right)^k\right)\right)\right) $$
But $1 - \left(-1\right)^k$ is $0$ for even $k$ and $2$ for odd $k$. So we can consider only the case where $k$ is odd, so $k = 2j + 1$:
$$F_n = \frac{1}{2^n\sqrt{5}} \left( \sum_{2j+1=1}^{2j+1=n} \left({n \choose 2j+1} \left( \sqrt{5} \right)^{2j+1}\cdot2\right)\right) $$
Simplify:
$$F_n = \frac{1}{2^{n-1}\sqrt{5}} \sum_{j=0}^{\lfloor{\frac{n}{2}}\rfloor} \left({n \choose 2j+1} \left( 5^j \sqrt{5} \right)\right) $$
$$F_n = \frac{1}{2^{n-1}} \sum_{j=0}^{\lfloor{\frac{n}{2}}\rfloor} \left(5^j {n \choose 2j+1} \right) $$
And we are done!!
A: To cancel out the binomial coefficients with even bottom indices, the sum can be written as
$$
\begin{align}
\frac1{2^{n-1}}\sum_{k=0}^n\binom{n}{k}\frac{\sqrt5^k-\left(-\sqrt5\right)^k}{2\sqrt5}
&=\frac{\left(\frac{1+\sqrt5}2\right)^n-\left(\frac{1-\sqrt5}2\right)^n}{\sqrt5}\\
&=F_n
\end{align}
$$
