# Homework Help: Proof By Induction: Fibonacci Sequence

1. Feb 18, 2012

### dba

1. The problem statement, all variables and given/known data
$\sum_{i=0}^{k} {k \choose i}f_{n+i} = f_{n+2k}$
2. Relevant equations
Definition:
$f(0)=0 ; f(1)=1$
$f(n)=f_{n-1} + f_{n-2}$ for $n>=2$

3. The attempt at a solution
I searched a basis for which the statement is true:
n=2 and k=1
$\sum_{i=0}^{1} {1 \choose i}f_{2+i} = f_{2+2(1)}$
i=0: ${1 \choose 0}f_{2+0} + {1 \choose 1}f_{3} = 3$

and

$f_{n+2k} = f_{2+2(1)} = f_{4} = 3$

I assume for k-1
$\sum_{i=0}^{k-1} {k-1 \choose i}f_{n+i} = f_{n+2(k-1)}$

I need to show
$\sum_{i=0}^{k} {k \choose i}f_{n+i} = f_{n+2k}$

Normally I would take the Left-hand-side(LHS) and
$\sum_{i=0}^{k} {k \choose i}f_{n+i} = \sum_{i=0}^{k-1} {k-1 \choose i}f_{n+i} +k$

I do not know how to write the summation notation in a way that I could get to the Right-hand-side(RHS) which would be f_{n+2k}

Thanks for any help.