Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Summation notation Fibonacci

  1. Feb 18, 2012 #1

    dba

    User Avatar

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

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

    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:

    [itex]\sum_{i=1}^{n}(i) = 1+2+3+...+n [/itex]

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

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

    Can someone show me how to write this as an expanded version or give me an example how to do this?
    Thank you.
     
  2. jcsd
  3. Feb 18, 2012 #2

    HallsofIvy

    User Avatar
    Science Advisor

    [itex]\begin{pmatrix}n \\ i\end{pmatrix}[/itex] is the "binomial coefficient"
    [tex]\frac{n!}{i! (n-i)!}[/tex]
    [itex]\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[/itex]

    So, for example, with k= 3
    [tex]\sum_{i=0}^3\begin{pmatrix}3 \\ i\end{pmatrix}f_{n+i}= f_n+ 3f_{n+1}+ 3f_{n+2}+ f_{n+3}[/tex]
     
  4. Feb 18, 2012 #3

    dba

    User Avatar

    Thank you very much.
    I understand this now :smile:
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook