0
$\begingroup$

Prove by mathematical induction for all natural numbers $n$:

$$\sum_{k=0}^{n} \binom{n}{k}=2^n$$

thus is it sufficient to show that (but I think I made a mistake) thus how to do it properly?

$$2^n+\binom{n+1}{n+1}=2^{n+1}$$

$\endgroup$
  • $\begingroup$ The problem is that the first part of your sum does not add up to $2^n$. $\endgroup$ – user10444 Feb 15 '15 at 19:23
  • $\begingroup$ how come? the first part is copied directly from the question $\endgroup$ – kurkowski Feb 15 '15 at 19:25
  • $\begingroup$ See the answer below $\endgroup$ – user10444 Feb 15 '15 at 19:26
  • $\begingroup$ The assertion that $2^n + \binom{n + 1}{n + 1} = 2^{n + 1}$ is incorrect: $2^n + \binom{n + 1}{n + 1} = 2^n + 1$. $\endgroup$ – N. F. Taussig Feb 15 '15 at 19:28
2
$\begingroup$

Not quite, because ${n+1\choose n+1}=1$. Combinatorically, is it easy to see that ${n+1\choose k}={n\choose k}+{n\choose k-1}$ (we either include the last element or we don't). From here on the proof is easy because (using the induction hypothesis):

$\sum_{k=0}^{n+1} {n+1\choose k}=\sum_{k=0}^{n+1} {n\choose k}+{n\choose k-1}=\sum_{k=0}^{n+1} {n\choose k}+\sum_{k=0}^{n+1} {n\choose k-1}=2^n+2^n=2^{n+1}$

Because ${n\choose -1}={n\choose n+1}=0$ (it's impossible to choose -1 or n+1 elements out of n).

$\endgroup$
1
$\begingroup$

Note that $$\sum_{k=0}^{n+1} \begin{pmatrix} n+1 \\ k\end{pmatrix} = \begin{pmatrix} n+1 \\ n+1\end{pmatrix} + \underbrace{\sum_{k=0}^n \begin{pmatrix} n+1 \\ k\end{pmatrix}}_{\neq 2^n}.$$

Alternatively, note that $\begin{pmatrix} n+1 \\ n+1\end{pmatrix} = 1$, and that $2^{n+1} \neq 2^n + 1$.

$\endgroup$
  • $\begingroup$ thus how to approach the inductional proof? $\endgroup$ – kurkowski Feb 15 '15 at 19:26
0
$\begingroup$

See the answer of Arkamis to find your mistake.

Under the convention that $\binom{n}{k}=0$ if $k\notin\left\{ 0,\dots,n\right\} $ we have:

$$\sum_{k\in\mathbb{Z}}\binom{n+1}{k}=\sum_{k\in\mathbb{Z}}\left[\binom{n}{k-1}+\binom{n}{k}\right]=\sum_{k\in\mathbb{Z}}\binom{n}{k-1}+\sum_{k\in\mathbb{Z}}\binom{n}{k}=2^{n}+2^{n}=2^{n+1}$$

$\endgroup$
0
$\begingroup$

Not quite because you are missing the $n+1$ in all the sum. Anyway $2^n+1\neq 2^{n+1}$. The key is to use $\binom{n+1}{k+1}=\binom{n}{k+1}+\binom{n}{k}$.

$\endgroup$

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.