1
$\begingroup$

$${n \choose n-1} + {n+1 \choose n-2} + {n+2 \choose n-3} + \cdots + {2n - 1 \choose 0}$$

For the above series, does a closed form exist?

  • 0
    I'd say $\frac{2^{-n}\left(-(3-\sqrt{5})^n+(3+\sqrt{5})^n\right)}{\sqrt{5}}$ is a closed form.2012-07-01
  • 1
    @Julian: That's more of an answer than a comment.2012-07-01

1 Answers 1

5

Your series is

$$\sum_{k=0}^{n-1}\binom{n+k}{n-k-1}=\sum_{k=0}^{n-1}\binom{2n-1-k}k\;,$$

which is the special case of the series

$$\sum_{k\ge 0}\binom{m-k}k$$

with $m=2n-1$. It’s well-known (and easy to prove by induction) that

$$\sum_{k\ge 0}\binom{m-k}k=f_{m+1}\;,$$

where $f_m$ is the $m$-th Fibonacci number: $f_0=0,f_1=1$, and $f_n=f_{n-1}+f_{n-2}$ for $n>1$. Thus, the sum of your series is $f_{2n}$.

The Binet formula gives a closed form for $f_{2n}$: $$f_{2n}=\frac{\varphi^{2n}-\hat\varphi^{2n}}{\sqrt5}\;,$$ where $\varphi=\frac12\left(1+\sqrt5\right)$ and $\hat\varphi=\frac12\left(1-\sqrt5\right)$. A computationally more convenient expression is $$f_{2n}=\left\lfloor\frac{\varphi^{2n}}{\sqrt5}+\frac12\right\rfloor\;.$$