# Proof of this one

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.

Thank you.

quasar987
Homework Helper
Gold Member
This is just the binomial expansion of $(1 + 1)^n$

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)$$

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

Muzza said:
Let A be a set with n elements. How many elements does the powerset of A have?
I can't imagine the "powerset of A"...

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...

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...

Galileo
Homework Helper
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:
Thank you Galileo, I've already achieved this point, but I'm not able to edit it further...

Galileo
Homework Helper
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.

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...

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}$$
$$\sum_{k=0}^{n}{n \choose k}=2^n$$
By the way:${n \choose k}=0$ if k>n.