Proof by mathematical induction

[nuuskur]

Hello,

I need to prove the following:
\sum_{i=0}^n\binom{n}{i} = 2^n
by using something called mathematical induction. I understand, somewhat, what it is - we propose a statement and show that is true for n=1, then we assume that the statement is true for all n \in \mathbb{N}, which should also mean that the statement is true for n+1. This is what I have written down:

\binom{n+1}{0} + \binom{n+1}{1}+ . . .+ \binom{n+1}{n-1}+ \binom{n+1}{n}+ \binom{n+1}{n+1} = 2^{n+1}
which is
1 + (n+1) + \frac{n(n+1)}{2!}+ . . .+ \frac{n(n+1)}{2!}+ (n+1)+ 1 = 2^{n+1}
I can see a symmetry and I thought about calculating half and showing that it equals 2ⁿ, but that idea quickly died, since I don't know where the "half point" is in the sum.

What should I do?
Thanks in advance!

 

[Ray Vickson]

Hello,

I need to prove the following:
\sum_{i=0}^n\binom{n}{i} = 2^n
by using something called mathematical induction. I understand, somewhat, what it is - we propose a statement and show that is true for n=1, then we assume that the statement is true for all n \in \mathbb{N}, which should also mean that the statement is true for n+1. This is what I have written down:

\binom{n+1}{0} + \binom{n+1}{1}+ . . .+ \binom{n+1}{n-1}+ \binom{n+1}{n}+ \binom{n+1}{n+1} = 2^{n+1}
which is
1 + (n+1) + \frac{n(n+1)}{2!}+ . . .+ \frac{n(n+1)}{2!}+ (n+1)+ 1 = 2^{n+1}
I can see a symmetry and I thought about calculating half and showing that it equals 2ⁿ, but that idea quickly died, since I don't know where the "half point" is in the sum.

What should I do?
Thanks in advance!

Given the truth of the statement for $n=k$, you need to prove it for $n= k+1$. To do that, you need to know how $\binom{n+1}{r}$ relates to $\binom{n}{s}$. Use Pascal's Triangle; look it up if you have not heard of it.

 

[nuuskur]

I looked it up Here and saw the Pascal's rule, according to which I could state that:
\binom{n+1}{k} = \binom{n}{k-1}+ \binom{n}{k}, n \geq 0 \land k \in [1, n]
(k can't be zero, right? If it is then _nC_k-1=ø)

If I plug in k=n I get:
Left side:
\frac{(n+1)!}{n!}= n+1
Right side:
\frac{n!}{(n-1)!}+ \frac{n!}{n!}= n+1
Cannot understand how this helps me come to the conclusion in the first statement(the original assignment). What exactly does that equality show?

 

[Fredrik]

It doesn't look like you're trying to use induction. The idea between induction is this: Suppose that for each natural number n, P(n) is a statement about n. You can prove that P(n) is true for all n, by proving only two statements:

1. P(0)
2. For all n, if P(n) then P(n+1).

In your case, P(n) is the statement $\sum_{i=1}^n \binom n i=2^n$. You need to prove P(0), i.e. that $\sum_{i=0}^0 \binom 0 i =2^0$. This is of course easy. Then you let n be an arbitrary natural number and try to prove that if P(n) then P(n+1). So you have to use $\sum_{i=0}^n \binom n i =2^n$ to prove $\sum_{i=0}^{n+1}\binom{n+1}{i}=2^{n+1}$.