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 Sn=1×1!+2×2!+3×3!++n×n! S_n = 1 \times 1! + 2 \times 2! + 3 \times 3! + \ldots + n \times n!?

Trying small cases, we see: S1=1,S2=5,S3=23,S4=119,S5=719 S_1 = 1, S_2 = 5, S_3 = 23, S_4 = 119, S_5 = 719 , which strongly suggests that Sn=(n+1)!1 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 112+122+132++1n22 \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 π261.645 \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=1n=1 is obvious and true. However, when we try and work on the induction step, knowing that

112+122+132++1k22 \frac{1}{1^2} + \frac{1}{2^2} + \frac{1}{3^2} + \ldots + \frac{ 1}{k^2} \leq 2

doesn't show

112+122+132++1k2+1(k+1)22. \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 112+122+132++1n221n\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=1n=1
LHS =112=1 = \frac{1}{1^2} = 1 .
RHS =211=1 = 2 - \frac{1}{1} = 1 .
Since 11 1 \leq 1 , hence the base case is true.

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

112+122+132++1k2+1(k+1)221k+1(k+1)221k+1 \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 1n \frac{1}{n} works nicely here, is because 1n1n+1=1n(n+1)>1(n+1)2 \frac{1}{n} - \frac{1}{n+1} = \frac{ 1}{n (n+1) } > \frac{1}{(n+1)^2} .

2. a,ba, b are positive integers such that 2aba2+b2=sinθ \frac {2ab}{a^2+b^2} = \sin \theta, show that (a2+b2)nsinnθ (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=1n=1 .
This statement is clearly true, since (a2+b2)1sinθ=2ab (a^2 +b^2) ^1 \sin \theta = 2ab is an integer.

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

(a2+b2)k+1sin(k+1)θ=(a2+b2)ksinkθ×(a2+b2)cosθ+(a2+b2)kcoskθ×(a2+b2)sinθ \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 \sin terms will result in integers, but we know nothing about the cos \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 sin2θ+cos2θ=1 \sin^2 \theta + \cos^2 \theta = 1 , so

cos2θ=1sin2θ=(1sinθ)(1+sinθ)=a22ab+b2a2+b2×a2+2ab+b2a2+b2=((ab)(a+b)a2+b2)2 \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θ=±(ab)(a+b)a2+b2 \cos \theta = \pm \frac{ (a-b)(a+b) } { a^2+b^2 } , hence (a2+b2)cosθ (a^2+b^2)\cos \theta is also an integer. However, this does not tell us how to deal with coskθ \cos k\theta , which will always appear in the induction step.

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

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

Induction hypothesis:

(a2+b2)k+1sin(k+1)θ=(a2+b2)ksinkθ×(a2+b2)cosθ+(a2+b2)kcoskθ×(a2+b2)sinθ(a2+b2)k+1cos(k+1)θ=(a2+b2)kcoskθ×(a2+b2)cosθ(a2+b2)ksinkθ×(a2+b2)sinθ \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 nn, prove that 234n<3 \sqrt{2 \sqrt{3 \sqrt{ 4 \ldots { \sqrt{n} }}}} < 3 .

An attempt to blindly induct on nn 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 n2n\geq 2. For all integer values of 2kn2\leq k \leq n, k(k+1)n<k+1.\sqrt{ k \sqrt{(k+1) \sqrt{\ldots \sqrt{n} } } } < k+1 .

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

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

For the induction step, we have

(k1)kk+1n<(k1)(k+1)<k \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

234n<2.8 \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.

Note by Calvin Lin
7 years, 2 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link]( link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}


There are no comments in this discussion.


Problem Loading...

Note Loading...

Set Loading...