How do I show that the following sum is equal to the fibonacci numbers? Atleast numerical evaluation suggests it is $$ \sum_{k=0}^{\lceil n/2\rceil}\binom{n+1-k}{n+1-2k} $$ The image below shows how it moves through pascals triangle, it starts at the right $1$ on line $n+1$, if the upper line is $n=0$. enter image description here

  • 2
    $\begingroup$ Use induction, showing that your formula satisfies the Fibonacci recurrence relation $F(n+1) = F(n) + F(n-1)$. $\endgroup$ – Bob Krueger Apr 5 '15 at 19:52
  • $\begingroup$ @Bob1123 right, that was pretty obvious. Oh well $\endgroup$ – Alice Ryhl Apr 5 '15 at 19:54
  • $\begingroup$ It may be easy to show that the relation is true, but it does not make the identity obvious. Take a look at the last picture here. $\endgroup$ – Bob Krueger Apr 5 '15 at 20:03

It's clear that: $$ \binom{n+1-k}{n+1-2k}=\binom{n+1-k}{k} $$ and there is a solution here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.