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!

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