Closed formula for $\sum_{k=0}^{n}\binom{n+k}{k}x^k$

Solution 1:

$$\sum_{k=0}^{n}\binom{n+k}{k}x^k = \sum_{k=0}^{n}x^k\cdot[t^n](1+t)^{n+k}=[t^n](1+t)^n\sum_{k=0}^{n}(x(1+t))^k=[t^n](1+t)^n\frac{1-x^n(1+t)^n}{1-x(1+t)}$$ if $x=\frac{1}{2}$ equals $$ [t^n](1+t)^n \frac{1-\left(\frac{1+t}{2}\right)^n}{\frac{1-t}{2}}=\frac{2}{2^n}[t^n]\frac{2^n(1+t)^n-(1+t)^{2n}}{1-t}=\frac{2}{2^n}\sum_{k=0}^{n}[t^k]\left(2^n(1+t)^n-(1+t)^{2n}\right)$$ or $$ \frac{2}{2^n}\sum_{k=0}^{n}\left(2^n\binom{n}{k}-\binom{2n}{k}\right)=\frac{2}{2^n}\left(4^n-\frac{4^n}{2}\right)=\color{red}{2^n}. $$

Solution 2:

I could not find any closed form of this expression, but a recurrence relation would be like that:

$$\color{blue}{S_n}:=\sum_{k=0}^{n}\binom{n+k}{k}x^k=\frac{1}{x^n}\sum_{k=n}^{2n}\binom{k}{n}x^k$$$$=\frac{1}{x^n}\left[\sum_{k=n}^{2n}\binom{k+1}{n+1}x^k-\sum_{k=n}^{2n}\binom{k}{n+1}x^k \right]$$$$=\frac{1}{x^n}\left[\frac{1}{x}\sum_{k=n+1}^{2n+1}\binom{k}{n+1}x^k-\sum_{k=n}^{2n}\binom{k}{n+1}x^k \right]$$$$=\frac{1}{x^n}\left[\left(\frac{1}{x}-1\right)\sum_{k=n+1}^{2n}\binom{k}{n+1}x^k+\binom{2n+1}{n+1}x^{2n}\right]$$$$=\frac{1}{x^n}\left[\left(\frac{1}{x}-1\right)\sum_{k=n+1}^{2(n+1)}\binom{k}{n+1}x^k+\binom{2n+1}{n+1}x^{2n}-\left(\frac{1}{x}-1\right)\left(\binom{2n+1}{n+1}x^{2n}+\binom{2n+2}{n+1}x^{2n+1}\right)\right]$$$$=\frac{1}{x^n}\left[\left( 1-x \right)x^{n}S_{n+1}+x^{\left(2n-1\right)}\left(2x^{2}-1\right)\binom{2n+1}{n}\right]$$$$=\color{blue}{\left(1-x\right)S_{n+1}+x^{\left(n-1\right)}\left(2x^{2}-1\right)\binom{2n+1}{n}}$$

Using this recurrence relation we have:

