# Prove that $F_n={n-1 \choose 0 }+{n-2 \choose 1 }+{n-3 \choose 2 }+\ldots$ where $F(n)$ is the $n$-th fibonacci number [duplicate]

If $F_n$ is the $n$-th fibonacci number, then prove that,
$$F_n={n-1 \choose 0 }+{n-2 \choose 1 }+{n-3 \choose 2 }+\ldots$$

Any combinatorial argument would be of greater help than rigorous proof.

Thank you.

## marked as duplicate by Grigory M, user98602, Najib Idrissi, user147263, user26857Dec 24 '14 at 17:39

• This just begs for induction: write out $F_{n+1}$ and $F_{n+2}$, and repeatedly apply the rule that ${n+1 \choose k} = {n \choose k}+ {n \choose k-1}$. – John Hughes Dec 24 '14 at 14:49
• @JohnHughes ok, that's an idea, thanks, but I need something more inspiring. – Swadhin Dec 24 '14 at 14:50
• You can check this link en.wikipedia.org/wiki/Fibonacci_number#Use_in_mathematics – Jihad Dec 24 '14 at 14:51
• Sorry...all I've got is math, not inspiration. Try writing out $F_{n+2} = F_{n+1} + F_n$ for, say, $n = 3$, writing out all the terms (not with values, but in "m choose k" form), and then seeing which ones you can pair up nicely to show that the statement is true. That'll lead you to the induction proof. – John Hughes Dec 24 '14 at 14:51
• I'm not quite sure what you mean by the $+\cdots$ in your question. Also, are you using $F_1=0$ or $F_1=1$? – Math1000 Dec 24 '14 at 15:25

Let's call that relation $B_n$ instead for a second ($B$ is for binomial). Let's also say for the moment that $n$ is even, so $n=2m$, with $m$ an integer.

Now,

$$B_{n-1} = {2m-2 \choose 0 }+{2m-3 \choose 1 }+{2m-4 \choose 2 }+\ldots+{m - 1 \choose m - 1},$$

and

$$B_{n-2} = {2m-3 \choose 0 }+{2m-4 \choose 1 }+{2m-5 \choose 2 }+\ldots+{m - 1 \choose m - 2}.$$

From Pascal's triangle, we have the relation

$${n \choose k} + {n \choose k+1} = {n+1 \choose k+1}.$$

Looking at the two expressions for $B_{n-1}, B_{n-2}$, and applying this relation as we add the $k$th term of $B_{n-2}$ and the $(k+1)$th term of $B_{n-1}$, we see that

$$B_{n-1} + B_{n-2} = {2m-2 \choose 0} + {2m-2 \choose 1} + {2m-3 \choose 2} + \ldots +{m \choose m-1}+ {m - 1 \choose m - 2}.$$

Since ${n \choose 0} = 1$ for any positive integer $n$, we can substitute ${2m-1 \choose 0}$ for the first term.

Hence, $B_n = B_{n-1} + B_{n-2}$ for even $n$.

The process is similar to show that this holds for odd $n$.

Finally, noting that $B_1 = 1$ and $B_2 = 2$, we've shown that $B_n$ is the Fibonacci series, which is in essence what you set out to prove.

But ... I'll agree with other commenters that induction is cleaner. :)

For $n \ge 1$, let $f_n$ be the number of ways of breaking a string of length $n-1$ into substrings of length $1$ and $2$. It is easy to see

$$f_1 = f_2 = 1, f_3 = 2,\ldots \quad\text{ and }\quad f_n = f_{n-1} + f_{n-2}\quad\text{ for } n \ge 3$$

Compare this with the definition of the Fibonacci numbers $F_n$, we have $f_n = F_n$.

An alternative way to count $f_n$ is group the breakdown of original string according to the number of substrings with length $2$. Let $k$ be the number of substrings with length $2$ in a breakdown. It is clear $0 \le k \le \lfloor \frac{n-1}{2}\rfloor$. For any breakdown with a given $k$, there will be $n-1-k$ substrings, $n-1-2k$ of them have length $1$ and $k$ of them have length $2$. It is clear there are $$\binom{n-1-2k+k}{k} = \binom{n-1-k}{k}$$ ways of mixing these two set of substrings. As a result

$$F_n = f_n = \sum_{k=0}^{\lfloor\frac{n-1}{2}\rfloor} \binom{n-1-k}{k}$$