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

Question

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

I tried the idea of using Pascal's triangle, but it seems to need some adjustment, so I am stuck, please help.

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

Thank you.

Answer 1

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. :)

Answer 2

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