Induction theorem

[Maths Pro]

Is it mandatory to have P(1) to be proven true before we prove P(k+1) to be true? If P(1), P(2), P(3) are not proven but P(4) onwards could be proven to prove P(k+1), then is it valid? I will state an example : n!>2^n could be proven true for n>=4 and thus for n=k+1. Is it valid?
Also in example : 1.6 + 2.9 + 3.12........n(3n+3) = n^3 + 3n^2 + 2n + 3, P(1) doesn't hold but P(k+1) holds. What exactly is the condition for induction theorem?

 

[Dr.Peterson]

Is it mandatory to have P(1) to be proven true before we prove P(k+1) to be true?

Presumably you mean, that you must prove both the base case and the inductive step, that if P(k), then P(k+1).

If you proved the latter, but not the former, then of course you are not finished.

If P(1), P(2), P(3) are not proven but P(4) onwards could be proven to prove P(k+1), then is it valid?

Again, you are not being clear. If you prove P(4), and that P(k) implies P(k+1) for k>=4, then you have proved P(k) for k>=4.

Is that what you mean, or not?

I will state an example : n!>2^n could be proven true for n>=4 and thus for n=k+1. Is it valid?

If you prove P(4) [by showing that 4! = 24 > 2^4 = 16], and that P(k) implies P(k+1) for k>=4 [which I suppose you will do], then you have proved P(k) for k>=4.

The way you stated it doesn't quite mean this. Logic must be stated clearly.

Also in example : 1.6 + 2.9 + 3.12........n(3n+3) = n^3 + 3n^2 + 2n + 3, P(1) doesn't hold but P(k+1) holds.

I can't tell what this means.

If I assume "." means multiplication and not a decimal point, then it appears that P(1) means 1(3(1)+3) = 1*6 = 6 should be equal to 1^3 + 3*1^2 + 2*1 + 3 = 9, so P(1) is false. What do you mean by saying that "P(k+1) holds", without specifying k?

I suspect that you have incorrectly shown P(n).

What exactly is the condition for induction theorem?

Please state the theorem as given to you! Any theorem, fully stated, will include all its conditions.

 

[Maths Pro]

If I assume "." means multiplication and not a decimal point, then it appears that P(1) means 1(3(1)+3) = 1*6 = 6 should be equal to 1^3 + 3*1^2 + 2*1 + 3 = 9, so P(1) is false. What do you mean by saying that "P(k+1) holds", without specifying k?

Let us assume that P(k) is true
1.6+2.9+3.12....k(3k+3) =k^3+3k^2+2k+3...(1)
Now to prove: P(k+1) is true
i.e. to prove : 1.6+2.9+3.12....k(3k+3) + (k+1)(3k+6) =(k+1)^3+3(k+1)^2+2(k+1)+3

L.H.S = [1.6+2.9+3.12....k(3k+3)]+ (k+1)(3k+6)
= [k^3+3k^2+2k+3 ]+ (k+1)(3k+6)
= [k^3+3k^2+2k+3] + 3k^2+6k+3k+6
= k^3+6k^2+11k+9 which I write as
= (k^3+3k^2+3k+1)+(3k^2+8k+8) which I write as
= (k^3+3k^2+3k+1) + 3(k^2+2k+1) + (2k+2) + 3
=(k+1)^3 +3(k+1)^2 +2(k+1) +3
=R.H.S
Thus proved for P(k+1)
Dot is multiplication as you rightly guessed.

Please state the theorem as given to you! Any theorem, fully stated, will include all its conditions.

This is given in my book:
"Step1(Foundation): Formulate the statement of the theorem as P(n) say, for any positive integer n and verify it for integer n=1. In fact, it is often instructive, though not necessary, to verify the statement for n=2 and n=3. This gives better insight into the theorem
Step2(Assumption): Assume that the statement is true for a positive integer k
Step3(Succession): Prove the statement for n=k+1
Step 4(Induction): Now invoke the principle of Mathematical induction. Conclude that the theorem is true for any positive integer n."

This is all that is given. They also compared it to row of dominos standing close to each other.

 

[mrtwhs]

I think I understand what you are asking. Consider attempting to prove this by induction:

If [imath]P(n)=1+2+3+\cdots+n[/imath] then [imath]P(n)=\dfrac{n(n+1)}{2}+7[/imath].

