<s>[INST] 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!
 [/INST] 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.
</s>