Exercises — Strong induction

What the recurrence reaches back to: only $b_{n-1}$ — the single immediately-previous term. Why that decides it: ordinary induction hands you exactly one predecessor $P(n-1)$, which is all this step wants. So ordinary induction suffices, with one base case ($b_1=5$). Answer: ordinary induction, 1 base case.

Where the step lands: to compute $c_n$ the recurrence needs $c_{n-1}$ and $c_{n-2}$ — two steps back. Why that forces two bases: the first time you apply the step is at $n=3$, needing $c_2$ and $c_1$. Neither is produced by the recurrence, so both must be given/proved directly. Answer: 2 base cases ($c_1$ and $c_2$), and strong induction because the step uses a predecessor other than $n-1$.

The trouble: a composite $n=ab$ splits into $a,b$ that are somewhere below $n$, but not guaranteed to be $n-1$. Ordinary induction only offers $P(n-1)$ — the wrong number. Answer: Strong induction — you need $P(a)$ and $P(b)$ for unpredictable $a,b<n$, i.e. the whole history. (See Prime Factorisation.)

Sanity check the guess. $a_1=3^1-1=2$ ✅, $a_2=3^2-1=8\ne 5$. ❌ The guess is wrong. Compute a couple: $a_3=5(5)-6(2)=13$. The true closed form is $a_n=3^{n-1}+1$. Check: $3^0+1=2$ ✅, $3^1+1=4\ne 5$ ❌ — also wrong. Solve properly: characteristic $x^2=5x-6\Rightarrow (x-2)(x-3)=0$, roots $2,3$, so $a_n=A\cdot 2^n+B\cdot 3^n$. From $a_1=2,a_2=5$: $2A+3B=2,4A+9B=5\Rightarrow B=\frac{1}{3},A=\frac{1}{2}$. Hmm non-integer — recheck $a_2$: with these, $a_2=4(\frac{1}{2})+9(\frac{1}{3})=2+3=5$ ✅ and $a_1=2(\frac{1}{2})+3(\frac{1}{3})=1+1=2$ ✅. So $a_n=\frac{1}{2}\cdot 2^n+\frac{1}{3}\cdot 3^n=2^{n-1}+3^{n-1}.$ Claim $P(n)$: $a_n=2^{n-1}+3^{n-1}$. Bases: $a_1=2^0+3^0=2$ ✅; $a_2=2^1+3^1=5$ ✅. Two bases because the step reaches back two. Strong step: assume $P(k)$ for all $k<n$ (so for $n-1,n-2$). $a_n=5a_{n-1}-6a_{n-2}=5(2^{n-2}+3^{n-2})-6(2^{n-3}+3^{n-3}).$ Group by base: $2$-terms give $5\cdot 2^{n-2}-6\cdot 2^{n-3}=2^{n-3}(10-6)=4\cdot 2^{n-3}=2^{n-1}$. The $3$-terms give $5\cdot 3^{n-2}-6\cdot 3^{n-3}=3^{n-3}(15-6)=9\cdot 3^{n-3}=3^{n-1}$. So $a_n=2^{n-1}+3^{n-1}=P(n)$. ✅

Claim $P(n)$: $f_n<2^n$. Bases: $f_1=1<2$ ✅; $f_2=1<4$ ✅. Two bases — the step uses $f_{n-1},f_{n-2}$. Strong step: for $n\ge 3$ assume $P(k)$ for all $k<n$. $f_n=f_{n-1}+f_{n-2}<2^{n-1}+2^{n-2}.$ Why this is enough: $2^{n-1}+2^{n-2}=2^{n-2}(2+1)=3\cdot 2^{n-2}<4\cdot 2^{n-2}=2^n.$ So $f_n<2^n$. ✅

Design the step first. For large $n$ we peel off one $4$-cent stamp: if $n-4$ is payable, so is $n$. This step jumps back by 4. How far must the base zone reach? The step needs $n-4\ge 12$, i.e. it only works for $n\ge 16$. So $12,13,14,15$ get no help from the step and must be shown directly. Bases (four of them): $12=4+4+4$; $13=4+4+5$; $14=4+5+5$; $15=5+5+5$. ✅ Strong step: for $n\ge 16$, assume payable for all values in $[12,n)$. Then $12\le n-4<n$, so by hypothesis $n-4$ is payable — add one $4$-stamp to reach $n$. ✅ Answer: 4 base cases, because the step's jump length is $4$ and the base zone starts at $12$.

Trace the first use of the step. The recurrence is first applied at $n=3$: $g_3=g_2+g_1$. This requires both $g_1$ and $g_2$ to be established. The gap: with only $g_1$ proven, the value $g_2$ is unjustified — the domino at position $3$ leans on a domino ($2$) that was never checked. Fix / where it breaks: the chain snaps at $n=3$; you must add the base $g_2=2$. (One base case is never enough when the step reaches back two — see the parent-note mistake box.)

Claim $P(n)$: the integer $n\ge 1$ is a sum of distinct powers of $2$ (i.e. $2^0,2^1,2^2,\dots$, each used at most once). We prove it for all $n\ge 1$; every $n\ge 2$ is then a special case. Base: $P(1)$: $1=2^0$. ✅ (Here $n_0=1$.) Strong step: assume $P(k)$ for all $1\le k<n$. Let $2^m$ be the largest power of $2$ with $2^m\le n$.

• Why largest power: it guarantees the leftover $r=n-2^m$ satisfies $r<2^m$ (else $2^{m+1}\le n$, contradicting maximality). So the leftover is strictly smaller than the piece we removed.
• Case $r=0$: then $n=2^m$, already a single distinct power. ✅
• Case $r\ge 1$: here $1\le r<n$, so the strong hypothesis gives $r$ as a sum of distinct powers of $2$, and every one of them is $<2^m$ (since $r<2^m$). Adding $2^m$ keeps all powers distinct. ✅ Why strong, not ordinary: the leftover $r$ can be any number below $n$, not $n-1$; only the full history covers it.

Find it. Characteristic equation $x^2=x+2\Rightarrow (x-2)(x+1)=0$, roots $2,-1$. So $a_n=A\cdot 2^n+B(-1{)}^n$. From $a_1=1,a_2=8$: $2A-B=1,4A+B=8\Rightarrow 6A=9,A=\frac{3}{2},B=2$. Thus $a_n=\frac{3}{2}\cdot 2^n+2(-1{)}^n=3\cdot 2^{n-1}+2(-1{)}^n.$ Check $a_1=3\cdot 1+2(-1)=1$ ✅, $a_2=3\cdot 2+2(1)=8$ ✅. Claim $P(n)$: $a_n=3\cdot 2^{n-1}+2(-1{)}^n$. Two bases (done above). Strong step: assume $P(n-1),P(n-2)$. $a_n=(3\cdot 2^{n-2}+2(-1{)}^{n-1})+2(3\cdot 2^{n-3}+2(-1{)}^{n-2}).$ $2$-power part: $3\cdot 2^{n-2}+6\cdot 2^{n-3}=3\cdot 2^{n-3}(2+2)=3\cdot 2^{n-3}\cdot 4=3\cdot 2^{n-1}.$ Sign part: $2(-1{)}^{n-1}+4(-1{)}^{n-2}=2(-1{)}^{n-2}((-1)+2)=2(-1{)}^{n-2}=2(-1{)}^n$ (since $(-1{)}^{n-2}=(-1{)}^n$). Sum: $3\cdot 2^{n-1}+2(-1{)}^n=P(n)$. ✅

Upper bound $f_n\le 2^{n-1}$. Bases: $f_1=1\le 2^0=1$ ✅; $f_2=1\le 2^1=2$ ✅. Step ($n\ge 3$): $f_n=f_{n-1}+f_{n-2}\le 2^{n-2}+2^{n-3}=2^{n-3}(2+1)=3\cdot 2^{n-3}\le 4\cdot 2^{n-3}=2^{n-1}$. ✅

Lower bound $f_n\ge (3/2{)}^{n-2}$. Let ${\varphi }_0=3/2$. Bases: $n=1$: $(3/2{)}^{-1}=2/3\approx 0.667\le 1=f_1$ ✅. $n=2$: $(3/2{)}^0=1\le 1=f_2$ ✅. Step ($n\ge 3$): using the hypothesis on $n-1,n-2$, $f_n=f_{n-1}+f_{n-2}\ge {\left(\frac{3}{2}\right)}^{n-3}+{\left(\frac{3}{2}\right)}^{n-4}={\left(\frac{3}{2}\right)}^{n-4}\left(\frac{3}{2}+1\right)={\left(\frac{3}{2}\right)}^{n-4}\cdot \frac{5}{2}.$ Why $5/2$ beats $(3/2{)}^2$: we need this $\ge (3/2{)}^{n-2}=(3/2{)}^{n-4}\cdot (3/2{)}^2=(3/2{)}^{n-4}\cdot 9/4$. Since $5/2=2.5\ge 9/4=2.25$, the inequality holds. ✅

What the figure shows. The plot below puts the index $n$ on the horizontal axis and value on a (logarithmic) vertical axis. The yellow dots are the actual Fibonacci numbers $f_n$; the red dashed curve is the upper wall $2^{n-1}$ and the green dashed curve is the lower wall $(3/2{)}^{n-2}$. The point of the picture: the yellow dots never poke above the red curve nor drop below the green one — the two induction bounds literally trap the sequence in a band for every $n$, which is the geometric content of the proof.

Reachability meaning: $n$ is a non-negative combination of $3$'s and $5$'s. The step subtracts either $3$ or $5$. Choose the safe jump = 3 (subtract $3$). It is valid once $n-3\ge 8$, i.e. $n\ge 11$. So $8,9,10$ must be base cases. Bases: $8=3+5$ ✅; $9=3+3+3$ ✅; $10=5+5$ ✅. 3 base cases, matching the jump length $3$. Strong step: for $n\ge 11$, assume reachable for all values in $[8,n)$. Then $8\le n-3<n$, so $n-3$ is reachable; add a $3$ to reach $n$. ✅ Why 3 and not 5? A jump of $5$ would demand base cases $8,9,10,11,12$ (five of them); the smaller valid jump minimises the base zone.

What the figure shows. Each amount $8,9,\dots ,16$ is drawn as a labelled disc on a number line. The yellow discs $8,9,10$ are the base zone — proved by hand. The blue discs $11$ and up are reached by the step. The green arrows draw the actual jump "$n\to n-3$", so you can trace, for any blue disc, the green arrow landing it back onto an already-established disc. Visually it makes the "no gap" guarantee obvious: every arrow lands on a disc that is either yellow (a base) or already reached.

Domino argument. Lay dominoes $n_0,n_0+1,\dots$. The step "$P(k)\text{ for all }k<n\Rightarrow P(n)$" says: domino $n$ falls once every earlier domino has fallen. The $b$ base cases are the first $b$ dominoes pushed by hand. For any later $n$, the step reaches back at most $b$; those targets are either hand-pushed (in the base zone) or already fallen (proved earlier). No domino ever waits on an un-fallen one — no gap. Well-Ordering link: suppose some $n$ failed. Then the set of failures is non-empty, so by Well-Ordering it has a least element $m$. But every $k<m$ is not a failure (else $m$ wouldn't be least), so the strong hypothesis holds at $m$, forcing $P(m)$ true — contradiction. So the failure set is empty. This is exactly strong induction, viewed backwards.