Illustrative examples of a phenomenon in the logic of mathematical induction

Consider the simple continued fraction $\langle a_0;a_1,a_2,\dots\rangle$, where all the $a_i$ are integers, and all positive except possibly $a_0$.

Define the sequences $p_i$, $q_i$ by

$p_{-1}=0$, $p_0=a_0$, and $p_k=a_kp_{k-1}+p_{k-2}$, and

$q_{-1}=0$, $q_0=1$, and $q_k=a_kq_{k-1}+q_{k-2}$.

We want to show that $\langle a_0;a_1,\dots,a_k\rangle=\frac{p_k}{q_k}$.

The standard way to prove the result by induction is to prove the stronger result that for any positive $x$, $$\langle a_0;a_1,\dots,a_{k-1},x\rangle=\frac{xp_{k-1}+p_{k-2}}{xq_{k-1}+q_{k-2}}.$$

As a small additional example, a recent question asked for a proof that the denominator of $\frac{1}{\sqrt{a_1}+\sqrt{a_2}+\cdots+\sqrt{a_n}}$ can be rationalized. An induction proof used the stronger induction hypothesis that $\frac{1}{\sqrt{a_1}+\sqrt{a_2}+\cdots+\sqrt{a_n}+t}$ can be rationalized, where $t$ is a free parameter.

For early induction arguments, however, I think inequalities are quite persuasive, since it is clear that for example knowing that $1+\frac{1}{2^2}+\frac{1}{n^2}\lt 2$ cannot by itself imply that $1+\frac{1}{2^2}+\frac{1}{n^2}+\frac{1}{(n+1)^2}\lt 2$

Example:

You can prove

$$ \frac{1}{2}\cdot\frac{3}{4}\cdot\ldots\cdot\frac{2n-1}{2n} < \sqrt{\frac{1}{3n}} $$

by strengthening to

$$ \frac{1}{2}\cdot\frac{3}{4}\cdot\ldots\cdot\frac{2n-1}{2n} < \sqrt{\frac{1}{3n+1}} $$

and using plain induction; this is the simplest example I know (you can make the inequality even shorter using the double factorial notation). In fact some time ago there was a post here about it, but I couldn't find it.

I hope this helps ;-)

Edit:

I've just seen even simpler example in this question, that is,

Prove that $0 \leq a_n < 1$ for all $n \in \mathbb{N}$ where $a_0 = 0$ and $ a_n = a_{n-1}^2 + \frac{1}{4} $ for $n > 0$.

which can be easily solved by proving $0 \leq a_n < \frac{1}{2}$ (in the original post @DanielFischer was first to give this hint).