0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mauve Jan 15 '18 at 14:14
  • $\begingroup$ you are right, I edited the question so the q's and r's should be in place now $\endgroup$ – Travis Jan 15 '18 at 14:23
1
$\begingroup$

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

\begin{align}\sum_{q=0}^{r-1}\binom{r}{q} = \sum_{q=0}^{r}\binom{r}{q}-\binom{r}{r}=2^r-1=2^{n+1}-1. \end{align}

$\endgroup$
  • $\begingroup$ I don't get it: if $r=n+1$, then $n = r-1$ and thus $n-1 = r-1-1 = r-2$ right? $\endgroup$ – Travis Jan 15 '18 at 14:28
  • 1
    $\begingroup$ 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$. $\endgroup$ – Mauve Jan 15 '18 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.