Stronger Induction

There are instances in which we would like to approach a problem by Induction, but we are not explicitly given the Induction hypothesis. In such instances, we need to guess the Induction hypothesis before we can proceed. Consider the following example:

What is the sum $S_n = 1 \times 1! + 2 \times 2! + 3 \times 3! + \ldots + n \times n!$?

Trying small cases, we see: $S_1 = 1, S_2 = 5, S_3 = 23, S_4 = 119, S_5 = 719$, which strongly suggests that $S_n=(n+1)! -1$. Now, we can treat this problem as a standard summation question and proceed via induction.

In other instances, the given statement doesn't seem to yield to Induction. Consider the following example:

Show that $\frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} +\ldots + \frac{ 1}{n^2} \leq 2$.

This may be recognizable to some readers who know the infinite sum of the reciprocal of squares is $\frac{ \pi^2} { 6} \approx 1.645$. If so, showing that it is bounded by 2 should give us some leeway. Let's consider what happens when we want to prove this by induction. The base case $n=1$ is obvious and true. However, when we try and work on the induction step, knowing that

$\frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} + \ldots + \frac{ 1}{k^2} \leq 2$

doesn't show

$\frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} +\ldots + \frac{ 1}{k^2} + \frac{1}{(k+1)^2} \leq 2 .$

We have added an additional term to the summation. If we had equality initially, then the LHS would be greater than 2, and hence induction will not work.

In Stronger Induction, we modify the statement and strengthen it (aka prove something which tells us much more). This gives us more information to work with in the Induction step. We are sacrificing the simplicity of the base case, to make the Induction hypothesis much easier to deal with. As a example of this usage, Carsten Thomassen showed in 1993 that Every Planar Graph is 5-Choosable, using "The trick is to find an appropriate extension". It had previously stumped mathematicians like Paul Erdos, who couldn't push through their proofs.

Note: The term 'stronger induction' is not common usage. Some people simply refer to it as "Strengthen the Induction Hypothesis".

Worked Examples

1. Prove that $\frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} +\ldots + \frac{ 1}{n^2} \leq 2 - \frac{1}{n}$.

Solution: Base case: $n=1$
LHS $= \frac{1}{1^2} = 1$.
RHS $= 2 - \frac{1}{1} = 1$.
Since $1 \leq 1$, hence the base case is true.

Induction step: Suppose the statement is true for some $k$, so we know that $\frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} + \frac{ 1}{k^2} \leq 2 - \frac{1}{k}$. If so,

$\frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} + \ldots + \frac{1}{k^2} + \frac{ 1}{(k+1)^2} \leq 2 - \frac{1}{k} + \frac{1}{(k+1)^2} \leq 2 - \frac{1}{k+1}$ Hence, we are done.

Note: The reason why $\frac{1}{n}$ works nicely here, is because $\frac{1}{n} - \frac{1}{n+1} = \frac{ 1}{n (n+1) } > \frac{1}{(n+1)^2}$.

2. $a, b$ are positive integers such that $\frac {2ab}{a^2+b^2} = \sin \theta$, show that $(a^2+b^2)^n \sin n\theta$ is an integer.

First, let's try this problem and see where we get stuck.
Base case: $n=1$.
This statement is clearly true, since $(a^2 +b^2) ^1 \sin \theta = 2ab$ is an integer.

Induction step: Suppose the statement is true for some $k$. Consider

$\begin{aligned} & (a^2+b^2)^{k+1} \sin (k+1)\theta \\ = & (a^2+b^2) ^k \sin k\theta \times (a^2 +b^2) \cos \theta + (a^2+b^2)^k \cos k\theta \times (a^2+b^2) \sin \theta \\ \end{aligned}$

Now, the induction hypothesis tells us that the $\sin$ terms will result in integers, but we know nothing about the $\cos$ terms. There is no guarantee that they will play nice and give us a sum that is an integer.

From Trigonometric Identities, we know that $\sin^2 \theta + \cos^2 \theta = 1$, so

$\begin{aligned} \cos^2 \theta & = 1 - \sin^2 \theta = (1-\sin \theta) ( 1 + \sin \theta) \\ & = \frac{ a^2 - 2ab + b^2}{a^2 + b^2} \times \frac{ a^2 + 2ab + b^2 } { a^2 + b^2 } \\ & = \left( \frac{ (a-b)(a+b) } { a^2+b^2} \right)^2 \\ \end{aligned}$

Thus $\cos \theta = \pm \frac{ (a-b)(a+b) } { a^2+b^2 }$, hence $(a^2+b^2)\cos \theta$ is also an integer. However, this does not tell us how to deal with $\cos k\theta$, which will always appear in the induction step.

As such, this suggests that we should prove the following stronger statement: $a, b$ are positive integers such that $\frac {2ab}{a^2+b^2} = \sin \theta$. Then $(a^2+b^2)^n \sin n\theta$ and $(a^2+b^2)^n \cos n\theta$ are both integers.

Solution: Base case: $n=1$.
This was already dealt with above. Both $(a^2+b^2)\sin \theta$ and $(a^2+b^2)\cos \theta$ are integers.

Induction hypothesis:

$\begin{aligned} & (a^2+b^2)^{k+1} \sin(k+1) \theta \\ = & (a^2 + b^2)^k \sin k\theta \times (a^2+b^2) \cos \theta + (a^2+b^2) ^k \cos k\theta \times (a^2+b^2) \sin \theta \\ & (a^2+b^2)^{k+1} \cos(k+1) \theta \\ = & (a^2 + b^2)^k \cos k\theta \times (a^2+b^2) \cos \theta - (a^2+b^2) ^k \sin k\theta \times (a^2+b^2) \sin \theta \end{aligned}$

Then, each of the terms on the right hand side are integers, so the left hand side are also integers.

3. For an integer $n$, prove that $\sqrt{2 \sqrt{3 \sqrt{ 4 \ldots { \sqrt{n} }}}} < 3$.

An attempt to blindly induct on $n$ leads to almost immediate failure, since we are increasing the LHS while keeping the RHS constant. We cannot copy Worked Example 1, as there is no clear adjustment to the RHS. Instead, we perform the following induction:

Fix integer $n\geq 2$. For all integer values of $2\leq k \leq n$, $\sqrt{ k \sqrt{(k+1) \sqrt{\ldots \sqrt{n} } } } < k+1 .$

The trick in this induction, is that we apply it going from $k$ to $k - 1$, as opposed to the typical induction step of $n$ to $n+1$.

The base case is obvious. When $k=n$, (remember that $n$ is fixed) we have $\sqrt{k } < k + 1$.

For the induction step, we have

$\sqrt{ (k-1) \sqrt{ k \sqrt{k+1} \ldots \sqrt{n}}} < \sqrt{(k-1)(k+1)} < k$

Hence, this complete the induction, and the result follows

Give yourself a pat on the back for making it all the way through this long post!

As a challenge, show that

$\sqrt{2 \sqrt{3 \sqrt{4 \ldots \sqrt{n}} } } < 2.8$

Hint: I've done all the heavy lifting already.

This concludes the series of posts on Induction techniques. You should read the Proof of AM-GM to learn how to apply Forward-Backward Induction.