Prove that $\sum_{k=1}^n\binom{2n-1}{n-k}=4^{n-1}$.

Question

Let $S_n=\sum_{k=1}^n\binom{2n-1}{n-k}$, I tried to prove that $S_{n+1}=4S_n$: \begin{align} S_{n+1}&=\sum_{k=1}^{n+1}\binom{2n+1}{n+1-k}\\ &=\sum_{k=0}^{n}\binom{2n+1}{n-k}=\text{stuck} \end{align} Maybe some $\Gamma$ functions? $$S_n=\Gamma(2n)\sum_{k=1}^n\frac{1}{\Gamma(n-k+1)\Gamma(n+k)}=?$$ Any hint will be appreciated.

Answer 1

Hint: the sum of all the binomial coefficients $\binom{2n-1}{k}$ for $0\le k\le 2n-1$ is equal to $2^{2n-1}=2\cdot 4^{n-1}$. But you are only adding up half of the coefficients, in the range $0\le k\le n-1$.

Answer 2

Since you are aware of the gamma function and its existence, I'm going to assume that you are also well aware of the hockey stick identity.$$\binom {n-1}{r-1}+\binom {n-1}{r}=\binom nr\tag1$$Which can be proven algebraically by expanding both sides and seeing that they're both equal. Starting from where you left off, we use the (1) to break the sums up in terms of $\binom {2n-1}k$ where $1\leq k\leq n$. The first expansion yields$$\begin{align*}S_{n+1} & =\color{blue}{\binom {2n+1}n}+\color{red}{\binom {2n+1}{n-1}}+\cdots+\color{brown}{\binom {2n+1}1}+\color{green}{\binom {2n+1}0}\\ & =\color{blue}{\binom {2n}{n-1}+\binom {2n}n}+\color{red}{\binom {2n}{n-2}+\binom{2n}{n-1}}+\cdots+\color{brown}{\binom{2n}0+\binom{2n}1}+\color{green}{\binom {2n+1}0}\\ & =\binom {2n}n+2\binom {2n}{n-1}+2\binom {2n}{n-2}+\cdots+2\binom {2n}1+2\binom {2n}0\end{align*}$$Note that the last term appears because $\binom {2n}0=\binom{2n+1}0=1$. With that out of the way, we again use (1) to expand $S_{n+1}$. The reason behind this is because we have $S_n$ defined as$$S_n=\sum\limits_{k=1}^n\binom {2n-1}{n-k}\tag2$$So if we can get the top term of the binomial coefficient to equal $2n-1$, then we can use (2) to write a recurrence relation. From which we can easily solve for $S_{n+1}$. Hockey stick identity gives us$$\begin{align*}S_{n+1} & =\binom {2n}n+\color{blue}{2\binom {2n}{n-1}}+\color{red}{2\binom {2n}{n-2}}+\cdots+\color{green}{2\binom{2n}1}+2\binom {2n}0\\ & =\binom {2n}n+\color{blue}{2\left[\binom {2n-1}{n-2}+\binom {2n-1}{n-1}\right]}+\color{red}{2\left[\binom {2n-1}{n-3}+\binom {2n-1}{n-2}\right]}+\\ & \qquad\qquad\qquad\qquad\qquad\qquad\qquad\cdots+\color{green}{2\left[\binom {2n-1}0+\binom {2n-1}1\right]}+2\\ & =\binom {2n}n+4\sum\limits_{k=1}^n\binom {2n-1}{n-k}-2\binom {2n-1}{n-1}\\ & =\binom {2n}n-2\binom {2n-1}{n-1}+4S_n\end{align*}$$The right-hand side can be reduced to $4S_n$ for all $n>0$ and $n$ is an integer. To prove that the two binomials reduce to zero, we can show that they are equal to each other. Using the basic definition of the binomial coefficient that we all learned in kindergarden, the simplification is as follows$$\begin{align*}\binom {2n}n & =\frac {(2n)!}{(n!)^2}\\ & =\frac {2n}n\frac {(2n-1)!}{n!(n-1)!}\\ & =2\left[\frac {(2n-1)!}{n!(n-1)!}\right]\\ & =2\binom {2n-1}{n-1}\tag3\end{align*}$$Hence, by (3), we have$$\begin{align*}S_{n+1} & =4S_n\qquad\implies\qquad S_n=4^{n-1}\end{align*}$$

Answer 3

If $S_n =\sum_{k=1}^n\binom{2n-1}{n-k} $, then, putting $n-k+1$ for $k$, $S_n =\sum_{k=1}^n\binom{2n-1}{n-(n-k+1)} =\sum_{k=1}^n\binom{2n-1}{k-1} =\sum_{k=0}^{n-1}\binom{2n-1}{k} $.

Also, $S_n =\sum_{k=1}^n\binom{2n-1}{(2n-1)-(n-k)} =\sum_{k=1}^n\binom{2n-1}{n+k-1} =\sum_{k=n}^{2n-1}\binom{2n-1}{k} $.

Therefore $2S_n =\sum_{k=0}^{n-1}\binom{2n-1}{k}+\sum_{k=n}^{2n-1}\binom{2n-1}{k} =\sum_{k=0}^{2n-1}\binom{2n-1}{k} =2^{2n-1} $ by the binomial theorem.

Therefore $S_n =2^{2n-2} $