$$\bbox[5px,border:2px solid #00A000]{S_{n}=\frac{S_{n-1}-x^{\left(n-2\right)}\left(2x^{2}-1\right)\binom{2(n-1)+1}{n}}{\left(1-x\right)}}\; \;\;\;\;\;\;\;\;\;\;\; \left(n \in \mathbb N^{*}\right)$$

Another family of this expression:

$$\color{blue}{S_n}:=\sum_{k=0}^{n}\binom{2n-k}{n}x^k=x^{2n}\sum_{k=n}^{2n}\binom{k}{n}\frac{1}{x^k}=x^{2n}\left[\sum_{k=n}^{2n}\binom{k+1}{n+1}\frac{1}{x^k}-\sum_{k=n}^{2n}\binom{k}{n+1}\frac{1}{x^k}\right]$$$$=x^{2n}\left[x\sum_{k=n+1}^{2n+1}\binom{k}{n+1}\frac{1}{x^{k}}-\sum_{k=n}^{2n}\binom{k}{n+1}\frac{1}{x^k}\right]$$$$=x^{2n}\left [x\sum_{k=n+1}^{2n}\binom{k}{n+1}\frac{1}{x^{k}}-\sum_{k=n+1}^{2n}\binom{k}{n+1}\frac{1}{x^k}+\binom{2n+1}{n+1}\frac{1}{x^{2n}}\right]$$$$=x^{2n}\left [\left(x-1\right)\sum_{k=n+1}^{2n}\binom{k}{n+1}\frac{1}{x^{k}}+\binom{2n+1}{n+1}\frac{1}{x^{2n}}\right]$$$$=x^{2n}\left[\left(x-1\right)\sum_{k=n+1}^{2(n+1)}\binom{k}{n+1}\frac{1}{x^{k}}+\binom{2n+1}{n+1}\frac{1}{x^{2n}}-\left(x-1\right)\left(\binom{2n+1}{n+1}\frac{1}{x^{2n+1}}+\binom{2n+2}{n+1}\frac{1}{x^{2n+2}}\right)\right]$$$$=x^{2n}\left[\left(x-1\right)\frac{S_{n+1}}{x^{2(n+1)}}+\binom{2n+1}{n}\frac{1}{x^{2n}}-\left(x-1\right)\left(x+2\right)\binom{2n+1}{n}\frac{1}{x^{2n+2}}\right]$$$$=x^{2n}\left[\left(x-1\right)\frac{S_{n+1}}{x^{2(n+1)}}-\left(x-2\right)\binom{2n+1}{n}\frac{1}{x^{2n+2}}\right]$$$$=\color{blue}{\frac{\left(x-1\right)S_{n+1}-\left(x-2\right)\binom{2n+1}{n}}{x^{2}}}$$

$$\bbox[5px,border:2px solid #00A000]{S_n=\frac{\left(x-1\right)S_{n+1}-\left(x-2\right)\binom{2n+1}{n}}{x^{2}}} \; \;\;\;\;\;\;\;\;\;\;\; \left(n \in \mathbb N\right)$$

Setting $x \mapsto 2$ in the above relation yields the expression which has been duscussed earlier .

Or:

$$\color{red}{S_n}:=\sum_{k=0}^{n}\binom{2n-k}{n}2^k=2^{2n}\sum_{k=n}^{2n}\binom{k}{n}\frac{1}{2^k}=2^{2n}\left[\sum_{k=n}^{2n}\binom{k+1}{n+1}\frac{1}{2^k}-\sum_{k=n}^{2n}\binom{k}{n+1}\frac{1}{2^k}\right]$$$$=2^{2n}\left[2\sum_{k=n+1}^{2n+1}\binom{k}{n+1}\frac{1}{2^{k}}-\sum_{k=n}^{2n}\binom{k}{n+1}\frac{1}{2^k}\right]$$$$=2^{2n}\left[2\sum_{k=n+1}^{2n}\binom{k}{n+1}\frac{1}{2^{k}}-\sum_{k=n+1}^{2n}\binom{k}{n+1}\frac{1}{2^k}+\binom{2n+1}{n+1}\frac{1}{2^{2n}}\right]$$$$=2^{2n}\left[\sum_{k=n+1}^{2n}\binom{k}{n+1}\frac{1}{2^{k}}+\binom{2n+1}{n+1}\frac{1}{2^{2n}}\right]$$$$=2^{2n}\left[\sum_{k=n+1}^{2(n+1)}\binom{k}{n+1}\frac{1}{2^{k}}+\binom{2n+1}{n+1}\frac{1}{2^{2n}}-\binom{2n+1}{n+1}\frac{1}{2^{2n+1}}-\binom{2n+2}{n+1}\frac{1}{2^{2n+2}}\right]$$$$=2^{2n}\left[\frac{S_{n+1}}{2^{2(n+1)}}+\binom{2n+1}{n}\frac{1}{2^{2n+1}}-\binom{2n+1}{n}\frac{1}{2^{2n+1}}\right]=\color{red}{\frac{S_{n+1}}{2^{2}}}$$

Since $S_0=1$, using this recurrence relation implies:

$$\bbox[5px,border:2px solid #00A000]{S_n=2^{2n}}$$