Proof by Induction

Q:  Prove by induction that:

1*1!+2*2!+…+n*n! = (n+1)! – 1

A:  Here are the steps to induction:

1.  Base Case:  Prove the statement true for a base case, usually n = 1

2.  Induction Assumption: Assume the statement is true for some N.

3.  Induction Step: Using the induction assumption, prove the statement is true for N + 1

The logic:  If we prove that we can use the previous case to get to the next case, this will step up like a ladder, right?  Use the previous step to get to the next step, and so on… All we need to do is to prove the first step (base case) and then we know it could be used to get to each of the following steps.

In our case, we have:

1*1!+2*2!+…+n*n! = (n+1)! – 1

Base Case:  Prove true for n = 1

The left-hand side of the equation: 1*1! = 1

The right-hand side of the equation: (n + 1)! – 1 = (1 + 1)! – 1 = 2 – 1 = 1

Therefore, the left-hand side equals the right-hand side.  So, for n = 1, it is true that:

1*1!+2*2!+…+n*n! = (n+1)! – 1

Induction Assumption:  Assume true for N:

Assume that 1*1!+2*2!+…+N*N! = (N+1)! – 1

Induction Step:  Prove true for (N+1)

The goal is to show that: 1*1!+2*2!+…+N*N! + (N+1)*(N+1)! = ((N+1)+1)! – 1

Or simplified:  1*1!+2*2!+…+N*N! + (N+1)*(N+1)! = (N+2)! – 1

So let’s examine the left-hand side of the equation for (N+1)

1*1!+2*2!+…+N*N! + (N+1)*(N+1)!

Using our induction assumption, we know that 1*1!+2*2!+…+N*N! = (N+1)! – 1

Therefore, substituting:

1*1!+2*2!+…+N*N! + (N+1)*(N+1)! = (N+1)! – 1 + (N+1)*(N+1)!

Re-arranging, we have:
1*1!+2*2!+…+N*N! + (N+1)*(N+1)! = (N+1)! + (N+1)(N+1)! – 1

1*1!+2*2!+…+N*N! + (N+1)*(N+1)! = (N+1)! [ 1 + (N+1)] – 1

1*1!+2*2!+…+N*N! + (N+1)*(N+1)! = (N+1)! (N+2) – 1

1*1!+2*2!+…+N*N! + (N+1)*(N+1)! = (N+2)! – 1

By using our induction assumption for N, we were able to prove the N+1 case.  So, we have proved, by induction, that:

1*1!+2*2!+…+n*n! = (n+1)! – 1

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s