I recently found out that the Fibonacci Sequence appears in the Pascal Triangle. If it is written like so:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
etc.
If we sum the diagonals, we get:
$1 = 1 $
$1 = 1 $
$1+1 = 2 $
$1+2 = 3 $
$1+3+1 = 5 $
etc.
Which is the Fibonacci Sequence
I realized that since Pascal's triangle can be written using the choose operation, I could find $F_n$ as such:
$F_n= \sum_{i=0}^{n/2}{{n-i}\choose{i}}$
My question is, can we prove this using induction? I tried but got stuck, here is my attempt:
For the base, when n=0, $F_0= \sum_{i=0}^{0/2}{{0-i}\choose{i}}= {0\choose0}=1$
Now, if we assume that the equation is correct for $n=k$, we must prove that the equation is true for $n=k+1$. Since we know that $F_{n+1}=F_n+F_{n-1}= \sum_{i=0}^{n/2}{{n-i}\choose{i}}+\sum_{i=0}^{{n-1}/2}{{n-1-i}\choose{i}}$.
Where do I go from here?