Proof of Equality: Summation & 2^n

[twoflower]

Hi all,

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

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.

 

[quasar987]

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

 

[twoflower]

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

<br /> \left(<br /> \begin{array}{cc}<br /> 0\\<br /> 0\end{array}<br /> \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)<br />

 

[Muzza]

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

 

[twoflower]

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

 

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

 

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

 

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

 

[twoflower]

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

 

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

 

[twoflower]

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

<br /> \sum_{k=0}^{n}{n \choose k-1} - \sum_{k=0}^{n}{n \choose k+1} + 1 = 0<br />

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