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} $

  • 2
    $\begingroup$ Induction?${}{}$ $\endgroup$ – 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*}$


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.