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!

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!!
