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