15
$\begingroup$

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!

$\endgroup$
8
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Great! I will try and I might post it as an answer. $\endgroup$ – Barron Nov 6 '16 at 23:31
  • $\begingroup$ I figured it out! I have posted it here. Thanks! $\endgroup$ – Barron Nov 6 '16 at 23:45
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Wow, that's cool and very different! Where do you get the first equation from? I think that's the only thing I don't quite understand. $\endgroup$ – Barron Nov 6 '16 at 23:54
  • $\begingroup$ This method is called the Egorychev method. The first equation represents the formal power series identity $${n\choose k} = [z^k] (1+z)^n$$ using complex variables. It becomes evident that we substitute the main variable during the computation and that's why power series alone does not suffice and we need the differential. $\endgroup$ – Marko Riedel Nov 6 '16 at 23:59
  • $\begingroup$ Ah, cool! I hadn't heard of this before, but it's very nice! $\endgroup$ – Barron Nov 7 '16 at 0:04
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you! That makes it very easy. $\endgroup$ – Barron Nov 6 '16 at 23:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.