Proof of this one

  • Thread starter twoflower
  • Start date
  • #1
368
0
Hi all,

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

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.
 

Answers and Replies

  • #2
quasar987
Science Advisor
Homework Helper
Gold Member
4,783
18
This is just the binomial expansion of [itex](1 + 1)^n[/itex]
 
  • #3
368
0
Ok, that's something I already know, but I need to prove it using some properties of combination numbers, eg.

[tex]
\left(
\begin{array}{cc}
0\\
0\end{array}
\right) = 1[/tex]

[tex]\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)
[/tex]
 
  • #4
695
0
Let A be a set with n elements. How many elements does the powerset of A have?
 
  • #5
368
0
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"...
 
  • #6
695
0
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
368
0
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
Galileo
Science Advisor
Homework Helper
1,989
6
Hint:
[tex]\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[/tex]

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

[tex]\sum_{k=0}^{n}{n \choose k}=2^n[/tex]
and the identity:

[tex]\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)[/tex]
 
Last edited:
  • #9
368
0
Thank you Galileo, I've already achieved this point, but I'm not able to edit it further...
 
  • #10
Galileo
Science Advisor
Homework Helper
1,989
6
Well, you have:
[tex]{n \choose k} + {n \choose k+1} = {n+1 \choose k+1}[/tex]

and
[tex]\sum_{k=0}^{n}{n+1 \choose k}[/tex]
in the expression so we can almost put it together.
Why not sum over
[tex]\sum_{k=0}^{n}{n+1 \choose k+1}[/tex]
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
368
0
However I tried to use the equality, I only get to this point:

[tex]
\sum_{k=0}^{n}{n \choose k-1} - \sum_{k=0}^{n}{n \choose k+1} + 1 = 0
[/tex]

which I'm not able to go on with...
 
  • #12
Galileo
Science Advisor
Homework Helper
1,989
6
[tex]\sum_{k=0}^{n}{n+1 \choose k+1}=\sum_{k=0}^{n}{n \choose k}+\sum_{k=0}^{n}{n \choose k+1}[/tex]
This is obtained by simply using that identity.
Now
[tex]\sum_{k=0}^{n}{n \choose k}=2^n[/tex]
according to our induction hypothesis.

By the way:[itex]{n \choose k}=0[/itex] if k>n.
 

Related Threads on Proof of this one

  • Last Post
Replies
4
Views
2K
Replies
1
Views
1K
Replies
2
Views
1K
Replies
2
Views
679
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
14
Views
2K
Top