PROOF 129

Prove.

Verifying a general term by induction

On the natural numbers ℕ.

A way to read this proof

First separate what is assumed from what is to be proved. At each step, ask which definition or earlier result permits the move. If it is unclear, return to that premise rather than skipping to the conclusion.

Definition D1

The sequence (aₙ) is determined by a first term a₁ and a recurrence aₖ₊₁ = F(aₖ, k). For a formula f assigning one value to each natural number n, let the proposition P(n) be “aₙ = f(n)”.

Proof.

(1)a₁ is given and aₖ₊₁ is determined from aₖ, so aₙ is uniquely determined for each n.convention

(2)f is a conjecture. Until P(n) is verified, f(n) cannot be written in place of aₙ.convention

∎

Theorem T1

If P(1) holds and P(k) ⟹ P(k+1) for every natural number k, then aₙ = f(n) for every natural number n.

Proof.

(1)P(1) holds.assumption

(2)P(k) ⟹ P(k+1) for every k.assumption

(3)Therefore P(n) holds for every n, that is, aₙ = f(n).(1), (2), A1, D1

∎

Theorem T2

The induction step alone does not yield the conclusion.

Proof.

(1)Take the sequence (aₙ) with a₁ = 1, aₖ₊₁ = aₖ + 2, and the conjecture f(n) = 2n.D1

(2)If aₖ = 2k, then aₖ₊₁ = 2k + 2.(1), E

(3)2(k+1) = 2k + 2×1 = 2k + 2A2, A3

(4)Therefore aₖ₊₁ = 2(k+1), and P(k) ⟹ P(k+1) holds for every k.(2), (3)

(5)f(1) = 2 × 1 = 2 = 1 + 1A3, A6

(6)If a₁ = f(1), then 1 = 1 + 1, contradicting A5.(1), (5), E, A5

(7)Therefore P(1) fails, and it is not the case that aₙ = f(n) for every n.(6)

∎

Theorem T3

The base case alone does not yield the conclusion.

Proof.

(1)Take the sequence (aₙ) with a₁ = 1, aₖ₊₁ = aₖ + 2, and the conjecture h(n) = n.D1

(2)a₁ = 1 = h(1), so P(1) holds.(1)

(3)a₂ = a₁ + 2 = 1 + 2 = 2 + 1 = 3(1), A7, A6

(4)h(2) = 2(1)

(5)If 3 = 2, then 2 + 1 = 2 = 1 + 1.A6, E

(6)Then 2 = 1, and in turn 1 + 1 = 1, contradicting A5.(5), A4, A6, A5

(7)Therefore a₂ ≠ h(2), and even though P(1) holds, P(2) does not.(3), (4), (6)

(8)Nor is it the case that aₙ = h(n) for every n.(7)

∎

Remark

Can A1 be removed from this proof?

The two conditions of the verification procedure are finite computations. Check how far those computations reach.