Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Prove the following fibonacci sequence, which appear in Pascal's Triangle. I am not sure where to start on this, any pointers? $$ f_n = {n\choose0} + {n-1\choose1} + ... + {n-k\choose k}$$

where $\displaystyle k=\left\lfloor\frac{n}{2}\right\rfloor$

share|improve this question

3 Answers 3

up vote 7 down vote accepted

The proof is simpler if you include terms where the lower argument is greater than the upper argument: that is, $$ F_{n+1}=\sum_{k=0}^{n}\binom{n-k}{k}\tag{1} $$ The terms where $n-k\lt k$ are $0$.

Initial Values:

For $n=0$, the sum gives $1$.

For $n=1$, the sum gives $1$.

Recursion:

The recursion is satisfied: $$ \begin{align} \hspace{-1cm}\sum_{k=0}^{n}\binom{n-k}{k}+\sum_{k=0}^{n+1}\binom{n+1-k}{k} &=\sum_{k=1}^{n+1}\binom{n+1-k}{k-1}+\sum_{k=0}^{n+1}\binom{n+1-k}{k}\tag{2}\\ &=1+\sum_{k=1}^{n+1}\binom{n+2-k}{k}\tag{3}\\ &=\sum_{k=0}^{n+2}\binom{n+2-k}{k}\tag{4} \end{align} $$ Explanation:
$(2)$: reindex the left sum $k\mapsto k-1$
$(3)$: pull out the $k=0$ term from the right sum and use $\binom{n+1}{k}=\binom{n\vphantom{1}}{k}+\binom{n\vphantom{1}}{k-1}$
$(4)$: put back the $k=0$ term

Note, however, that because of the initial values, the sum is actually $F_{n+1}$, and not $F_n$.

share|improve this answer

Hint: Try to use induction and:

$$ \begin{align} \tag{i} f_{n+2} &= f_{n+1} + f_n \\ \tag{ii} \binom{n}{k} &= \binom{n-1}{k} + \binom{n-1}{k-1} \qquad \text{for $n > 0$} \end{align} $$

share|improve this answer

A combinatorial proof.

Fibonacci numbers count the number of ways to walk up $n$ steps, going one or two steps at a time.

$\binom{n-k}{k}$ counts the number of ways of walking up $n$ steps, going one or two steps at a time, but doing exactly $k$ two-steps.

(There are $n-2k$ one-steps, for a total of $n-k$ steps, of which you choose $k$ to be the two-steps)

share|improve this answer
    
Very interesting (+1) –  robjohn Jul 8 at 0:59
    
@robjohn: Yeah it is interesting. In fact, this approach provides many other identities too. –  Aryabhata Jul 8 at 1:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.