CourseCourseQ BankQuestion BankDocsDocuments

FP1.8 - Proof

Syllabus
2019
Topic
—
Level
AS

Build a complete proof by induction

Mathematical induction proves a statement P(n)P(n) for every integer n≥n0n\ge n_0 by establishing a starting case and a chain: whenever one case is true, the next case must be true.

Stage What the proof must establish
Base case Substitute n=n0n=n_0 and verify both sides or the required property.
Induction hypothesis Assume P(k)P(k) is true for an arbitrary integer k≥n0k\ge n_0.
Inductive step Use that assumption to derive the exact statement P(k+1)P(k+1).
Conclusion State that the base case and implication P(k)⇒P(k+1)P(k)\Rightarrow P(k+1) prove P(n)P(n) for all integers n≥n0n\ge n_0.
Required FP1 proof type Productive k→k+1k\to k+1 move
sum of a series Start with the assumed sum to kk and add the term whose index is k+1k+1.
divisibility by mm Rewrite f(k+1)f(k+1) as a multiple of the assumed divisible expression plus an explicit multiple of mm.
general term of a recurrence Substitute the assumed formula for uku_k into the recurrence; for a second-order recurrence use two base cases and assume formulas for two consecutive terms.
matrix power If Ak=MkA^k=M_k, write Ak+1=AkA=MkAA^{k+1}=A^kA=M_kA and simplify every entry to the stated matrix Mk+1M_{k+1}.

For example, let P(n)P(n) be ∑r=1n(2r−1)=n2.\sum_{r=1}^{n}(2r-1)=n^2. Base case: for n=1n=1, both sides equal 11. Assume P(k)P(k), so ∑r=1k(2r−1)=k2\sum_{r=1}^{k}(2r-1)=k^2. Then ∑r=1k+1(2r−1)=k2+(2(k+1)−1)=k2+2k+1=(k+1)2.\sum_{r=1}^{k+1}(2r-1)=k^2+\bigl(2(k+1)-1\bigr)=k^2+2k+1=(k+1)^2. This is exactly P(k+1)P(k+1). Since P(1)P(1) is true and P(k)P(k) implies P(k+1)P(k+1), the result holds for every positive integer nn.

The induction hypothesis is a temporary assumption inside a conditional argument; it is not the conclusion being assumed. The base case starts the chain, and the inductive step guarantees there is no break after any established case.

Checking several numerical cases does not prove the general result. Do not assume P(k+1)P(k+1), and do not finish after obtaining an expression that merely resembles it: rewrite it into the exact target form. Match the number of base cases and consecutive hypotheses to the order of a recurrence, and include the final quantified conclusion.