Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof of this one

  1. Nov 5, 2004 #1
    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. jcsd
  3. Nov 5, 2004 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    This is just the binomial expansion of [itex](1 + 1)^n[/itex]
  4. Nov 5, 2004 #3
    Ok, that's something I already know, but I need to prove it using some properties of combination numbers, eg.

    \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)
  5. Nov 5, 2004 #4
    Let A be a set with n elements. How many elements does the powerset of A have?
  6. Nov 5, 2004 #5
    I can't imagine the "powerset of A"...
  7. Nov 5, 2004 #6
    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...
  8. Nov 5, 2004 #7
    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...
  9. Nov 5, 2004 #8


    User Avatar
    Science Advisor
    Homework Helper

    [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: Nov 5, 2004
  10. Nov 5, 2004 #9
    Thank you Galileo, I've already achieved this point, but I'm not able to edit it further...
  11. Nov 5, 2004 #10


    User Avatar
    Science Advisor
    Homework Helper

    Well, you have:
    [tex]{n \choose k} + {n \choose k+1} = {n+1 \choose k+1}[/tex]

    [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.
  12. Nov 6, 2004 #11
    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...
  13. Nov 6, 2004 #12


    User Avatar
    Science Advisor
    Homework Helper

    [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.
    [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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook