# What is wrong with this proof about a sum of binomial coefficients?

I want to show that $\sum_{k=0}^n\binom{n+1}{k}=2^{n+1}-1$

Proof:

$$\sum_{k=0}^n\binom{n+1}{k} = \sum_{k=-1}^{n-1}\binom{n+1}{k+1} \;\; q:=k+1, \; r:=n+1$$ thus the sum equals $$\sum_{q=0}^{r-2}\binom{r}{q} = \sum_{q=0}^{r}\binom{r}{q} -\binom{r}{r-1} -\binom{r}{r} = 2^{r}-r-1 = 2^{n+1}-n-2$$ so clearly I did something wrong.

I tried to double-check everything but all steps seem OK to me.

Where did I go wrong?

• Did q and r get switched around? You define $q=k+1$, but $q$ appears in the top of the binomial coefficient in your second line whereas $k+1$ appears in the bottom of the binomial coefficient in your first line. – Mauve Jan 15 '18 at 14:14
• you are right, I edited the question so the q's and r's should be in place now – Travis Jan 15 '18 at 14:23

You made a mistake in your substitutions. If you let $q=k+1$, your lower limit is indeed $q=-1+1=0$. But your upper limit should be $q=(n-1)+1=n=r-1$ (instead of $r-2$). So you have
• I don't get it: if $r=n+1$, then $n = r-1$ and thus $n-1 = r-1-1 = r-2$ right? – Travis Jan 15 '18 at 14:28
• Yes, but that would be if you were trying to write the upper limit of the $k$'s in terms of $r$. You're now summing over $q$'s, and you need to add one to each of the limits because $q=k+1$. – Mauve Jan 15 '18 at 14:34