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

• Keen94
So, people can find these things when they are very young!In summary, the formula ∑nj=0 n C r = 2n was proven using mathematical induction. It was likely discovered by first discovering the binomial theorem and then substituting x = 1. This result was originally discovered by Newton at a young age.
Keen94

## Homework Statement

Prove that ∑nj=0 n C r = 2n

## Homework Equations

Defn. of a combination.
Defn. of mathematical induction.

## 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:
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:
wabbit said:
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.

Keen94 said:

## Homework Statement

Prove that ∑nj=0 n C r = 2n

## Homework Equations

Defn. of a combination.
Defn. of mathematical induction.

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

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.

## 1. What is an induction proof?

An induction proof is a mathematical method used to prove a statement for all values of a variable. It involves showing that the statement is true for a base case, typically n=0 or n=1, and then using the assumption that the statement is true for some value of n, to prove that it is also true for the next value of n.

## 2. How do you prove a statement using mathematical induction?

To prove a statement using mathematical induction, you must first show that it is true for the base case. Then, you assume that the statement is true for some value of n. Using this assumption, you must show that the statement is also true for the next value of n. This completes the inductive step. Finally, you can conclude that the statement is true for all values of n by the principle of mathematical induction.

## 3. What is the statement we are trying to prove with this induction proof?

The statement we are trying to prove is: ∑nj=0 n C r = 2n. This statement is also known as the Binomial Theorem, which states that the sum of the combinations of n objects taken r at a time is equal to 2n.

## 4. What is the base case for this induction proof?

The base case for this induction proof is when n=0, since the sum of combinations for n=0 is simply 0 C 0 = 1. Therefore, the statement holds true for n=0, and we can move on to the inductive step.

## 5. How do we use the assumption in the inductive step?

In the inductive step, we use the assumption that the statement is true for some value of n, let's say k. This means that ∑k j=0 k C r = 2k. We then use this assumption to prove that the statement is also true for the next value of n, which is k+1. By plugging in k+1 for n in the statement, we get ∑k+1 j=0 (k+1) C r = 2k+1. By manipulating this equation and using the assumption, we can show that the statement holds true for k+1. This completes the inductive step and proves the statement for all values of n.

Replies
9
Views
623
Replies
18
Views
1K
Replies
10
Views
725
Replies
6
Views
1K
Replies
4
Views
337
Replies
4
Views
1K
Replies
5
Views
1K
Replies
4
Views
2K
Replies
7
Views
1K
Replies
2
Views
2K