Exercises — Mathematical induction — principle, steps, problems

The left side is the sum of the first $n$ odd numbers. The $n$-th odd number is $2n-1$ (check: $n=1\to 1$, $n=2\to 3$, $n=3\to 5$).

• $P(n_0)=P(1):1=1^2=1$. ✓ (True, so the first domino stands.)
• $P(3):1+3+5=9=3^2$. ✓
• IH $P(k):1+3+5+\cdots +(2k-1)=k^2$.

Nothing to prove yet — this is just correct reading of the statement.

• Base $P(n_0)=P(1)$: $3^1=3$ and $2(1)+1=3$, so $3\ge 3$. ✓ (Equality is allowed by "$\ge$".)
• To build $P(k+1)$, take the original statement $P(n):3^n\ge 2n+1$ and replace every $n$ by $k+1$. The full sentence is: $P(k+1):3^{k+1}\ge 2(k+1)+1=2k+3.$ So $P(k+1)$ is the claim "$3^{k+1}\ge 2k+3$" — writing it out in full like this is exactly what step 4 of the template asks you to target.

Base $P(n_0)=P(1)$: LHS $=1$, RHS $=1^2=1$. ✓ IH: assume $1+3+\cdots +(2k-1)=k^2$. Step: the next odd number after $2k-1$ is $2(k+1)-1=2k+1$. Add it to both sides: $\underset{\text{use IH}}{\underbrace{1+3+\cdots +(2k-1)}}+(2k+1)=k^2+(2k+1).$ Why add exactly $2k+1$? Because $P(k+1)$'s left side is $P(k)$'s left side plus one more odd number, and that number is $2k+1$. $k^2+2k+1=(k+1{)}^2.$ This is precisely $P(k+1)$. Conclusion: the base $P(1)$ holds, and we showed $P(k)\Rightarrow P(k+1)$ for every $k\ge 1$; so the chain covers $1\to 2\to 3\to \cdots$ — by PMI, $P(n)$ is true for all $n\ge 1$. ∎

Base $P(1)$: LHS $=1$, RHS $={\left(\frac{1\cdot 2}{2}\right)}^2=1$. ✓ IH: $1^3+\cdots +k^3={\left(\frac{k(k+1)}{2}\right)}^2=\frac{k^2(k+1{)}^2}{4}$. Step: add the next cube $(k+1{)}^3$: $\frac{k^2(k+1{)}^2}{4}+(k+1{)}^3=(k+1{)}^2\left[\frac{k^2}{4}+(k+1)\right].$ Why factor out $(k+1{)}^2$ first? The target formula has $(k+1{)}^2$ as a factor of its numerator, so pulling it out early steers us there. $=(k+1{)}^2\cdot \frac{k^2+4(k+1)}{4}=(k+1{)}^2\cdot \frac{k^2+4k+4}{4}=(k+1{)}^2\cdot \frac{(k+2{)}^2}{4}.$ $={\left(\frac{(k+1)(k+2)}{2}\right)}^2,$ which is $P(k+1)$. Conclusion: base $P(1)$ true and $P(k)\Rightarrow P(k+1)$ for all $k\ge 1$, so by PMI the formula holds for every $n\ge 1$. ∎

Telescoping insight (motivation), read off the figure: partial fractions give $\frac{1}{i(i+1)}=\frac{1}{i}-\frac{1}{i+1}$. So the sum is $\left(\frac{1}{1}-\frac{1}{2}\right)+\left(\frac{1}{2}-\frac{1}{3}\right)+\cdots +\left(\frac{1}{n}-\frac{1}{n+1}\right)$; every interior $-\frac{1}{i}$ (a pink half) cancels the next $+\frac{1}{i}$ (the blue half of the following row), exactly as the yellow arrows show, leaving the surviving pair $\frac{1}{1}-\frac{1}{n+1}=\frac{n}{n+1}$. Induction now confirms this rigorously.

Base $P(1)$: LHS $=\frac{1}{1\cdot 2}=\frac{1}{2}$, RHS $=\frac{1}{2}$. ✓ IH: $\sum _{i=1}^k\frac{1}{i(i+1)}=\frac{k}{k+1}$. Step: add the next term $\frac{1}{(k+1)(k+2)}$: $\frac{k}{k+1}+\frac{1}{(k+1)(k+2)}=\frac{k(k+2)+1}{(k+1)(k+2)}=\frac{k^2+2k+1}{(k+1)(k+2)}.$ Why a common denominator $(k+1)(k+2)$? Both fractions share $(k+1)$; the new term contributes $(k+2)$, so the least common denominator is their product. $=\frac{(k+1{)}^2}{(k+1)(k+2)}=\frac{k+1}{k+2},$ which is $P(k+1)$ (replace $n$ by $k+1$ in $\frac{n}{n+1}$). Conclusion: base $P(1)$ holds and $P(k)\Rightarrow P(k+1)$ for all $k\ge 1$; by PMI the identity holds for every $n\ge 1$. ∎

Choosing $n_0$. Test small cases: $n=1:2>1$ ✓; $n=2:4=4$ ✗ (not strictly greater); $n=3:8<9$ ✗; $n=4:16=16$ ✗; $n=5:32>25$ ✓. The statement is false for $n=2,3,4$, so the first standing domino is $n_0=5$.