Assume they are equal for some value of [imath]n[/imath]. Consider [imath]n+1[/imath]. Add [imath]n+1[/imath] to both sides.

[imath]1+2+3+\cdots+n+(n+1)=\dfrac{n(n+1)}{2}+7+(n+1)=\dfrac{n(n+1)}{2}+7+\dfrac{2(n+1)}{2}=\dfrac{n(n+1)+2(n+1)}{2}+7[/imath]
[imath]=\dfrac{(n+1)(n+2)}{2}+7=P(n+1)[/imath].

Therefore, IF the statement is true for [imath]n[/imath], it is true for [imath]n+1[/imath].

Unfortunately it is not true for any integer and therefore not true at all.

Using your domino example, if you have an infinite row of dominoes and you can knock over one of them, then all dominoes from that point on will fall over. However in this case, you cannot knock over ANY domino in the infinite row.

 

[Dr.Peterson]

Let us assume that P(k) is true
1.6+2.9+3.12....k(3k+3) =k^3+3k^2+2k+3...(1)
Now to prove: P(k+1) is true
i.e. to prove : 1.6+2.9+3.12....k(3k+3) + (k+1)(3k+6) =(k+1)^3+3(k+1)^2+2(k+1)+3

L.H.S = [1.6+2.9+3.12....k(3k+3)]+ (k+1)(3k+6)
= [k^3+3k^2+2k+3 ]+ (k+1)(3k+6)
= [k^3+3k^2+2k+3] + 3k^2+6k+3k+6
= k^3+6k^2+11k+9 which I write as
= (k^3+3k^2+3k+1)+(3k^2+8k+8) which I write as
= (k^3+3k^2+3k+1) + 3(k^2+2k+1) + (2k+2) + 3
=(k+1)^3 +3(k+1)^2 +2(k+1) +3
=R.H.S
Thus proved for P(k+1)

The bold line is what you failed to state, which is essential.

And, as @mrtwhs has pointed out, doing this without showing any specific P(n) to be true proves nothing.

In fact, the RHS should be n^3 + 3n^2 + 2n, without the added 3. With that change, both the base step and the inductive step work.

This is given in my book:
"Step1(Foundation): Formulate the statement of the theorem as P(n) say, for any positive integer n and verify it for integer n=1. In fact, it is often instructive, though not necessary, to verify the statement for n=2 and n=3. This gives better insight into the theorem
Step2(Assumption): Assume that the statement is true for a positive integer k
Step3(Succession): Prove the statement for n=k+1
Step 4(Induction): Now invoke the principle of Mathematical induction. Conclude that the theorem is true for any positive integer n."

Presumably they state the Principle of Mathematical Induction. Can you quote that? That's what I was asking for! (A theorem, not just a procedure.)

