STEP 1 OF 22 · Lesson Opening

Today: Math Induction — the 3-step framework

Pass 1 of proof writing. We meet the workhorse of olympiad proofs: "True for $n=1$, and if true for $n=k$ then true for $n=k+1$, therefore true for all $n$." Every infinite-family identity, every divisibility chain, every recurrence proof rides this same shape.

📌 What you will learn today

Topic: Mathematical induction. The 3-step framework (base / hypothesis / inductive step). Classic targets: $\sum k = n(n+1)/2$, divisibility ($6 \mid n^3 - n$), and inequalities ($2^n > n^2$).
Category: Proof writing (Pass 1) — sub-topic Math Induction Basics.
Solves these AIMO problems: 2016 Q4
Plus the synthesis problem at Step 15 — proving $6 \mid 7^n - 1$ for all $n \ge 1$.
AoPS Reference: Introduction to Number Theory by Mathew Crawford, ch. on induction, and Art of Problem Solving Vol. 2, the chapter on sums and identities.
Why this matters: Induction is the single most marked-rewarded technique across AIMO Q6–Q9 and AMO. A clean 3-step write-up earns at least 2 partial marks even before the algebra is verified. Pass 1 target: write the base + hypothesis + inductive opening on any identity and lock in 2/5 of marks.
Time required: About 85–95 minutes for the full lesson, plus practice problems.

How this lesson is structured

Phase 0 (Step 2): Prerequisites — what $P(n)$ means, $\Sigma$ notation, "assume $P(k)$" logic.
Phase 1 (Step 3): Visual intuition — the dominoes picture + ladder + 3-step framework box.
Phase 1.5 (Step 4): Formula manual — 5 sentence templates you can drop in to any proof.
Phase 2 (Steps 5–7): Three guided derivations — the triangular sum, sum of odd numbers, $2^n > n$.
Phase 3 (Steps 8–12): Five worked examples ⭐⭐ → ⭐⭐⭐⭐⭐, each fully written out.
Phase 4 (Step 13): Five P1–P5 practice problems with Hint / Answer / Solution.
Phase 5 (Step 14): AIMO 2016 Q4 — the recurrence last-digit problem, the full hint stack.
Phase 5.5 (Step 15): Synthesis — prove $6 \mid 7^n - 1$ with the gradeProof rubric scorer.
Steps 16–17: Atomic-skill matrix + 4 micro-validations.
Steps 18–20: Cheat sheet, ⭐ self-assessment, error book.
Steps 21–22: Wrap-up + bridge to Part 2 (Proof by Contradiction).

Pedagogy: Pass 1 — assumes Week 1–10 algebra and number theory basics are solid. We deliberately defer strong induction, double induction, and structural induction to W15 Pass 2. Today the goal is the 3-step shape: prove a base case clearly, assume $P(k)$, then transform it into $P(k+1)$. Even half-finished, the structure carries marks.

STEP 2 OF 22 · Phase 0 · Prerequisites

Prerequisites — $P(n)$, $\Sigma$ notation, and "assume $P(k)$"

Before we can write an induction proof, four small ideas must be totally automatic: what a statement $P(n)$ means, what counts as the base case, what "assume $P(k)$" lets you do, and how $\Sigma$ notation behaves.

① The statement $P(n)$

$P(n)$ is a statement that depends on $n$. For each natural number you pick, $P(n)$ is either true or false. Examples:

$P(n)$: "$1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$" — an equality statement.
$P(n)$: "$6 \mid n^3 - n$" — a divisibility statement.
$P(n)$: "$2^n > n^2$" — an inequality statement.

Induction proves $P(n)$ is true for every $n \ge n_0$, where $n_0$ is the base case (usually $1$, sometimes $0$, $4$, $5$, depending on when the statement starts being true).

② The natural numbers $\mathbb{N}$ and the base case $n_0$

We work over $\mathbb{N} = \{1, 2, 3, \ldots\}$ (or $\{0, 1, 2, \ldots\}$ — both conventions exist). The base case $n_0$ is the smallest $n$ for which we claim $P(n)$ is true. You must verify the base case explicitly — never skip it. A famous fake proof: "$P(n)$: all horses are the same colour" fails because the inductive step requires two horses, so $n=1$ doesn't transfer to $n=2$.

③ "Assume $P(k)$ is true" — the inductive hypothesis (IH)

This is the move that scares beginners. It looks like circular reasoning: "I'm trying to prove $P$ — but I'm assuming $P$?". The trick: we're not assuming $P(k+1)$; we're only assuming $P(k)$ for a generic $k$, and using that to derive $P(k+1)$. The chain of implications $P(1) \Rightarrow P(2) \Rightarrow P(3) \Rightarrow \cdots$ then carries true-ness forward from the verified base case.

④ $\Sigma$ notation cheat-sheet

$\displaystyle \sum_{i=1}^{n} f(i) = f(1) + f(2) + \cdots + f(n)$. Useful identities:

$\displaystyle \sum_{i=1}^{n+1} f(i) = \sum_{i=1}^{n} f(i) + f(n+1)$ — the "peel off the last term" move, which is the engine of induction.
$\displaystyle \sum_{i=1}^{n} c \cdot f(i) = c \sum_{i=1}^{n} f(i)$ — constants pull out.
$\displaystyle \sum_{i=1}^{n}\bigl(f(i) + g(i)\bigr) = \sum_{i=1}^{n} f(i) + \sum_{i=1}^{n} g(i)$ — linearity.

Quick check: if $P(n)$ is "$1 + 2 + \cdots + n = n(n+1)/2$", what does $P(4)$ assert? Enter the right-hand side as a single number.

STEP 3 OF 22 · Phase 1 · Visual Intuition

Visual — Dominoes, ladders, and the 3-step framework

Three pictures, one idea. Induction is just: (1) push the first domino, (2) make sure every domino topples its neighbour. Memorise the shape — every proof you write today follows it.

Picture ① — The dominoes

Push the first domino ($P(1)$). The "if $P(k)$ then $P(k+1)$" rule guarantees every neighbour topples. So all of $\mathbb{N}$ falls.

Picture ② — The ladder

Climbing a ladder: you stand on rung $k$ ($P(k)$ is true), then step up to rung $k+1$ ($P(k+1)$). Doing so once shows you can keep climbing forever.

Picture ③ — The 3-step framework box

The 3-step induction template. Step 1 and Step 2 are mostly writing. Step 3 is where the real algebra happens.

🔑 Mark allocation insight. AIMO graders give partial credit by step. Writing the base case ("$P(1)$: LHS $=$ RHS, ✓") earns 1 mark even with no further work. Writing the inductive hypothesis sentence ("Assume $P(k)$") earns another. So just by setting up the right scaffold you bank 2/5 — even before any algebra.

STEP 4 OF 22 · Phase 1.5 · Formula Manual

Formula manual — 5 sentence templates

Every clean induction proof uses the same five sentences. Memorise them. When you sit down in the exam, you write these first, then fill the algebra in afterwards.

F1 · Base case sentence

"Base case: when $n = 1$, LHS $= \ldots$ and RHS $= \ldots$, so $P(1)$ holds."

Tip

Compute both sides separately, then write "✓" or "$\therefore$ true". Marker can see at a glance.

F2 · Inductive hypothesis (IH) sentence

"Assume $P(k)$ holds for some integer $k \ge 1$: that is, $\ldots = \ldots$."

Tip

Write the actual equation/inequality of $P(k)$ here in full, even if it looks long. It will be re-used as a substitution in Step 3.

F3 · Inductive step opening

"We now show $P(k+1)$, i.e. $\ldots = \ldots$."

Tip

Write what $P(k+1)$ actually says. This is your goal — having it in front of you keeps the algebra honest.

F4 · The key substitution (the move that uses IH)

"$\text{LHS of } P(k+1) = \text{LHS of } P(k) + (\text{new term}) \stackrel{\text{IH}}{=} \ldots$"

Tip

Mark the step where you substituted IH with "$\stackrel{\text{IH}}{=}$" or "(by IH)". This earns the substitution mark.

F5 · Conclusion sentence

"Therefore $P(k+1)$ holds. By induction, $P(n)$ is true for all $n \ge 1$. $\blacksquare$"

Tip

The $\blacksquare$ or "QED" is not decoration — markers explicitly look for the closing sentence. 1 mark.

Drill: Write these five templates on the back of your scratch paper before reading the next step. By the end of today you should be able to produce them with eyes closed.

STEP 5 OF 22 · Phase 2 · Derivation ①

Derivation ① — Prove $1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$

The mother of all induction examples. Follow the 3-step framework. We write all five sentences (F1–F5) explicitly.

Claim: For every integer $n \ge 1$, $\displaystyle 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$.

Step 1 · Base case (F1)

When $n = 1$: LHS $= 1$. RHS $= \dfrac{1 \cdot 2}{2} = 1$. So LHS $=$ RHS, and $P(1)$ holds. ✓

Step 2 · Inductive hypothesis (F2)

Assume $P(k)$ holds for some integer $k \ge 1$. That is,

$1 + 2 + \cdots + k = \dfrac{k(k+1)}{2}$. (IH)

Step 3 · Inductive step (F3 + F4)

We show $P(k+1)$: that is, $1 + 2 + \cdots + k + (k+1) = \dfrac{(k+1)(k+2)}{2}$.

$1 + 2 + \cdots + k + (k+1)$ $\stackrel{\text{IH}}{=} \dfrac{k(k+1)}{2} + (k+1)$ (substitute IH) $= \dfrac{k(k+1) + 2(k+1)}{2}$ (common denominator) $= \dfrac{(k+1)(k+2)}{2}$. (factor out $(k+1)$)

Step 4 · Conclusion (F5)

Therefore $P(k+1)$ holds. By induction, $P(n)$ is true for all $n \ge 1$. $\blacksquare$

