# Induction Proofs

1. Jun 10, 2015

### Keen94

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)
Then
(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. Jun 10, 2015

### wabbit

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
3. Jun 10, 2015

### Keen94

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.

4. Jun 10, 2015

### Ray Vickson

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

Newton discovered that result in 1665, before age 25.