Proof of Induction Principle starting from N, not from 1

Hall · May 12, 2022

In this video lecture (though I have linked the video at "current time", in case it doesn't; work please see the video at 19:16), the lecturer just works out (he is not explaining anything) the proof of Induction Principle starting from ##N##. Let me give out here what he did:

Statement: Let N be an integer, ##P(n)## denotes the Property P that a natural number ##n \geq N## may or may not follow. If
1. P(N) holds
2. P(n) implies P(n+1)
then P(n) is true for all ##n \gt N##.

Proof: ##Q(n) = P(n+N-1)##
1. ## Q(1) = P(N)##, since P(N) holds therefore, Q(1) is true.
2. If ## Q(n) = P(n+N-1)## holds then ##Q(n+1) = P(n+N)## holds and therefore P(n) holds for all ##n\geq N##.

I couldn't understand anything of step 2 of the proof. Can you please give some hint?

Hall · May 12, 2022

Well, I think I got it.

We have to prove that ##P(n)## holds for all ##n \geq N## if the following two conditions are given:
1. P(N) holds
2. P(n) implies P(n+1), for all ##n \geq N##

Proof: Assume another proposition, ## Q (n) = P(n+N-1)##.
Since, ##Q(1) = P(N)## and ##P(N)## is true, therefore, Q(1) is true.

Assume that, ##Q(n)## is true, that is ##P(n+N-1)## is true, then ##Q(n+1) = P(n+N)## is true because it is of the form ##P(r) \implies P(r+1)##, r= n+N-1, which is validated by property 2 in the statement. Hence, ##Q(n) \implies Q(n+1)##, therefore ##Q(n)## is true for all n.

Since, ## P(n+N-1)## is true for all n, we get

for n=1, we have P(N) is true
for n=2, we have P(N+1) is true
for n=3, we have P(N+2) is true

Therefore, P(n) is true for all ##n\geq N##.

Hence, proved.

The lecturer left out so many of things in proof, maybe for some it was obvious.

PeroK · May 12, 2022

The key point is that induction from ##N## reduces to induction from ##1## simply by rephrasing the propositions.

FactChecker · May 12, 2022

One proposition's (P's) N is another proposition's (Q's) 1. It is just a matter of where you start counting and adjusting for that.

Hall · May 13, 2022

@PeroK @FactChecker Yes, reducing the N induction principle to the normal induction principle was the trick. But the last step, moving from ##P(n+N-1)## to ##P(n) ~ \forall n\geq N##, was also not very obvious.

WWGD · May 15, 2022

In most accounts I'm familiar with, the Well-Ordering principle is used, so that the set of all P(n) that are true has a least element. Maybe that would shed light on the proof/argument.

FactChecker · May 15, 2022

Hall said:

But the last step, moving from ##P(n+N-1)## to ##P(n) ~ \forall n\geq N##, was also not very obvious.

The task of shifting an index is one that you may run into occasionally. You can simplify your understanding of it by plugging in n=1 in the side that should start with 1 and see what you get: P(1+N-1)=P(N). And it goes up from there: P(2+N-1) = P(N+1). It really is simple once you get used to it.

PS. Using the same dummy index, n, on both sides may be a conceptual mistake. Use ##n \ge 1## on one side and ##m \ge N## on the other.

Proof of Induction Principle starting from N, not from 1

1. What is the induction principle and why is it important?

2. Can the induction principle be applied to any set of numbers?

3. Why is it necessary to start the induction principle from N instead of 1?

4. How is the induction principle different from other proof techniques?

5. Can the induction principle be used to prove statements about real numbers?

Similar threads

Hot Threads

Recent Insights