🔑 Anatomy: the whole proof is just five sentences with two lines of algebra. The hard part — getting from $\dfrac{k(k+1)}{2} + (k+1)$ to $\dfrac{(k+1)(k+2)}{2}$ — is exactly the move "add the next term to both sides of IH and simplify". Memorise this move.

STEP 6 OF 22 · Phase 2 · Derivation ②

Derivation ② — Prove $1 + 3 + 5 + \cdots + (2n-1) = n^2$

The sum of the first $n$ odd numbers equals a perfect square. Same 3-step shape, slightly different algebra.

Claim: For every integer $n \ge 1$, $1 + 3 + 5 + \cdots + (2n-1) = n^2$.

Step 1 · Base case

$n = 1$: LHS $= 1$. RHS $= 1^2 = 1$. ✓

Step 2 · Inductive hypothesis

Assume $1 + 3 + 5 + \cdots + (2k-1) = k^2$ for some $k \ge 1$. (IH)

Step 3 · Inductive step

We show that $1 + 3 + 5 + \cdots + (2k-1) + (2(k+1) - 1) = (k+1)^2$.

$1 + 3 + \cdots + (2k-1) + (2k+1)$ $\stackrel{\text{IH}}{=} k^2 + (2k+1)$ (substitute IH) $= k^2 + 2k + 1$ $= (k+1)^2$. (complete the square)

Step 4 · Conclusion

By induction, $1 + 3 + 5 + \cdots + (2n-1) = n^2$ for all $n \ge 1$. $\blacksquare$

🔑 Pattern: in summation identities, the inductive step always goes "left side of $P(k+1)$ = left side of $P(k)$ + (new term)". Then you substitute IH and simplify the right side until it matches $P(k+1)$'s right side.

STEP 7 OF 22 · Phase 2 · Derivation ③

Derivation ③ — Prove $2^n > n$ for all $n \ge 1$

First inequality induction. The move is the same shape, but instead of an "=", we chain "$>$"s.

Claim: For every integer $n \ge 1$, $2^n > n$.

Step 1 · Base case

$n = 1$: $2^1 = 2 > 1$. ✓

Step 2 · Inductive hypothesis

Assume $2^k > k$ for some $k \ge 1$. (IH)

Step 3 · Inductive step

We show that $2^{k+1} > k+1$.

$2^{k+1} = 2 \cdot 2^k$ $\stackrel{\text{IH}}{>} 2k$ (use IH: $2^k > k$, multiply by 2) $= k + k$ $\ge k + 1$ (since $k \ge 1$)

So $2^{k+1} > k+1$.

Step 4 · Conclusion

By induction, $2^n > n$ for all $n \ge 1$. $\blacksquare$

🔑 Inequality move: when the IH is "$X > Y$" and you want "$X' > Y'$", you typically (i) write $X'$ in terms of $X$, (ii) apply IH to replace $X$ with something $\ge Y$, (iii) finish with simple inequalities. Always state which step uses IH.

STEP 8 OF 22 · WE 1 · ⭐⭐

Worked Example 1 — Triangular sum (verify at $n = 10$)

Same identity as Derivation ①, but now you fill in the value at a specific $n$ to lock in the formula. This builds computational confidence on top of the proof.

WE 1 ⭐⭐ · Skill P1-A1 (3-step framework)

Use the identity $1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$ (which we proved in Step 5). Compute the value of $1 + 2 + \cdots + 10$ and submit the answer below.

By the formula at $n = 10$: $\dfrac{10 \cdot 11}{2} = \dfrac{110}{2} = 55$.

Your answer (integer)

$\therefore 1 + 2 + \cdots + 10 = 55$.

STEP 9 OF 22 · WE 2 · ⭐⭐⭐

Worked Example 2 — Sum of squares identity

A famous identity. Worth memorising. The inductive step requires factoring a cubic — careful algebra.

WE 2 ⭐⭐⭐ · Skill P1-A1 (3-step framework)

Claim: For every $n \ge 1$, $\displaystyle 1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}$. Verify by computing the value at $n = 5$.

Proof (sketch)

Base ($n=1$): LHS $= 1$. RHS $= \dfrac{1 \cdot 2 \cdot 3}{6} = 1$. ✓

IH: $1^2 + 2^2 + \cdots + k^2 = \dfrac{k(k+1)(2k+1)}{6}$ for some $k \ge 1$.

Step:

$1^2 + \cdots + k^2 + (k+1)^2 \stackrel{\text{IH}}{=} \dfrac{k(k+1)(2k+1)}{6} + (k+1)^2$ $= \dfrac{(k+1)\bigl[k(2k+1) + 6(k+1)\bigr]}{6}$ $= \dfrac{(k+1)(2k^2 + 7k + 6)}{6} = \dfrac{(k+1)(k+2)(2k+3)}{6}$.

This matches $P(k+1)$ with $n$ replaced by $k+1$. ✓

At $n = 5$: $\dfrac{5 \cdot 6 \cdot 11}{6} = \dfrac{330}{6} = 55$.

Compute $1^2 + 2^2 + 3^2 + 4^2 + 5^2$

$\therefore 1^2 + 2^2 + 3^2 + 4^2 + 5^2 = 55$.

STEP 10 OF 22 · WE 3 · ⭐⭐⭐⭐

Worked Example 3 — Divisibility: $6 \mid n^3 - n$

First divisibility induction. The inductive step needs algebraic manipulation plus a small parity observation.

WE 3 ⭐⭐⭐⭐ · Skill P1-A2 (divisibility induction)

Claim: For every $n \ge 1$, $6 \mid n^3 - n$ (i.e. $n^3 - n$ is divisible by $6$).

Proof

Base ($n=1$): $1^3 - 1 = 0$, and $6 \mid 0$. ✓

IH: Assume $6 \mid k^3 - k$ for some $k \ge 1$.

Step: We show $6 \mid (k+1)^3 - (k+1)$.

$(k+1)^3 - (k+1)$ $= k^3 + 3k^2 + 3k + 1 - k - 1$ $= (k^3 - k) + (3k^2 + 3k)$ $= (k^3 - k) + 3k(k+1)$.

By IH, $6 \mid (k^3 - k)$. For the other term: $k(k+1)$ is the product of two consecutive integers, so it is even, i.e. $2 \mid k(k+1)$. Therefore $6 \mid 3k(k+1)$. The sum of two multiples of $6$ is a multiple of $6$, so $6 \mid (k+1)^3 - (k+1)$.

By induction, $6 \mid n^3 - n$ for all $n \ge 1$. $\blacksquare$

🔑 Pattern for divisibility: rewrite the $(k+1)$-version as (the $k$-version) + (something obviously divisible by $d$). Then both summands are divisible by $d$, hence so is the whole.

STEP 11 OF 22 · WE 4 · ⭐⭐⭐⭐

Worked Example 4 — Fibonacci numbers mod 3 (find the period)

Recurrence problems and periodicity. The key idea: compute the sequence modulo $m$, find where it repeats, and exploit the period. This is the warm-up for AIMO 2016 Q4.

WE 4 ⭐⭐⭐⭐ · Skill P1-A3 (recurrence-sequence induction)

The Fibonacci sequence is $F_1 = 1$, $F_2 = 1$, $F_{n+2} = F_{n+1} + F_n$ for $n \ge 1$. Compute $F_n \pmod{3}$ for $n = 1, 2, 3, \ldots$ and determine the period (the smallest $p$ such that $F_{n+p} \equiv F_n \pmod 3$ for all $n$).

Computation

We work entirely mod 3:

$F_1 \equiv 1, \quad F_2 \equiv 1$ $F_3 \equiv 1 + 1 = 2$ $F_4 \equiv 1 + 2 = 3 \equiv 0$ $F_5 \equiv 2 + 0 = 2$ $F_6 \equiv 0 + 2 = 2$ $F_7 \equiv 2 + 2 = 4 \equiv 1$ $F_8 \equiv 2 + 1 = 3 \equiv 0$ $F_9 \equiv 1 + 0 = 1$ $F_{10} \equiv 0 + 1 = 1$

The sequence mod 3 reads: $1, 1, 2, 0, 2, 2, 1, 0, 1, 1, \ldots$ — and $(F_9, F_{10}) = (1, 1) = (F_1, F_2)$, so the sequence repeats with period 8.

Period of $F_n \pmod 3$

$\therefore$ the period is $8$.

🔑 Why this works: there are only finitely many pairs $(a, b) \pmod m$ (exactly $m^2$). So any second-order recurrence mod $m$ must eventually repeat — typically much sooner than $m^2$. Once you see a pair $(F_{j}, F_{j+1})$ equal to $(F_1, F_2)$, the sequence repeats forever from there.

STEP 12 OF 22 · WE 5 · ⭐⭐⭐⭐⭐

Worked Example 5 — Prove $2^n > n^2$ for $n \ge 5$

Sharper inequality induction. The base case is not at $n = 1$ — small $n$ values fail. We must start at $n = 5$.

WE 5 ⭐⭐⭐⭐⭐ · Skill P1-A4 (inequality induction)

Claim: For every integer $n \ge 5$, $2^n > n^2$.

Why $n \ge 5$? Check small values: $2^1 = 2$ vs $1^2 = 1$ ✓; $2^2 = 4$ vs $2^2 = 4$ ✗ (not strict); $2^3 = 8$ vs $3^2 = 9$ ✗; $2^4 = 16$ vs $4^2 = 16$ ✗; $2^5 = 32$ vs $5^2 = 25$ ✓. So the inequality only locks in at $n = 5$.

Proof

Base ($n=5$): $2^5 = 32$, $5^2 = 25$. Since $32 > 25$, $P(5)$ holds. ✓

IH: Assume $2^k > k^2$ for some $k \ge 5$.

Step: We show $2^{k+1} > (k+1)^2$.

$2^{k+1} = 2 \cdot 2^k$ $\stackrel{\text{IH}}{>} 2 k^2$ (use IH and multiply by 2)

