$\sum_{k=1}^n \sum_{i=0}^{k-1}\binom{k-1-i}{i}=\sum_{j=0}^{n+1} \binom{n+1-j}{j}-1$ $\sum_{k=1}^n \sum_{i=0}^{k-1}\binom{k-1-i}{i}=\sum_{j=0}^{n+1} \binom{n+1-j}{j}-1$. How to prove it? By some example, I see both $=F_{n+2}-1$, where $F_n$ is the $n$-th Fibonacci number.
 A: The Fibonacci sequence can be defined as
$$F_{k}=\sum_{i=0}^{k-1}{k-1-i \choose i}, k\ge 1, F_1=1,F_2=1,F_3=2,...$$
Using $${n \choose k}={n-1 \choose k}+{n-1 \choose k-1}$$
Check that
$$\sum_{i=0}^{k-1}{k-1-i \choose i}=\sum_{i=0}^{k-1} {k-2-i \choose i}+\sum_{i=0}^{k-1}{k-2-i \choose i-1}.$$
$$\implies\sum_{i=0}^{k-1}{k-1-i \choose i}=\sum_{i=0}^{k-1} {k-2-i \choose i}+\sum_{i=0}^{k-1}{k-2-i \choose i-1}.$$
$$\implies\sum_{i=0}^{k-1}{k-1-i \choose i}=\sum_{i=0}^{k-2} {k-2-i \choose i}+\sum_{l=0}^{k-3}{k-3-j \choose j}+{-1\choose k-1}+{-1 \choose k-2}$$
$$\implies F_{k}=F_{k-1}+F_{k-2}+(-1)^{k-1}+(-1)^{k-2}$$
So we have to prove that
$$S=\sum_{k=1}^n \sum_{i=0}^{k-1}\binom{k-1-i}{i}=\sum_{j=0}^{n+1} \binom{n+1-j}{j}-1$$
Or equivalently
$$S\implies \sum_{k=1}^{n} F_{k}=F_{n+2}-1$$
This an be proved using $$F_{k}=\frac{a^{k}-b^{k}}{\sqrt{5}}, k\ge 1, a+b=1, ab=-1,a-b=\sqrt{5}$$
Then $$S=\frac{1}{\sqrt{5}}\sum_{k=1}^n[a^{k}-b^{k}]=\frac{1}{\sqrt{5}}\left(a\frac{a^n-1}{a-1}-b\frac{b^n-1}{b-1}\right)$$
$$\implies S=\frac{1}{\sqrt{5}}[a^{n+2}-b^{n+2}-\sqrt{5}]=F_{n+2}-1.$$
A: This is a combinatorial proof.
Left Hand Side
You have $k+1$ indistinguishable candies and want to distribute it to $i+1$ boxes but you want each box to have at least $2$ candies. The number of ways to do this is given by the term in the left hand side:
$$
\binom{(n+1)-(i+1)-1}{(i+1)-1}=\binom{k-1-i}{i}
$$
The left hand side then gives us the number of possible distribution for $2, 3, …, n+1$ candies into all possible number of boxes:
$$
\sum_{k=1}^{n}\sum_{i=0}^{k-1}\binom{k-1-i}{i}
$$
Right Hand Side
For every candies distribution, add another box filled with at least $2$ candies so that the total number of candies distributed is always $n+3$. Notice that this is the same as distributing $n+3$ candies into several boxes such that each box have at least $2$ candies, but not all candies are in the same box. The number of way to do this is given below:
$$
\sum_{j=1}^{n+1}\binom{(n+3)-(j+1)-1}{(j+1)-1}=\sum_{j=0}^{n+1}\binom{n+1-j}{j}-1
$$
Since we count the same objects, both left hand side and right hand side must be equal
Challenge for You
Prove that the following is true:
$$
\sum_{k=5}^{n}\sum_{i=0}^{\lfloor\frac{k-5}{6}\rfloor}\binom{k-5-5i}{i}=\sum_{j=1}^{\lfloor\frac{n+1}{6}\rfloor}\binom{n+1-5j}{j}
$$
A: I thought I'd add yet another proof to the list using a solid, simple and standard technique: induction. Checking $n=1$ is simple so suppose it holds for $n=l$ and consider the case of $n=l+1$.
The LHS is $$\sum_{k=1}^{l+1}\sum_{i=0}^{k-1} \binom{k-1-i}{i} = \sum_{k=1}^{l}\sum_{i=0}^{k-1} \binom{k-1-i}{i}+\sum_{i=0}^l\binom{l-i}{i}$$ $$= \left(\sum_{j=0}^{l+1}\binom{l+1-j}{j}-1\right) + \sum_{i=0}^l\binom{l-i}{i}$$
where the second equality is by the inductive hypothesis, and the RHS is $$\sum_{j=0}^{l+2}\binom{l+2-j}{j}-1$$ So showing equality between the LHS and RHS is equivalent to showing $$\sum_{i=0}^l\binom{l-i}{i} = \sum_{j=0}^{l+2}\binom{l+2-j}{j} -\sum_{j=0}^{l+1}\binom{l+1-j}{j}$$ We will simply the RHS of this new equation. Observe that $$\sum_{j=0}^{l+2}\binom{l+2-j}{j} -\sum_{j=0}^{l+1}\binom{l+1-j}{j} = \sum_{j=0}^{l+1}\binom{l+2-j}{j} -\binom{l+1-j}{j} = \sum_{j=1}^{l+1}\binom{l+2-j}{j} -\binom{l+1-j}{j}$$ and then we can use $\binom{n+1}{k+1}= \binom{n}{k}+\binom{n}{k+1}$ to simplify this to $$\sum_{j=1}^{l+1}\binom{l+1-j}{j-1}  = \sum_{j=1}^{l+1}\binom{l-(j-1)}{j-1} = \sum_{j=0}^{l}\binom{l-j}{j}$$ as desired!
