Induction Proofs Homework: Prove ∑nj=0 n C r = 2n

[Keen94]

Homework Statement

Prove that ∑ⁿ_j=0 n C r = 2ⁿ

Homework Equations

Def^n. of a combination.
Def^n. of mathematical induction.

The Attempt at a Solution

The formula is true for n=1
2=∑_j=0¹ n C r
= 1 C 0 +1 C 1
=1 + 1
= 2
Now assume that for some k∈ℕ and 0≤ j ≤ k we have
2^k = ∑^k_j=0 (k C j)
Then
(2)(2^k)=2^k+1= (2)∑^k_j=0 (k C j)

LHS= ∑^k_j=0 (k C j) + ∑^k_j=0 (k C j)

LHS= ∑^k_j=0 (k C j) + ∑^k+1_j=0 (k C j-1)

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

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

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

LHS= ∑^k+1_j=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.

 

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

 

[Keen94]

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.

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.

 

[Ray Vickson]

Homework Statement

Prove that ∑ⁿ_j=0 n C r = 2ⁿ

Homework Equations

Def^n. of a combination.
Def^n. of mathematical induction.

The Attempt at a Solution

The formula is true for n=1
2=∑_j=0¹ n C r
= 1 C 0 +1 C 1
=1 + 1
= 2
Now assume that for some k∈ℕ and 0≤ j ≤ k we have
2^k = ∑^k_j=0 (k C j)
Then
(2)(2^k)=2^k+1= (2)∑^k_j=0 (k C j)

LHS= ∑^k_j=0 (k C j) + ∑^k_j=0 (k C j)

LHS= ∑^k_j=0 (k C j) + ∑^k+1_j=0 (k C j-1)

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

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

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

LHS= ∑^k+1_j=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.

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.