Relation between sum of combinations

Question

I just realised the following identity: $$\sum_{i=0}^n {2n+1\choose i}=\sum_{i=0}^{2n}{2n\choose i}.$$ Is that correct? Has this been already proved?

Answer 1

Yes, the identity holds and, as remarked by Ted Shifrin, it is equivalent to $\displaystyle 2^{2n} = \frac12\cdot 2^{2n+1}$.

By the binomial theorem, we have that that $$2^{2n}=(1+1)^{2n}=\sum_{i=0}^{2n}{2n\choose i}$$ and, since $\binom{m}{k}=\binom{m}{m-k}$, $$ \begin{align}2^{2n+1}&=(1+1)^{2n+1}=\sum_{i=0}^{2n+1} {2n+1\choose i}=\sum_{i=0}^{n} {2n+1\choose i}+\sum_{i=n+1}^{2n+1} {2n+1\choose i}\\&=\sum_{i=0}^{n} {2n+1\choose i}+\sum_{i=n+1}^{2n+1} {2n+1\choose 2n+1-i} =\sum_{i=0}^{n} {2n+1\choose i}+\sum_{j=0}^{n} {2n+1\choose j}\\&=2\sum_{i=0}^{n} {2n+1\choose i}.\end{align}$$

Answer 2

$\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}$ \begin{align} \sum_{i = 0}^{n}{2n + 1 \choose i} & = {1 \over 2}\sum_{i = 0}^{2n + 1}{2n + 1 \choose i} = {1 \over 2} + {1 \over 2}\sum_{i = 0}^{2n} \bracks{{2n \choose i} + {2n \choose i - 1}} \\[5mm] & = {1 \over 2} + {1 \over 2}\sum_{i = 0}^{2n}{2n \choose i} + {1 \over 2}\sum_{i = 1}^{2n}{2n \choose i - 1} = {1 \over 2} + {1 \over 2}\sum_{i = 0}^{2n}{2n \choose i} + {1 \over 2}\sum_{i = 0}^{2n - 1}{2n \choose i} \\[5mm] & = {1 \over 2} + {1 \over 2}\sum_{i = 0}^{2n}{2n \choose i} + {1 \over 2}\bracks{\sum_{i = 0}^{2n}{2n \choose i} - 1} = \bbx{\sum_{i = 0}^{2n}{2n \choose i}} \end{align}