# Induction problem

• May 2nd 2013, 09:44 AM
RatchetTheLombax
Induction problem
Verify that

1(1!)+2(2!)+...+n(n!) = (n+1)! - 1

is true using induction

For the nth case I plug in n = 1

1(1!) = (1+1)! - 1
1 = 2! - 1
1 = 1 This is true

For the n+1 case n = 1

1(1!) + 2(2!)+...+n(n!)(n+1) = ((n+1)+1))! - 1

n(n!)(n+1)((n+1)! - 1) = (n+2)! - 1

1(1!)(1+1)((1+1)!-1) = (1+2)! - 1

2 = 5 This is not true

Therefore, this is not true on the n+1 case.

Am I correct?
• May 2nd 2013, 10:16 AM
Plato
Re: Induction problem
Quote:

Originally Posted by RatchetTheLombax
Verify that

1(1!)+2(2!)+...+n(n!) = (n+1)! - 1

is true using induction

For the nth case I plug in n = 1

1(1!) = (1+1)! - 1
1 = 2! - 1
1 = 1 This is true

If we use summation it is easier to see.

The induction hypothesis is $\sum\limits_{k = 1}^N {k\left[ {k!} \right]} = \left( {N + 1} \right)!-1$ is true.

Look at $\sum\limits_{k = 1}^{N+1} {k\left[ {k!} \right]} = \sum\limits_{k = 1}^N {k\left[ {k!} \right]}+(N+1)[(N+1)!] \\=\left[ {\left( {N + 1} \right)! - 1} \right] + (N + 1)\left[ {(N + 1)!} \right] = \left( {[N + 2]! - 1} \right)$
• May 2nd 2013, 10:17 AM
emakarov
Re: Induction problem
Quote:

Originally Posted by RatchetTheLombax
1(1!) + 2(2!)+...+n(n!)(n+1) = ((n+1)+1))! - 1

n(n!)(n+1)((n+1)! - 1) = (n+2)! - 1

The first line should probably be

1(1!) + 2(2!)+...+(n+1)(n!)(n+1) = ((n+1)+1))! - 1

Also, I don't understand how the second line is related to the first one.

In general, proofs in the high school style consisting of a series of equalities ending with something like 1 = 1 are not used in higher mathematics. In a proof, it should be clear how subsequent claims follow from previous ones. Thus, real proofs may use long chains of equalities E1 = E2 = E3 = ..., possibly split over several lines and accompanied by short comments saying how each equality is obtained. Otherwise, a proof should be a sequence of claims joined by words or symbols such as "therefore", "thus" or "⇒", which show the relationship between the claims.
• May 2nd 2013, 11:17 AM
RatchetTheLombax
Re: Induction problem
Quote:

Originally Posted by emakarov
The first line should probably be

1(1!) + 2(2!)+...+(n+1)(n!)(n+1) = ((n+1)+1))! - 1

Also, I don't understand how the second line is related to the first one.

In general, proofs in the high school style consisting of a series of equalities ending with something like 1 = 1 are not used in higher mathematics. In a proof, it should be clear how subsequent claims follow from previous ones. Thus, real proofs may use long chains of equalities E1 = E2 = E3 = ..., possibly split over several lines and accompanied by short comments saying how each equality is obtained. Otherwise, a proof should be a sequence of claims joined by words or symbols such as "therefore", "thus" or "⇒", which show the relationship between the claims.

What do you mean? You have to take the n and the n+1 case and prove they are equal.
• May 2nd 2013, 12:08 PM
emakarov
Re: Induction problem
Quote:

Originally Posted by RatchetTheLombax
What do you mean? You have to take the n and the n+1 case and prove they are equal.

Now I am not sure what you mean by n-case and (n+1)-case. A proof by induction starts with identifying a property of natural numbers, often denoted by P(n). For each n, P(n) is either true or false (in particular, P(n) is not a number). This property can be an equality, as in the current problem, but it can have other forms: e.g., e1(n) divides e2(n) for some expressions e1 and e2, e(n) is a triangular number for some e, etc. The problem is to prove that P(n) holds for all natural n ≥ n0. The base case consists of proving P(n0). The induction step consists of proving that P(n) implies P(n+1) for all n ≥ n0.

In this problem, P(n) is 1(1!) + 2(2!) + ... + n(n!) = (n+1)! - 1; therefore, P(n+1) is 1(1!) + 2(2!) + ... + (n+1)(n+1)! = (n+2)! - 1. I assumed the line

1(1!) + 2(2!)+...+n(n!)(n+1) = ((n+1)+1))! - 1

in post #1 supposed to be P(n+1). That's why I said n(n!)(n+1) should be replaced by (n+1)(n!)(n+1) = (n+1)(n+1)!.
• May 2nd 2013, 04:01 PM
RatchetTheLombax
Re: Induction problem
Quote:

Originally Posted by emakarov
Now I am not sure what you mean by n-case and (n+1)-case. A proof by induction starts with identifying a property of natural numbers, often denoted by P(n). For each n, P(n) is either true or false (in particular, P(n) is not a number). This property can be an equality, as in the current problem, but it can have other forms: e.g., e1(n) divides e2(n) for some expressions e1 and e2, e(n) is a triangular number for some e, etc. The problem is to prove that P(n) holds for all natural n ≥ n0. The base case consists of proving P(n0). The induction step consists of proving that P(n) implies P(n+1) for all n ≥ n0.

In this problem, P(n) is 1(1!) + 2(2!) + ... + n(n!) = (n+1)! - 1; therefore, P(n+1) is 1(1!) + 2(2!) + ... + (n+1)(n+1)! = (n+2)! - 1. I assumed the line

1(1!) + 2(2!)+...+n(n!)(n+1) = ((n+1)+1))! - 1

in post #1 supposed to be P(n+1). That's why I said n(n!)(n+1) should be replaced by (n+1)(n!)(n+1) = (n+1)(n+1)!.

You are probably right. Induction doesn't make any sense at all. I understand what it is but that is the extent of it.
• May 2nd 2013, 04:41 PM
Plato
Re: Induction problem
[QUOTE=RatchetTheLombax;785496]You are probably right. Induction doesn't make any sense at all. I
understand what it is but that is the extent of it.[/QUOTE

Why do you say that?

Here is a real-world example.
Think of a garden path made up of stepping stones.
Now suppose I show you that there is absolutely a way that you can get onto the first stone in the path.
Then I show you that if you are on any stone then you can absolutely 'move' to the next stone.
Does that not mean that "you can start at the first stone and move through the entire garden path?
You can get on at $S_1$, but then you have a grantee you can go to $S_2$ then to $S_3$, etc.

That is what induction is all about.
We can step on all positive integers for a statement.
• May 10th 2013, 03:05 AM
ibdutt
Re: Induction problem