But they do clearly state here that you need to prove for n=1 as well as the inductive step. That should be enough to answer your question -- unless what you were asking is whether it is necessary to do the base case first. (It doesn't always have to be P(1), depending on what you are trying to prove.) That isn't essential, though it is wise; but until you have done both, you have not accomplished the task.

 

[Maths Pro]

Can you quote that

surprisingly, it's not given in my book. Where can I find it? I mean I can google but I think I get what you are saying. First prove base case then assume P(k) only then p(k+1) can be proven, right?

 

[Dr.Peterson]

surprisingly, it's not given in my book. Where can I find it?

That's odd; why would a book refer to something in this way that hasn't been taught? I'd go to the start of the chapter and start reading, if it isn't listed in the index. It's going to be there somewhere.

First prove base case then assume P(k) only then p(k+1) can be proven, right?

I'd say it this way:

First prove base case, then assume P(k) and prove P(k+1); only then has P(n) been proved for all n starting with the base case.​

 

[Maths Pro]

This is what I found on web:
The Principle of Mathematical Induction: Let P(n) be a statement involving a natural number n. If(i) it is true for n = 1, i.e., P(1) is true; and(ii) assuming k>= 1 and P(k) to be true, it can be proved that P(k+ 1) is true; then P(n) must be true for every natural number n Note that condition (ii) above does not say that P(k) is true. It says that whenever P(k)is true, then P( k + 1) is true’.Let us see, for example, how the principle of mathematical induction allows us to conclude that P(n) is true for n = 11.By (i) P(1) is true. As P(1) is true, we can put k = 1 in (ii), So P(1 + 1), i.e., P(2) is true. As P(2) is true, we can put k = 2 in (ii) and conclude thatP(2 + 1), i.e., P(3) is true. Now put k = 3 in (ii), so we get that P(4) is true. It is now clear that if we continue like this, we shall get that P(11) is true. It is also clear that in the above argument, 11 does not play any special role. We can prove that P(137) is true in the same way. Indeed, it is clear that P(n) is true for all n > 1
And then an example is given. Prove that, 1 +2 + 3 + .....n = n(n+1)/2 , where n is a natural number.

 

[fresh_42]

surprisingly, it's not given in my book. Where can I find it? I mean I can google but I think I get what you are saying. First prove base case then assume P(k) only then p(k+1) can be proven, right?

Yes. The idea is: Prove P(1), P(2), ... We can't do that for all numbers, so let's pretend we have done it until P(n). If we can now use this also to prove P(n+1), then we are done because n could be any number. The starting point P(1) does not have to be 1, but there has to be some starting point.

Example 1: All numbers n! are divisible by 7.

If 7 divides n!, then 7 also divides (n+1)! = n! x (n+1). This is the induction step. But 7 does not divide 1! or 2!, which means that the induction is incomplete and the statement is not true for all numbers. However, 7 divides 7!, so the statement becomes true if we demand n > 6. We need an induction base, in this case, P(1)=7.

The German term for the induction proof is "complete induction." This always reminds us that the base is crucial, not only the induction step.

Example 2: Every positive integer coincides with its successor n+1.

P(n) says that n =n+1. Then n+1=(n)+1=(n+1)+1=n+2, which proves P(n+1). So the induction step is correct. However, we will never find an induction base, i.e., a single number n for which n=n+1 is true. The statement itself is incorrect, although the induction step is correct.

 

[Dr.Peterson]

We need an induction base, in this case, P(1)=7.

I don't think you quite meant what you wrote.

The statement being proved is

P(n): n! is divisible by 7.​

This is only true for n>=7, so we have to take that as the base case; we prove that P(7) is true, rather than P(1). That, together with the induction step, proves that P(n) is true for n>=7.

The German term for the induction proof is "complete induction." This always reminds us that the base is crucial, not only the induction step.

In English, "complete induction" is a variation of induction proof, also called "strong induction":

Mathematical induction - Wikipedia

en.wikipedia.org

I mention this only for completeness ...

 

[fresh_42]

I don't think you quite meant what you wrote.

The statement being proved is

P(n): n! is divisible by 7.​

This is only true for n>=7, so we have to take that as the base case; we prove that P(7) is true, rather than P(1). That, together with the induction step, proves that P(n) is true for n>=7.

Yes, I saw that I confused P(n) with n at the induction base, but the edit window has already expired, and I didn't want to confuse the OP with a correction post. I find the distinction of the various induction forms a matter for logicians. It doesn't make a substantial difference where we set the induction base as long as there is one, or to distinguish the assumption P(n) from P(k) for all k<n+1. I find it more important to realize that the induction proof is a formal handling of "and so on".

 

[fresh_42]

To complete the discussion about induction proofs, @Maths Pro, there can also be inductions where the induction step isn't +1 but any other distance. E.g., "Every third number is divisible by 3."

Induction base: P(1) is true since the first third number is 3, and 3 divides 3.
Induction assumption: P(n) is true.
Induction step: If n is the n-th third number, then n=3m for some m. Thus, n+3= 3m+3= 3 x (m+1), which is the next third number, is also divisible by 3, proving P(n+1).

n is the count of third numbers, not the number itself. So the step is 1 by counts, by 3 by numbers, and we could write P(3) and P(3n) instead of P(1) and P(n). It only means that we have to be careful what the n represents.

Of course, we can replace this example with more complicated step distances. The point is the "and so on". We cannot proceed and so on up to infinity, so we pretend that we have done it up to some number, and then prove the next step based on this assumption. The logical trick is that if n is any number, and we proved a statement P for n+1, then we covered all numbers, because there is always a next one, +1, and all numbers can be reached this way.