Relation between Pascal's triangle and fibonacci series. 
Accidentally, I had seen this relation. I tried to find the formula
Here is my try:-
$$f_0= {{0}\choose{0}}  $$
$$f_1={{1}\choose{0}} $$
$$f_2={{2}\choose{0}}+ {{1}\choose{1}} $$
$$f_3= {{3}\choose{0}}+ {{2}\choose{1}} $$
$$f_4= {{4}\choose{0}}+ {{3}\choose{1}}+{{2}\choose{2}} $$
$$...$$
Generalizing,
$$f_n=\sum_{s+r=n,s\ge r}{{s}\choose{r}}, 0\le s,r \le n $$
How to write the correct formula of n-th term. Why this pattern is coming. I could verify using calculation for upto n=10. How to give a rigorous proof?.
 A: Let $f_n$ be the number of ways to climb a stair of $n$ levels, each time you can cross through one or two steps. 
There are two ways to evaluate this. The first way is via recursion. If your first move crossed through one step, you have $f_{n-1}$ ways to clime the remaining; and if your first move crossed through two steps, you have $f_{n-2}$ ways to do the remaining. So $f_n = f_{n-1} + f_{n-2}$. The initial condition gives $f_1 = 1$ and $f_2 = 2$, and you can see this is Fibonacci.
On the other hand, you can find a way to describe via combinatorics. If you climb the entire stairs of $n$ levels in $n$ moves, then you crossed one step $n$ times and crossed two steps 0 time, so there are $\binom {n}{0}$ ways to do so. If If you climb the entire stairs of $n$ levels in $n-1$ moves, then you crossed one step $n-1$ times and crossed two steps 1 time, so there are $\binom {n-1}{1}$ ways to do so. So on and so forth you see that
$$
f_n = \binom {n}{0} + \binom {n-1}{1} + \binom {n-2}{2} + \cdots.
$$