It remains to show $2k^2 \ge (k+1)^2$ for $k \ge 5$. Expanding:

$2k^2 - (k+1)^2 = 2k^2 - k^2 - 2k - 1 = k^2 - 2k - 1$.

For $k \ge 5$: $k^2 - 2k - 1 \ge 25 - 10 - 1 = 14 > 0$. So $2k^2 > (k+1)^2$, and hence $2^{k+1} > (k+1)^2$. ✓

By induction, $2^n > n^2$ for all $n \ge 5$. $\blacksquare$

🔑 Two-stage inequality trick: when the simple "double IH" step doesn't immediately reach the target, prove the intermediate inequality ($2k^2 \ge (k+1)^2$) separately using simple algebra. Then chain: $2^{k+1} > 2k^2 \ge (k+1)^2$.

STEP 13 OF 22 · Phase 4 · Practice

Practice — 5 problems with Hint / Answer / Solution

Try each on paper. Use the buttons in order: Hint first, then Answer to check, then Solution only if you got stuck.

P1 · ⭐⭐ · sum identity

Prove by induction: $\displaystyle 1 + 2 + 3 + \cdots + n = \dfrac{n(n+1)}{2}$. Then compute the sum $1 + 2 + \cdots + 100$.

Same as Step 5. Use the 3-step framework; at $n = 100$, evaluate $\frac{100 \cdot 101}{2}$.

$5050$.

