Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $L_n$ be the Lucas numbers, defined by $L_n = F_{n-1} + F_{n+1}$ where f is the Fibonacci numbers.

How to prove that

$L_{2n+1} = \displaystyle \sum_{k=0}^{\lfloor n + 1/2\rfloor}\frac{2n+1}{2n+1 - k}{2n+1 - k \choose k} $

share|cite|improve this question
Induction?${}{}$ – Gerry Myerson Jul 4 '11 at 6:09

The upper limit of the summation is simply $n$:$$L_{2n+1} = \sum\limits_{k=0}^n \frac{2n+1}{2n+1-k} {{2n+1-k}\choose{k}}.$$

Notice that as the index $k$ changes, the sum of the upper and lower numbers in the binomial coefficient remains constant at $2n+1$. In other words, ignoring for a moment the fractional coefficient, we're summing lower-left-to-upper-right diagonals in Pascal's triangle when it's written in rectangular form, as for instance shown at the top of this web page. It's well known that those sums are the Fibonacci numbers: $$F_{n+1} = \sum\limits_{k=0}^{\lfloor n/2 \rfloor} {{n-k}\choose{k}}.$$ (It's also not hard to prove this by induction, using the recursive definition of the Fibonacci numbers and the fact that ${{n}\choose{k}} = {{n-1}\choose{k}} + {{n-1}\choose{k-1}}$.) This suggests trying to manipulate the given summation into a form recognizable as the sum of two of these diagonal sums.

This works: $$\frac{2n+1}{2n+1-k} = 1 + \frac{k}{2n+1-k}$$ and $$\frac{k}{2n+1-k} {{2n+1-k}\choose{k}} = {{2n-k}\choose{k-1}},$$ so

$ \begin{align*} \sum\limits_{k=0}^n \frac{2n+1}{2n+1-k} {{2n+1-k}\choose{k}} &= \sum\limits_{k=0}^n \left(1 + \frac{k}{2n+1-k} \right) {{2n+1-k}\choose{k}}\\ &= \sum\limits_{k=0}^n \left[{{2n+1-k}\choose{k}} + {{2n-k}\choose{k-1}} \right]\\ &= \sum\limits_{k=0}^n {{2n+1-k}\choose{k}} + \sum\limits_{k=0}^n {{2n-k}\choose{k-1}}\\ &= \sum\limits_{k=0}^n {{2n+1-k}\choose{k}} + \sum\limits_{k=-1}^{n-1} {{2n-1-k}\choose{k}}\\ &= \sum\limits_{k=0}^n {{2n+1-k}\choose{k}} + \sum\limits_{k=0}^{n-1} {{2n-1-k}\choose{k}}\\ &= F_{2n+2} + F_{2n}\\ &=L_{2n+1}. \end{align*}$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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