Mathematical induction condition "p(k)$\Rightarrow$p(k+1)" for the divisibility by a prime number

Question

"

Mathematical induction If p(n) is a statement involving the natural number n such that:

p(1) is true, and

p(k)$\Rightarrow$p(k+1) for any arbitrary natural number k, then p(n) is true for any natural number n.

Example 12 Prove by mathematical induction that

​1+2+3+...+n= n(n+1)/2 for every natural number n

[Proof] Here p(n) represents the statement 1+2+3+...+n= n(n+1)/2

In particular p(1) represents 1 = (1ㆍ2)/2, which obviously is a true statement. Therefore, condition (1) for mathematical induction is satisfied.

To prove that condition (2) is satisfied, we assume that p(k), which is "1+2+3+...+k= k(k+1)/2" is true. Then add k+1 to both sides of this equality. We have

1+2+3+...+k+(k+1) = k(k+1)/2 + (k+1) = k(k+1)/2+ 2(k+1)/2 = (k+1)(k+2)/2

which shows that p(k+1) is true. We have now shown that the condition (1) and (2) of mathematical induction are satisfied. Therefore, by the principle of mathematical induction,

1+2+3+...+n= n(n+1)/2 is true for every natural number n"

Source: Set Theory by You-Feng Lin, Shwu-Yeng T. Lin

In the below proof, I have a question. I see "P(2) is true" is used instead of "p(1) is true" for the divisibility by a prime. But unlike from the above proof and the definition, why P(i) is divisible by a prime number for all integers i from 2 through k, rather than for some integer k≥2?

Source: Discrete Mathematics with Applications: Susanna S. Epp

Answer 1

It uses so-called "strong induction". If it is not explicitly mentioned in the book what this is, it is a variation on the principle of mathematical induction. Specifically, it is the following principle:

If $P(n)$ is some property that some natural number $n$ might have, and it is true that

• $P(a)$ is true for some $a \in \mathbb{N}$
• $P(k)$ is true for all $a \leq k < n$ implies that $P(n)$ is true

then $P(n)$ is true for all natural numbers greater than or equal to $a$.

This principal follows from the "normal" version of induction:

Suppose that we have the property $P$ with the conditions above satisfied. Let $Q$ be the predicate: $$ Q(n) = ((k \geq a \text{ and } k \leq n) \implies P(k)) $$ In other words, $Q(n)$ is true if either $n$ is less than $a$, or if $P(k)$ is true for all $k$ from $a$ to $n$.

You can then check that $Q(1)$ is true, and that from the conditions on $P$, that we have that $Q(n) \implies Q(n + 1)$. So by "normal" induction, $Q(n)$ is true for all natural numbers $n$. But $Q(n)$ implies $P(n)$ for all $n \geq a$, so we then also have that $P(n)$ is true for all $n \geq a$.

In your case, we are proving by induction the property $Q(n)$, where $Q(n)$ is given by the statement

"If $n \geq 2$, then all natural numbers from $2$ to $n$ have a prime factor."