CourseCourseQ BankQuestion BankDocsDocuments

1.7 Proof by induction

Syllabus
9231–2028–2029
Topic
1.7
Level
AS

Learning objectives

1.7.1Proof by induction• use the method of mathematical induction to establish a given result e.g. rn n4 1 1 r n 42 2 1 = + = ^h/, u 2 1 13n n 1= + -_ i for the sequence given by uu 31nn1 -=+ and u 11 =, 4 6 1 1 32 2 32 6 12 32 n n n n n11 # # - - - - - -= ++f fp p, 32 53nn2 # -+ is divisible by 8.1.7.2Inductive conjecture• recognise situations where conjecture based on a limited trial followed by inductive proof is a useful strategy, and carry this out in simple cases. e.g. find the nth derivative of x ex, find !rr r n 1 # = /.

Make the inductive hypothesis do the k-to-k+1 work

To prove P(n)P(n) for every integer n≥n0n\ge n_0: state the domain; verify P(n0)P(n_0); assume P(k)P(k) for an arbitrary integer k≥n0k\ge n_0; start from the k+1 expression and use the hypothesis to obtain exactly P(k+1)P(k+1); conclude that P(n)P(n) holds for all integers in the stated domain by mathematical induction.

Statement type Productive k+1 move
Finite sum Write Sk+1=Sk+S_{k+1}=S_k+ the new term, then substitute the hypothesis
Recurrence Write the given uk+1u_{k+1} relation and substitute the formula for uku_k
Matrix identity Form the next power/product and use the assumed matrix expression with order preserved
Divisibility by m Rearrange the k+1 expression as a known multiple of m plus a multiple of the assumed divisible expression

Claim: $24\mid(5^{2n}-1)$ for every positive integer n. Base: $5^2-1=24$. Assume $5^{2k}-1=24q$ for some integer q. Then5^{2(k+1)}-1=25\cdot5^{2k}-1=25(5^{2k}-1)+24=24(25q+1),sothek+1expressionisdivisibleby24.Hencetheclaimfollowsforallpositiveintegersn.so the k+1 expression is divisible by 24. Hence the claim follows for all positive integers n.

The hypothesis is not the conclusion: it may be used only for the arbitrary k case. A correct k-to-k+1 calculation without a valid base case establishes no starting chain, and numerical checks alone are not induction.

Use trials to discover the statement, then restart with proof

Calculate several exact cases and record the whole expression, not just decimal outputs. Look for factorial shifts, powers, finite differences or a stable algebraic form. State a conjecture with its starting index and domain, test one further case, then treat the conjecture only as the statement P(n)P(n) to be proved.

For Sn=∑r=1nr r!S_n=\sum_{r=1}^{n}r\,r!:

n Direct total Revealing form
1 1 2!−12!-1
2 1+4=51+4=5 3!−13!-1
3 1+4+18=231+4+18=23 4!−14!-1

Conjecture: Sn=(n+1)!−1S_n=(n+1)!-1 for every positive integer n.

Base: $S_1=1=2!-1$. Assume $S_k=(k+1)!-1$. ThenS_{k+1}=S_k+(k+1)(k+1)!=(k+1)!-1+(k+1)(k+1)!=(k+2)(k+1)!-1=(k+2)!-1.Thereforetheconjectureholdsforallpositiveintegersnbyinduction.Therefore the conjecture holds for all positive integers n by induction.

The same discovery route applies to repeated differentiation: compute the first few derivatives, factor out the common exponential term, conjecture the remaining n-pattern, and prove the successor by differentiating the assumed nth-derivative form.

Trials reveal a plausible formula but cannot establish universality. If the induction step fails, revise the conjecture or its domain; do not disguise extra examples as proof.