Base $P(n_0)=P(5)$: $2^5=32>25=5^2$. ✓ IH: assume $2^k>k^2$ for a fixed $k\ge 5$. Step: $2^{k+1}=2\cdot 2^k>2k^2$ (by IH). Why multiply IH by 2? Multiplying by $2$ turns $2^k$ into $2^{k+1}$, the quantity we need. Now we want $2k^2\ge (k+1{)}^2$. Check: $2k^2-(k+1{)}^2=2k^2-k^2-2k-1=k^2-2k-1=(k-1{)}^2-2.$ For $k\ge 5$, $(k-1{)}^2\ge 16>2$, so $2k^2-(k+1{)}^2\ge 14>0$, i.e. $2k^2>(k+1{)}^2$. Chaining: $2^{k+1}>2k^2>(k+1{)}^2,$ which is $P(k+1)$. Conclusion: base $P(5)$ holds and $P(k)\Rightarrow P(k+1)$ for all $k\ge 5$, so the chain starting at $5$ covers every $n\ge 5$; by PMI, $P(n)$ is true for all $n\ge 5$. ∎

Choosing $n_0$. $n=1:1>2$ ✗; $n=2:2>4$ ✗; $n=3:6>8$ ✗; $n=4:24>16$ ✓. First standing domino at $n_0=4$. Base $P(n_0)=P(4)$: $4!=24>16=2^4$. ✓ IH: $k!>2^k$ for fixed $k\ge 4$. Step: $(k+1)!=(k+1)\cdot k!>(k+1)\cdot 2^k$ (by IH). Why? $(k+1)!$ is $(k+1)$ times $k!$, so multiply the IH by $(k+1)$. Since $k\ge 4$, we have $k+1\ge 5>2$, so $(k+1)\cdot 2^k>2\cdot 2^k=2^{k+1}.$ Hence $(k+1)!>2^{k+1}$, which is $P(k+1)$. Conclusion: base $P(4)$ true and $P(k)\Rightarrow P(k+1)$ for all $k\ge 4$, so by PMI $P(n)$ holds for all $n\ge 4$. ∎

Base $P(n_0)=P(1)$: $7-3=4$, and $4\mid 4$. ✓ IH: $4\mid 7^k-3^k$, i.e. $7^k-3^k=4m$ for some integer $m$. Step: we want to build $7^{k+1}-3^{k+1}$ so the old chunk $7^k-3^k$ appears. $7^{k+1}-3^{k+1}=7\cdot 7^k-3\cdot 3^k=7\cdot 7^k-7\cdot 3^k+7\cdot 3^k-3\cdot 3^k.$ Why add and subtract $7\cdot 3^k$? It's the trick that manufactures the difference $7^k-3^k$: the first pair gives $7(7^k-3^k)$, and the rest collapses. $=7(7^k-3^k)+(7-3)\cdot 3^k=7\cdot 4m+4\cdot 3^k=4(7m+3^k).$ Divisible by $4$, so $P(k+1)$ holds. Conclusion: base $P(1)$ holds and $P(k)\Rightarrow P(k+1)$ for all $k\ge 1$; by PMI, $4\mid 7^n-3^n$ for every $n\ge 1$. ∎

Naming the statement. Let $P(n)$ be the claim "$n$ lines in general position divide the plane into $\frac{n^2+n+2}{2}$ regions." To make the counting concrete we write $R(n)$ for the actual number of regions produced by $n$ such lines; then $P(n)$ is precisely the equation $R(n)=\frac{n^2+n+2}{2}$. So proving $P(n)$ means proving this equation, and $R(n)$ is just a name for the left-hand side we manipulate.

Choosing $n_0$: we start at $n_0=0$. Base $P(0)$ (no lines): the whole plane is $1$ region, so $R(0)=1$, and $\frac{0+0+2}{2}=1$. ✓ The base at $n_0=0$ is all PMI requires — we do not need to check $n=1$ separately, since the inductive step (below) will carry $P(0)\Rightarrow P(1)\Rightarrow P(2)\Rightarrow \cdots$ automatically. IH: assume $P(k)$, i.e. $R(k)=\frac{k^2+k+2}{2}$. Step — reading the figure: draw the $(k+1)$-th line (the dashed line in the figure). Because it is parallel to none of the $k$ existing lines, it crosses each of them exactly once — the three coloured dots for $k=3$. These $k$ crossing points cut the new line into $k+1$ pieces (a line cut at $k$ points has $k+1$ segments/rays — count $4$ pieces from $3$ dots in the figure). Why does each piece matter? Every one of those $k+1$ pieces slices an existing region into two (the arrow shows one such split), so it adds exactly one new region. Hence $R(k+1)=R(k)+(k+1)=\frac{k^2+k+2}{2}+(k+1)=\frac{k^2+k+2+2k+2}{2}=\frac{k^2+3k+4}{2}.$ Now check this equals the formula at $k+1$: $\frac{(k+1{)}^2+(k+1)+2}{2}=\frac{k^2+2k+1+k+1+2}{2}=\frac{k^2+3k+4}{2}.✓$ So $R(k+1)$ matches, i.e. $P(k+1)$ holds. Conclusion: base $P(0)$ holds and $P(k)\Rightarrow P(k+1)$ for all $k\ge 0$; by PMI, the region-count formula holds for every $n\ge 0$. ∎

