# Proof of this one

1. Nov 5, 2004

### twoflower

Hi all,

I don't know how to prove this equality:
$$\sum_{k=0}^n \left(\begin{array}{cc}n\\k \end{array}\right) = 2^n$$

I tried it many times, but never achieved the result. I used induction to do the proof, but no success.

Would somebody help please?

Thank you.

2. Nov 5, 2004

### quasar987

This is just the binomial expansion of $(1 + 1)^n$

3. Nov 5, 2004

### twoflower

Ok, that's something I already know, but I need to prove it using some properties of combination numbers, eg.

$$\left( \begin{array}{cc} 0\\ 0\end{array} \right) = 1$$

$$\left(\begin{array}{cc}n\\k\end{array}\right) + \left(\begin{array}{cc}n\\k+1\end{array}\right) = \left(\begin{array}{cc}n+1\\k+1\end{array}\right)$$

4. Nov 5, 2004

### Muzza

Let A be a set with n elements. How many elements does the powerset of A have?

5. Nov 5, 2004

### twoflower

I can't imagine the "powerset of A"...

6. Nov 5, 2004

### Muzza

The powerset of A is the set of all subsets of A.

E.g., let A = {1,2}. Then the powerset of A = { {}, {1}, {2}, {1,2} }.

If one could count the cardinality of the powerset of A in two different ways, one would immediately know that the resulting numbers would be equal...

7. Nov 5, 2004

### twoflower

Ok, now I know what you mean with "powerset", my translator gave me completely different meaning...Yes I know that it is 2^n, but...I need to prove it with induction...

8. Nov 5, 2004

### Galileo

Hint:
$$\sum_{k=0}^{n+1} {n+1 \choose k}=\sum_{k=0}^{n}{n+1 \choose k}+{n+1 \choose n+1}=\sum_{k=0}^{n}{n+1 \choose k}+1$$

You want to manipulate your expression in such a way so you can use your induction hypothesis:

$$\sum_{k=0}^{n}{n \choose k}=2^n$$
and the identity:

$$\left(\begin{array}{cc}n\\k\end{array}\right) + \left(\begin{array}{cc}n\\k+1\end{array}\right) = \left(\begin{array}{cc}n+1\\k+1\end{array}\right)$$

Last edited: Nov 5, 2004
9. Nov 5, 2004

### twoflower

Thank you Galileo, I've already achieved this point, but I'm not able to edit it further...

10. Nov 5, 2004

### Galileo

Well, you have:
$${n \choose k} + {n \choose k+1} = {n+1 \choose k+1}$$

and
$$\sum_{k=0}^{n}{n+1 \choose k}$$
in the expression so we can almost put it together.
Why not sum over
$$\sum_{k=0}^{n}{n+1 \choose k+1}$$
it's almost the same as the previous sum. You are missing a term (which you'll have to add) and it gives an extra term (which you'll have to subtract).
Then you can apply the identity.

11. Nov 6, 2004

### twoflower

However I tried to use the equality, I only get to this point:

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

which I'm not able to go on with...

12. Nov 6, 2004

### Galileo

$$\sum_{k=0}^{n}{n+1 \choose k+1}=\sum_{k=0}^{n}{n \choose k}+\sum_{k=0}^{n}{n \choose k+1}$$
This is obtained by simply using that identity.
Now
$$\sum_{k=0}^{n}{n \choose k}=2^n$$
according to our induction hypothesis.

By the way:${n \choose k}=0$ if k>n.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook