# Summation notation Fibonacci

1. Feb 18, 2012

### dba

1. The problem statement, all variables and given/known data
I have trouble with the summation notation.

$\sum_{i=0}^{k}\binom{k}{i}f_{n+i}$

How do I write this as a sequence based on the definition of Fibonacci sequence?

2. Relevant equations
Definition:
f(0)=0
f(1)=1
f(n)=f(n-1) + f(n-2) for n>=2

Example:
f(2) = f(1) + f(0) = 1+0 = 1
f(3) = f(2) + f(1) = 1+1 = 2
f(4) = f(3) + f(2) = 2+1 = 3
f(5) = f(4) + f(3) = 3+2 = 5
and so on

3. The attempt at a solution
I know how to write:

$\sum_{i=1}^{n}(i) = 1+2+3+...+n$

but I do not understand how to write the following Fibonacci sequence:

$\sum_{i=0}^{k}\binom{k}{i}f_{n+i}$

Can someone show me how to write this as an expanded version or give me an example how to do this?
Thank you.

2. Feb 18, 2012

### HallsofIvy

$\begin{pmatrix}n \\ i\end{pmatrix}$ is the "binomial coefficient"
$$\frac{n!}{i! (n-i)!}$$
$\sum_{i=0}^k \begin{pmatrix}k\\ i \end{pmatrix}f_{n+i}= f_n+ kf_{n+1}+ (k(k-1)/2)f_{n+2}+ \cdot\cdot\cdot$

So, for example, with k= 3
$$\sum_{i=0}^3\begin{pmatrix}3 \\ i\end{pmatrix}f_{n+i}= f_n+ 3f_{n+1}+ 3f_{n+2}+ f_{n+3}$$

3. Feb 18, 2012

### dba

Thank you very much.
I understand this now