Proof By Induction: Fibonacci Sequence

[dba]

Homework Statement

[itex]\sum_{i=0}^{k} {k \choose i}f_{n+i} = f_{n+2k} [/itex]

Homework Equations

Definition:
[itex] f(0)=0 ; f(1)=1 [/itex]
[itex]f(n)=f_{n-1} + f_{n-2}[/itex] for [itex] n>=2[/itex]

The Attempt at a Solution

I searched a basis for which the statement is true:
n=2 and k=1
[itex]\sum_{i=0}^{1} {1 \choose i}f_{2+i} = f_{2+2(1)} [/itex]
i=0: [itex]{1 \choose 0}f_{2+0} + {1 \choose 1}f_{3} = 3[/itex]

and

[itex]f_{n+2k} = f_{2+2(1)} = f_{4} = 3[/itex]

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

I need to show
[itex]\sum_{i=0}^{k} {k \choose i}f_{n+i} = f_{n+2k} [/itex]

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

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.

 

[KataKoniK]

First, let's rewrite the LHS using the given definition:
\sum_{i=0}^{k} {k \choose i}f_{n+i} = \sum_{i=0}^{k} {k \choose i} (f_{n+i-1} + f_{n+i-2})

Then, we can split this into two summations:
\sum_{i=0}^{k} {k \choose i}f_{n+i-1} + \sum_{i=0}^{k} {k \choose i}f_{n+i-2}

Next, we can use the binomial theorem to expand the first summation:
\sum_{i=0}^{k} {k \choose i}f_{n+i-1} = \sum_{i=0}^{k} {k \choose i} (f_{n+i} + f_{n+i-1})

Now, we can combine this with the second summation to get:
\sum_{i=0}^{k} {k \choose i}f_{n+i-1} + \sum_{i=0}^{k} {k \choose i}f_{n+i-2} = \sum_{i=0}^{k} {k \choose i} (f_{n+i} + f_{n+i-1}) + \sum_{i=0}^{k} {k \choose i}f_{n+i-2}

Using the distributive property, we can rewrite this as:
\sum_{i=0}^{k} {k \choose i} (f_{n+i} + f_{n+i-1} + f_{n+i-2})

Now, we can use the given definition again to rewrite the summation:
\sum_{i=0}^{k} {k \choose i} (f_{n+i} + f_{n+i-1} + f_{n+i-2}) = \sum_{i=0}^{k} {k \choose i} (f_{n+i+1} + f_{n+i})

Finally, we can use the binomial theorem to expand this last summation and we will get:
\sum_{i=0}^{k} {k \choose i} (f_{n+i+1} + f_{