Identity is proved in Step 5. At $n = 100$: $\frac{100 \cdot 101}{2} = \frac{10100}{2} = 5050$. (Gauss's classic schoolboy answer.)

P2 · ⭐⭐⭐ · sum of cubes

Prove by induction: $\displaystyle 1^3 + 2^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$. Compute the sum for $n = 4$.

Inductive step: $1^3 + \cdots + k^3 + (k+1)^3 \stackrel{\text{IH}}{=} \left(\frac{k(k+1)}{2}\right)^2 + (k+1)^3$. Factor $(k+1)^2$ out.

For $n = 4$: $1 + 8 + 27 + 64 = 100 = \left(\frac{4 \cdot 5}{2}\right)^2 = 10^2 = 100$.

Base $n=1$: $1 = 1$. Step: $\left(\frac{k(k+1)}{2}\right)^2 + (k+1)^3 = \frac{(k+1)^2}{4}\bigl[k^2 + 4(k+1)\bigr] = \frac{(k+1)^2 (k+2)^2}{4} = \left(\frac{(k+1)(k+2)}{2}\right)^2$. ✓ Beautiful "the sum of cubes is the square of the sum" identity.

P3 · ⭐⭐⭐ · divisibility

Prove that $3 \mid n^3 + 2n$ for every $n \ge 1$.

$(k+1)^3 + 2(k+1) = k^3 + 3k^2 + 3k + 1 + 2k + 2 = (k^3 + 2k) + 3(k^2 + k + 1)$.

Proved. ($n = 1$: $1 + 2 = 3$ ✓; etc.)

Base $n=1$: $1 + 2 = 3$. ✓ IH: $3 \mid k^3 + 2k$. Step: $(k+1)^3 + 2(k+1) = (k^3 + 2k) + 3(k^2 + k + 1)$. Both pieces are divisible by 3 (first by IH, second is $3 \cdot \text{integer}$). So $3 \mid (k+1)^3 + 2(k+1)$. By induction, done.

P4 · ⭐⭐⭐⭐ · inequality

Prove $n! > 2^n$ for all $n \ge 4$. (Hint: check base $n = 4$, then induct.)

Inductive step: $(k+1)! = (k+1) \cdot k! \stackrel{\text{IH}}{>} (k+1) \cdot 2^k$. Then show $(k+1) \cdot 2^k > 2^{k+1}$, i.e. $k+1 > 2$.

Proved. ($n = 4$: $24 > 16$ ✓.)

Base $n=4$: $4! = 24$, $2^4 = 16$, so $24 > 16$. ✓ IH: $k! > 2^k$ for some $k \ge 4$. Step: $(k+1)! = (k+1) \cdot k! \stackrel{\text{IH}}{>} (k+1) \cdot 2^k > 2 \cdot 2^k = 2^{k+1}$ since $k+1 > 2$. ✓

P5 · ⭐⭐⭐⭐ · geometric sum

Prove by induction: $\displaystyle 1 + r + r^2 + \cdots + r^n = \frac{r^{n+1} - 1}{r - 1}$ for any $r \ne 1$ and all $n \ge 0$.

$1 + r + \cdots + r^k + r^{k+1} \stackrel{\text{IH}}{=} \frac{r^{k+1} - 1}{r-1} + r^{k+1}$. Combine over common denominator.

Proved.

Base $n=0$: LHS $= 1$, RHS $= \frac{r-1}{r-1} = 1$ ✓. IH: $1 + r + \cdots + r^k = \frac{r^{k+1} - 1}{r-1}$. Step: $1 + r + \cdots + r^k + r^{k+1} = \frac{r^{k+1} - 1}{r-1} + r^{k+1} = \frac{r^{k+1} - 1 + r^{k+1}(r-1)}{r-1} = \frac{r^{k+2} - 1}{r-1}$. ✓

STEP 14 OF 22 · Phase 5 · AIMO 2016 Q4

AIMO 2016 Q4 — The 3-mark recurrence question

Now the real thing. AIMO 2016 Question 4, 3 marks. This is the canonical "recurrence sequence + last-digit + period" combo. Read carefully, then work through the 5 hints on the right.

AIMO 2016 · Q4 · ⭐⭐⭐ · 3 marks

The problem

A sequence is formed by the following rules: $s_1 = 1$, $s_2 = 2$ and $s_{n+2} = s_n^2 + s_{n+1}^2$ for all $n \ge 1$. What is the last digit of the term $s_{200}$?

Observe

$s_3 = 1^2 + 2^2 = 5$, $s_4 = 4 + 25 = 29$, $s_5 = 25 + 841 = 866$ — already the values are exploding. We obviously cannot compute $s_{200}$ directly. But we don't need the value — only the last digit. So we work mod 10.

Strategy

(1) Compute the sequence of last digits using only mod-10 arithmetic. (2) Watch for repetition: any time a consecutive pair $(s_j, s_{j+1}) \bmod 10$ equals $(s_1, s_2) \bmod 10 = (1, 2)$, the sequence repeats from there. (3) Use the period to find which earlier term has the same last digit as $s_{200}$.

Why this is a general technique

Any second-order recurrence mod $m$ must become periodic. Reason: there are only $m^2$ possible pairs $(a, b) \pmod m$. After $m^2 + 1$ pairs, some pair has appeared twice, and from there the sequence repeats. So the "compute mod $m$ until repetition" strategy always works for these problems — the only question is how long the period is.

Last digit of $s_{200}$ (integer 0–9)

Skill linkage: recurrence + mod $m$ + periodicity ⇒ skill P1-A3 (recurrence-sequence induction). The "compute pairs mod $m$ until repetition" pattern shows up at least once per AIMO paper.

📚 Hints — open one at a time

Hint 1 — reduce mod 10. The last digit of any integer $x$ is $x \bmod 10$. Importantly, $(s_n^2 + s_{n+1}^2) \bmod 10$ depends only on $s_n \bmod 10$ and $s_{n+1} \bmod 10$. So compute the sequence of last digits using mod-10 arithmetic only.

Hint 2 — compute the first dozen terms. $s_1 \equiv 1, s_2 \equiv 2$. Then $s_3 \equiv 1 + 4 = 5$. $s_4 \equiv 4 + 25 \equiv 4 + 5 = 9$. $s_5 \equiv 25 + 81 \equiv 5 + 1 = 6$. Keep going for at least 14 terms.

Hint 3 — full mod-10 sequence. $1, 2, 5, 9, 6, 7, 5, 4, 1, 7, 0, 9, 1, 2, \ldots$ — the pair $(s_{13}, s_{14}) \equiv (1, 2) \equiv (s_1, s_2)$, so the sequence repeats from there with period 12.

Hint 4 — find which earlier term matches $s_{200}$. Since the period is 12, $s_{200} \equiv s_{200 - 12k}$ for any $k$. Compute $200 \bmod 12$: $200 = 16 \cdot 12 + 8$, so $200 \equiv 8 \pmod{12}$, meaning $s_{200}$ has the same last digit as $s_8$.

Hint 5 — read off the answer. From the list $1, 2, 5, 9, 6, 7, 5, 4, 1, 7, 0, 9$ (indexed $s_1$ through $s_{12}$), the 8th entry is 4. So the last digit of $s_{200}$ is $\boxed{4}$.

stuck after all 5 hints?

Full solution

We work modulo 10 throughout, recording only the last digit of each $s_n$:

$s_1 \equiv 1$ $s_2 \equiv 2$ $s_3 \equiv 1^2 + 2^2 = 1 + 4 = 5$ $s_4 \equiv 2^2 + 5^2 = 4 + 25 \equiv 4 + 5 = 9$ $s_5 \equiv 5^2 + 9^2 = 25 + 81 \equiv 5 + 1 = 6$ $s_6 \equiv 9^2 + 6^2 = 81 + 36 \equiv 1 + 6 = 7$ $s_7 \equiv 6^2 + 7^2 = 36 + 49 \equiv 6 + 9 = 15 \equiv 5$ $s_8 \equiv 7^2 + 5^2 = 49 + 25 \equiv 9 + 5 = 14 \equiv 4$ $s_9 \equiv 5^2 + 4^2 = 25 + 16 \equiv 5 + 6 = 11 \equiv 1$ $s_{10} \equiv 4^2 + 1^2 = 16 + 1 \equiv 6 + 1 = 7$ $s_{11} \equiv 1^2 + 7^2 = 1 + 49 \equiv 1 + 9 = 10 \equiv 0$ $s_{12} \equiv 7^2 + 0^2 = 49 + 0 \equiv 9$ $s_{13} \equiv 0^2 + 9^2 = 0 + 81 \equiv 1$ $s_{14} \equiv 9^2 + 1^2 = 81 + 1 \equiv 1 + 1 = 2$.

Now $(s_{13}, s_{14}) \equiv (1, 2) \equiv (s_1, s_2)$. The recurrence depends only on the previous two values, so from this point onwards the sequence repeats with period $12$:

$s_{n+12} \equiv s_n \pmod{10}$ for all $n \ge 1$.

To find $s_{200} \bmod 10$, write $200 = 16 \cdot 12 + 8$, so $200 \equiv 8 \pmod{12}$. Hence $s_{200} \equiv s_8 \equiv 4 \pmod{10}$.

$\therefore$ the last digit of $s_{200}$ is $4$.

STEP 15 OF 22 · Phase 5.5 · Synthesis

Synthesis — Prove $6 \mid 7^n - 1$ for all $n \ge 1$

Write the full 3-step induction proof in the textarea below. The grader scores how many rubric keywords you used (out of 5). This trains the writing reflex.

Claim: For every integer $n \ge 1$, $6 \mid 7^n - 1$.

Setup hint: $7^{k+1} - 1 = 7 \cdot 7^k - 1 = 7(7^k - 1) + 6$. By IH, $6 \mid 7^k - 1$, so $6 \mid 7(7^k - 1)$. Also $6 \mid 6$. Therefore $6 \mid 7^{k+1} - 1$.

Rubric — your proof must mention

"base case" — verify at $n = 1$.
"assume" — state the inductive hypothesis at $n = k$.
"inductive" — announce the inductive step.
"show" (or "prove") — what you intend to derive.
"therefore" — conclude by induction.

STEP 16 OF 22 · Atomic-Skill Matrix

Atomic-skill matrix — the four skills you just trained

Every induction problem you solved today decomposed into one of four atomic skills. Memorise which is which — when you face a new problem, name the skill first, then apply the standard recipe.

Code	Skill	Trigger	Standard recipe
`P1-A1`	3-step framework: state → base → step	"Prove $P(n)$ for all $n \ge n_0$."	F1 base, F2 IH, F3+F4 inductive step, F5 conclusion. Use for identities and counting formulas.
`P1-A2`	Divisibility induction	"Prove $d \mid f(n)$ for all $n \ge n_0$."	Rewrite $f(k+1) = f(k) + (\text{a multiple of } d)$. IH gives $d \mid f(k)$, and the new term is obviously divisible by $d$. Therefore $d \mid f(k+1)$.
`P1-A3`	Recurrence-sequence induction (periods mod $m$)	"Last digit of $a_{200}$" / "$a_n \bmod m$" / "$a_n$ defined by $a_{n+2} = \ldots$"	Compute sequence mod $m$. Watch for repeated pair $(a_j, a_{j+1})$. Period $p$ is established; use $n \bmod p$ to read off the answer.
`P1-A4`	Inequality induction	"Prove $f(n) > g(n)$" or "$f(n) < g(n)$" for all $n \ge n_0$.	Find the right starting $n_0$ by testing small values. F1–F2 as usual. In F4, after using IH, prove an intermediate inequality (often a polynomial inequality in $k$). Chain: target $> $ IH-output $\ge $ goal.

STEP 17 OF 22 · Micro-Validations

Micro-validations — one quick check per skill

Quick sanity checks. If you fail any of these, return to the corresponding worked example before moving on.

MV1 · P1-A1. Using $1+2+\cdots+n = \frac{n(n+1)}{2}$, compute $1+2+\cdots+20$.

MV2 · P1-A2. What is $n^3 - n$ at $n = 4$? (Verify divisibility by 6.)

MV3 · P1-A3. In WE 4 (Fibonacci mod 3), what is $F_{17} \bmod 3$? Hint: $17 \bmod 8 = 1$, so $F_{17} \equiv F_1$.

MV4 · P1-A4. In WE 5, the inequality $2^n > n^2$ starts working at which $n$? (Smallest such $n$.)

STEP 18 OF 22 · Cheat Sheet

Cheat sheet — print this and pin it next to your desk

Every induction proof you write for the next 4 weeks should mirror this template.

The 3-step framework

Base case ($n = n_0$): directly verify $P(n_0)$. Show LHS and RHS separately. (1 mark)
Inductive hypothesis (IH): assume $P(k)$ holds for some integer $k \ge n_0$. Write the exact equation/inequality. (1 mark)
Inductive step: using IH, show $P(k+1)$. Mark the IH substitution with "(by IH)" or $\stackrel{\text{IH}}{=}$. (2–3 marks)
Close with: "By induction, $P(n)$ is true for all $n \ge n_0$. $\blacksquare$" (1 mark)

The 5 sentence templates (F1–F5)

F1: "Base case: when $n = 1$, LHS $= \ldots$ and RHS $= \ldots$. ✓"
F2: "Assume $P(k)$ holds for some $k \ge 1$: that is, $\ldots = \ldots$."
F3: "We now show $P(k+1)$, i.e. $\ldots = \ldots$."
F4: "$\text{LHS}(k+1) = \text{LHS}(k) + (\text{new term}) \stackrel{\text{IH}}{=} \ldots = \text{RHS}(k+1)$."
F5: "Therefore $P(k+1)$ holds. By induction, $P(n)$ is true for all $n \ge 1$. $\blacksquare$"

Common pitfalls

Forgetting the base case. Without it, the chain has no first link.
Wrong base case. $2^n > n^2$ fails for $n = 2, 3, 4$. You must check small values.
Using $P(k+1)$ to prove $P(k+1)$. Don't assume what you want — only $P(k)$.
Forgetting the conclusion sentence. Costs 1 mark every time.
Not labelling the IH substitution. Marker can't see where you used the hypothesis.

STEP 19 OF 22 · Self-Assessment

⭐ Self-assessment — rate your mastery of each skill

For each atomic skill, click 1–3 stars: ⭐ = "I can follow it"; ⭐⭐ = "I can do it with a hint"; ⭐⭐⭐ = "I can write it from scratch under exam pressure".

P1-A1 · 3-step framework. Identities like $\sum k = n(n+1)/2$, $\sum k^2$, etc.

P1-A2 · Divisibility induction. $6 \mid n^3 - n$, $6 \mid 7^n - 1$, etc.

P1-A3 · Recurrence + periodicity mod $m$. AIMO 2016 Q4-style.

P1-A4 · Inequality induction. $2^n > n^2$, $n! > 2^n$, etc.

⭐ 0 / 12 — click stars

STEP 20 OF 22 · Error Book

📒 Error book — your personal mistake log

Every time you got an answer wrong today, it was silently saved here. Review these before moving on. Coming back to this list once a week is one of the highest-leverage habits in olympiad training.

Errors logged this session

No errors yet — submit some practice answers and AIMO problems first.

Drill: for each error, write on paper (a) which atomic skill it belongs to, (b) the one move that would have saved you, (c) one fresh problem you can solve to lock that move in.

STEP 21 OF 22 · Wrap-Up

🎉 Wrap-up — what you can do now

Take stock. Today's lesson installed one of the two foundational proof techniques for the entire AIMO syllabus.

Today's takeaways

The 3-step framework is universal: base → IH → inductive step. Every induction proof you ever write follows it.
Five sentence templates (F1–F5) give you a fill-in scaffold worth 2/5 marks before any algebra.
Four atomic skills (P1-A1 to P1-A4) cover ~80% of olympiad induction problems: sum identities, divisibility, recurrences mod $m$, and inequalities.
Recurrences mod $m$ always periodicise (only $m^2$ possible pairs). When you see "last digit of $a_{200}$", reach for this technique.
Inequality induction needs the right $n_0$. Always check small values to find where the inequality first holds.

🔑 Pass 1 / Pass 2 strategy. Today (Pass 1) you mastered the basic 3-step shape. In W15 (Pass 2) we'll add: strong induction (assume $P(1), P(2), \ldots, P(k)$), double induction (induct on two variables), structural induction (induct over trees/graphs), and the extremal principle. Don't worry — the 3-step shape is still the core; these are just upgrades.

Stuck? Try in order:

Re-read the F1–F5 sentence templates (Step 4).
Re-do Phase 2 derivations 1, 2, 3 (Steps 5–7) on paper, watching the proof shape.
Open the relevant worked example (Steps 8–12) and follow each calc line one at a time.
For AIMO 2016 Q4, walk through the 5 hints in order — each unlocks a stage.

Common slip-ups today:

Forgetting the "$\blacksquare$" / "Therefore by induction" — costs the conclusion mark.
Not labelling where IH was used (e.g. "$\stackrel{\text{IH}}{=}$") — costs the substitution mark.
For $2^n > n^2$, missing that the base case is $n = 5$ (not $n = 1$).
For AIMO 2016 Q4, trying to compute $s_{200}$ directly instead of working mod 10.

STEP 22 OF 22 · Bridge

🏁 Bridge to Part 2 — Proof by Contradiction

You've banked one of the two great Pass-1 proof techniques. Next session: the other one — proof by contradiction.

Coming up in Part 2 (Proof by Contradiction Basics): the 4-step shape assume → derive → contradict → conclude. We'll prove $\sqrt{2}$ is irrational (the most famous proof in mathematics), Euclid's theorem on infinitely many primes, and attack AIMO 2018 Q9 for partial marks. The contradiction technique is your second tool for "Prove that…" problems — and the natural complement to induction.

→ Open Part 2: Proof by Contradiction Basics

Before you leave today: on a single A4 page, write out the 3-step induction framework + the 5 sentence templates F1–F5 from memory. Pin it on the wall next to your desk. Tomorrow morning, repeat the exercise — should take less than 90 seconds. After 5 days it's permanent.

— End of Week 11 · Part 1 · Math Induction Basics —