1
$\begingroup$

Can anybody provide a combinatorial proof or algebraic proof of following identity? ${n\choose 0 }+ {n-1\choose 1}+{n-2\choose 2}+ .. +{{n-\lfloor n/2\rfloor} \choose {\lfloor n/2\rfloor}} = F_{n+1}$ where $F_{n}$ is $n^{\text{th}}$ term of Fibonacci series.

  • 0
    I have already proved using weak induction. But i feel, that is not a proper way.2012-09-26

2 Answers 2

2

$F_{n+1}$ is the number of tilings of a board of length $n$ with tiles of length $1$ or $2$. If we use $k$ tiles of length $2$, there are exactly $\binom{n-k}k$ possibilities to position these on the board, for each such possibility corresponds to a position of $k$ length-1-tiles on a $n-k$ board (just cut off the second half of each tile). As we can use at most $\lfloor n/2\rfloor$ tiles of length 2, we get \[ F_{n+1} = \sum_{k=0}^{\lfloor n/2\rfloor} \binom{n-k}k \] as wished. Hope that is combinatorial enough. :)

  • 0
    Thanks. This argument is very helpful2012-09-26
0

Call your sum $A_n$. By looking at Pascal's triangle (or algebraically) you can verify that $A_{n} + A_{n+1} = A_{n+2}$. Clearly, $A_0 = A_1 = 1$. These relations uniquely define the Fibonacci sequence.