Base $P(n_0)=P(1)$: LHS $=1\cdot 1!=1$, RHS $=2!-1=1$. ✓ IH: $\sum _{i=1}^{k}i\cdot i!=(k+1)!-1$. Step: add the next term $(k+1)\cdot (k+1)!$: $(k+1)!-1+(k+1)\cdot (k+1)!=(k+1)![1+(k+1)]-1.$ Why factor out $(k+1)!$? Both surviving factorial terms share $(k+1)!$; pulling it out reveals the collapse. $=(k+1)!(k+2)-1=(k+2)!-1,$ which is $P(k+1)$ (since $(k+2)!=((k+1)+1)!$). Conclusion: base $P(1)$ holds and $P(k)\Rightarrow P(k+1)$ for all $k\ge 1$; by PMI, the identity holds for every $n\ge 1$. ∎

Because $a_n$ depends on the two previous terms, the inductive step will need both $P(k)$ and $P(k-1)$ — this is exactly when strong induction earns its keep. So we assume all earlier cases.

Base (two dominoes needed, $n_0=1$ and $n_0+1=2$):

• $n=1$: $\frac{2^2+(-1{)}^1}{3}=\frac{4-1}{3}=1=a_1$. ✓
• $n=2$: $\frac{2^3+(-1{)}^2}{3}=\frac{8+1}{3}=\frac{9}{3}=3=a_2$. ✓

Two base cases are required because the recurrence reaches back two steps; without both, the step at $k+1=3$ would have nothing to stand on.

Strong IH: assume the formula $a_i=\frac{2^{i+1}+(-1{)}^i}{3}$ holds for all $i$ with $1\le i\le k$ (where $k\ge 2$). Step: for $k+1\ge 3$ use the recurrence $a_{k+1}=a_k+2a_{k-1}$ and substitute the IH for both $a_k$ and $a_{k-1}$: $a_{k+1}=\frac{2^{k+1}+(-1{)}^k}{3}+2\cdot \frac{2^k+(-1{)}^{k-1}}{3}=\frac{2^{k+1}+(-1{)}^k+2\cdot 2^k+2(-1{)}^{k-1}}{3}.$ Why strong induction here? We needed $a_{k-1}$ as well as $a_k$; ordinary induction only hands us $a_k$. Both $k$ and $k-1$ lie in the range $1\le i\le k$, so the strong IH legally applies to each. Combine the powers of two: $2^{k+1}+2\cdot 2^k=2^{k+1}+2^{k+1}=2^{k+2}$. For the signs, note $(-1{)}^{k-1}=-(-1{)}^k$, so $(-1{)}^k+2(-1{)}^{k-1}=(-1{)}^k-2(-1{)}^k=-(-1{)}^k=(-1{)}^{k+1}$. Therefore $a_{k+1}=\frac{2^{k+2}+(-1{)}^{k+1}}{3},$ which is exactly the formula at $n=k+1$ (replace $n$ by $k+1$ in $\frac{2^{n+1}+(-1{)}^n}{3}$). So $P(k+1)$ holds. Conclusion: both bases $P(1),P(2)$ hold, and for every $k\ge 2$ the truth of all cases $P(1),\dots ,P(k)$ forces $P(k+1)$; so the chain covers every $n\ge 1$. By strong induction, $a_n=\frac{2^{n+1}+(-1{)}^n}{3}$ for all $n\ge 1$. ∎

Base $P(n_0)=P(2)$: $2$ is prime, so it is a product of primes (itself). ✓ Strong IH: assume every integer $m$ with $2\le m\le k$ is a product of primes. Step: consider $n=k+1$. Two cases:

• Case A — $k+1$ is prime. Then it is already a product of one prime. ✓
• Case B — $k+1$ is composite. Then $k+1=a\cdot b$ with $2\le a\le k$ and $2\le b\le k$ (both factors strictly between $1$ and $k+1$). Why can we use the IH now? Both $a$ and $b$ are $\le k$, so the strong IH applies to each: $a$ is a product of primes and $b$ is a product of primes. Multiplying those two prime products gives $k+1$ as a product of primes. ✓

Ordinary induction fails here because the factors $a,b$ are not $k$ — they are arbitrary smaller numbers, exactly the situation strong induction (equivalently, a smallest-counterexample / Well-Ordering argument) handles. Conclusion: base $P(2)$ holds and "all cases up to $k$" $\Rightarrow P(k+1)$ for every $k\ge 2$; by strong induction, every $n\ge 2$ factors into primes. ∎

Did I (1) verify the correct base(s) at the right $n_0$, (2) write the IH as an assumption about a fixed $k$, (3) derive $P(k+1)$ using only what the IH grants me, and (4) write the conclusion line invoking PMI? Base + Hypothesis + Step + Conclusion :::