# Sum involving binomial coefficients - generalisation of hockey stick identity? [duplicate]

This question already has an answer here:

I am trying to evaluate a sum involving binomial coefficients, and by some manipulations, I have reduced it to $$\sum_{i=0}^{n} \binom{n+i}{i} 2^{n-i}$$ where $$n$$ is a constant ($$n=1009$$ in my particular case). (This looks like the LHS of the Hockey Stick Identity, except for the presence of the $$2^{n-i}$$ term. I would also be interested in further generalisation, replacing the $$2$$ by an arbitrary constant).

To evaluate this, I attempted writing $$2^{n-i} = \sum_{k=0}^{n-i} \binom{n-i}{k}$$ which gave a more symmetric expression, but otherwise didn't seem to help much.

So, given that the answer (according to Mathematica) is $$4^n$$, how can this be proved?

## marked as duplicate by Mike Earnest, Jyrki Lahtonen, Nosrati, A. Pongrácz, DRFDec 8 '18 at 14:51

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• This problem also appeared at the following MSE link. – Marko Riedel Dec 7 '18 at 14:32

## 3 Answers

$$\text{Let } f(n)= \sum_{i=0}^{n} \binom{n+i}{i} 2^{n-i}.$$ $$f(n+1)=\sum_{i=0}^{n+1} \binom{n+i+1}{i} 2^{n+1-i}=\sum_{i=0}^{n+1} \binom{n+i}{i} 2^{n+1-i}+ \sum_{i=0}^{n+1} \binom{n+i}{i-1}2^{n+1-i}$$$$=\binom {2n+1}{n} + 2{\sum_{i=0}^{n} \binom{n+i}{i} 2^{n-i}}+ \sum_{i=0}^{n} \binom{n+i+1}{i}2^{n-i}$$$$=2f(n)+\frac{1}{2}\binom{2n+2}{n+1}+\frac{1}{2}\sum_{i=0}^{n} \binom{n+i+1}{i}2^{n+1-i}=2f(n)+\frac{1}{2}f(n+1)$$ $$\therefore f(n+1)=4f(n) \implies f(n)=4^{n-1}f(1)=4^n\ .$$ $$\blacksquare$$

Throw a fair coin repeatedly until the number of heads or the number of tails has exceeded $$n$$.

Let $$H$$ denote the number of heads and let $$T$$ denote the number of tails that have been thrown then.

In that situation $$H\neq T$$ so that $$P\left(H.

By symmetry $$P\left(H so we conclude that $$P\left(H.

Also we have $$P\left(H.

Proved is now that:

$$\sum_{i=0}^{n}\binom{n+i}{i}2^{-n-i}=1$$ or equivalently: $$\sum_{i=0}^{n}\binom{n+i}{i}2^{n-i}=2^{2n}=4^n$$

• Why the downvotes? Also on the other answers to this question? At least give an explanation for that. – drhab Dec 8 '18 at 9:45

$$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$$ $$$$\bbx{\mbox{Nothe that}\ \sum_{k = 0}^{n}{n + k \choose k}2^{n - k} = \left. 2^{n}\sum_{k = 0}^{n}{n + k \choose k}x^{k} \,\right\vert_{\ x\ =\ 1/2}}\label{1}\tag{1}$$$$

Let $$\ds{\mrm{f}\pars{x} \equiv \sum_{k = 0}^{n}{n + k \choose k}x^{k}}$$ such that

$$\ds{\bbox[#ffd,10px,border:1px groove navy] {\sum_{k = 0}^{n}{n + k \choose k}2^{n - k} = 2^{n}\,\mrm{f}\pars{1 \over 2}}\qquad}$$ and \begin{align} \mrm{f}'\pars{x} & = \sum_{k = 1}^{n}{\pars{n + k}! \over \pars{k - 1}!\, n!}x^{k - 1} = \sum_{k = 0}^{n - 1}{\pars{n + 1 + k}! \over k!\, n!}x^{k} \\[5mm] & = \sum_{k = 0}^{n - 1}\pars{n + 1 + k}{n + k \choose k}x^{k} \\[5mm] & = \sum_{k = 0}^{n}\pars{n + 1 + k}{n + k \choose k}x^{k} - \pars{2n + 1}{2n \choose n}x^{n} \\[5mm] & = \pars{n + 1}\,\mrm{f}\pars{x} + x\,\mrm{f}'\pars{x} - \pars{2n + 1}{2n \choose n}x^{n} \end{align} which leads to \begin{align} &\mrm{f}'\pars{x} - {n + 1 \over 1 - x}\,\mrm{f}\pars{x} = -\pars{2n + 1}{2n \choose n}{x^{n} \over 1 - x}\,,\qquad \left\{\begin{array}{lcl} \ds{\mrm{f}\pars{0}} & \ds{=} & \ds{1} \\[2mm] \ds{\mrm{f}\pars{1 \over 2}} & \ds{=} & \ds{\LARGE ?} \end{array}\right. \\[5mm] &\ \totald{\bracks{\pars{1 - x}^{n + 1}\,\mrm{f}\pars{x}}}{x} = -\pars{2n + 1}{2n \choose n}\pars{x - x^{2}}^{n} \\[1cm] &\ {1 \over 2^{n + 1}}\,\mrm{f}\pars{1 \over 2} - 1 \\ = &\ -\pars{2n + 1}{2n \choose n}\, \underbrace{\int_{0}^{1/2}\pars{x - x^{2}}^{n}\,\dd x} _{\ds{1/2 \over \pars{2n + 1}{2n \choose n}}} \implies\bbx{\mrm{f}\pars{1 \over 2} = 2^{n}} \end{align}
Then, $$\sum_{k = 0}^{n}{n + k \choose k}2^{n - k} = 2^{n}\,\mrm{f}\pars{1 \over 2} = \bbx{\large 4^{n}}$$

• +1 For some reason this nice answer was downvoted some minutes ago. – drhab Dec 8 '18 at 9:47
• Something within the context of the downvote: I just took a look at your profile and was impressed by the cartoon on it. A wise lesson for me (and others) and very actual right now. – drhab Dec 8 '18 at 9:54
• Thanks, @drhab Up and Down is MSE life somehow... – Felix Marin Dec 8 '18 at 17:14