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!

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!

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.

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

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