Proof of Induction Principle starting from N, not from 1

[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?

 

[Hall]

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]

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

 

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

 

[Hall]

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

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]

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.