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?

  • 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\;.$