# Proof of Induction Principle starting from N, not from 1

• I
• Hall

#### Hall

TL;DR Summary
Induction Principle.
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?

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.

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

• Delta2 and FactChecker
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.

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

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.

• Hall
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.

Last edited: