Proof of Induction Principle starting from N, not from 1

In summary, the lecturer in the video lecture explains the proof of the Induction Principle starting from ##N##. The key point is that induction from ##N## can be reduced to induction from ##1## by rephrasing the propositions. The lecturer also mentions that the last step, moving from ##P(n+N-1)## to ##P(n) ~ \forall n\geq N##, may not be obvious but can be simplified by plugging in values for n. It is also suggested to use different dummy indices on each side to avoid confusion.
  • #1
Hall
351
87
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?
 
Physics news on Phys.org
  • #2
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.
 
  • #3
The key point is that induction from ##N## reduces to induction from ##1## simply by rephrasing the propositions.
 
  • Like
Likes Delta2 and FactChecker
  • #4
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.
 
  • #5
@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.
 
  • #6
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.
 
  • Like
Likes Hall
  • #7
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.
 
Last edited:

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

The induction principle is a mathematical proof technique used to show that a statement is true for all natural numbers. It is important because it allows us to prove infinite sets of numbers without having to check each individual case.

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

No, the induction principle can only be applied to sets of numbers that have a well-defined successor function, such as the natural numbers. It cannot be applied to sets of numbers that have gaps or do not have a clear starting point.

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

Starting the induction principle from N instead of 1 allows us to prove statements for all natural numbers, including negative numbers. This is because the successor function for N includes both positive and negative numbers, while the successor function for 1 only includes positive numbers.

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

The induction principle is different from other proof techniques because it relies on the assumption that the statement is true for a starting case, and then uses this assumption to prove that it is also true for the next case. Other proof techniques may use different assumptions or logic to prove a statement.

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

No, the induction principle can only be used for sets of numbers that have a well-defined successor function, such as the natural numbers. Real numbers do not have a clear starting point or a successor function, so the induction principle cannot be applied to them.

Similar threads

  • Topology and Analysis
Replies
2
Views
2K
  • Topology and Analysis
2
Replies
48
Views
3K
  • Topology and Analysis
Replies
4
Views
1K
Replies
1
Views
645
Replies
2
Views
323
Replies
2
Views
1K
Replies
2
Views
709
  • Topology and Analysis
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
7
Views
311
  • Calculus and Beyond Homework Help
Replies
24
Views
626
Back
Top