1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Induction Proofs

  1. Jun 10, 2015 #1
    1. The problem statement, all variables and given/known data
    Prove that ∑nj=0 n C r = 2n

    2. Relevant equations
    Defn. of a combination.
    Defn. of mathematical induction.

    3. The attempt at a solution
    The formula is true for n=1
    2=∑j=01 n C r
    = 1 C 0 +1 C 1
    =1 + 1
    = 2
    Now assume that for some k∈ℕ and 0≤ j ≤ k we have
    2k = ∑kj=0 (k C j)
    (2)(2k)=2k+1= (2)kj=0 (k C j)

    LHS= ∑kj=0 (k C j) + ∑kj=0 (k C j)

    LHS= ∑kj=0 (k C j) + ∑k+1j=0 (k C j-1)

    LHS= ∑kj=0 (k C j) + ∑kj=0 (k C j-1) + (k+1 C k+1)

    LHS= ∑kj=0 [ (k C j) + (k Cj-1) ] +(k+1 C k+1)

    LHS= ∑kj=0 (k+1 C j) + (k+1 C k+1)

    LHS= ∑k+1j=0 (k+1 C j)

    Does everything check? In addition, how was this formula discovered? How do people even find these things? Thanks again for the help guys and gals.
    Last edited: Jun 10, 2015
  2. jcsd
  3. Jun 10, 2015 #2


    User Avatar
    Gold Member

    Seems OK, although it would be cleaner to adjust the ## j=0 ## starting point in some of your sums - these work if you define ## _k C _j= 0## for ## j=-1 ## but if you are using that you should say so.

    Otherwise I don't know how it was discovered but one way to see it directly is to note that ## _n C _k ## is the number of subsets of ## k ## elements of a set having ## n ## elements, and ## 2^n ## is the number of all subsets of a set having ## n ## elements.
    Last edited: Jun 10, 2015
  4. Jun 10, 2015 #3
    thanks for the reply. I forgot that nCr is the number of subsets of k elements of a set of n elements. I've seen other proofs for that.
  5. Jun 10, 2015 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    People discover these thing by first discovering the binomial theorem
    [tex] (1+x)^n = \sum_{k=0}^m {}_nC_k \, x^k [/tex]
    and then putting ##x = 1##.

    Newton discovered that result in 1665, before age 25.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted