Question

Let P (n) be a statement and let P (n) = P(n + 1) for all natural numbers n, then what will the
nature of P (n)?​

Answer 1

Answer:  First Principle of Mathematical Induction. Let P(n) be a predicate

with domain of discourse (over) the natural numbers N = {0, 1, 2, ...}. If

(1) P(0), and

(2) P(n) → P(n + 1)

then ∀nP(n).

Terminology: The hypothesis P(0) is called the basis step and the hypothesis,

P(n) → P(n + 1), is called the induction (or inductive) step.

Discussion

The Principle of Mathematical Induction is an axiom of the system of natural

numbers that may be used to prove a quantified statement of the form ∀nP(n), where

the universe of discourse is the set of natural numbers. The principle of induction has

a number of equivalent forms and is based on the last of the four Peano Axioms we

alluded to in Module 3.1 Introduction to Proofs. The axiom of induction states that

if S is a set of natural numbers such that (i) 0 ∈ S and (ii) if n ∈ S, then n + 1 ∈ S,

then S = N. This is a fairly complicated statement: Not only is it an “if ..., then ...”

statement, but its hypotheses also contains an “if ..., then ...” statement (if n ∈ S,

then n + 1 ∈ S). When we apply the axiom to the truth set of a predicate P(n), we

arrive at the first principle of mathematical induction stated above. More generally,

we may apply the principle of induction whenever the universe of discourse is a set of

integers of the form {k, k + 1, k + 2, . . . } where k is some fixed integer. In this case

it would be stated as follows:

Let P(n) be a predicate over {k, k + 1, k + 2, k + 3, . . . }, where k ∈ Z. If

(1) P(k), and

(2) P(n) → P(n + 1)

then ∀nP(n).

In this context the “for all n”, of course, means for all n ≥ k