Suppose we have a problem we would like to approach by Induction, but are not given a hypothesis that works directly. What approach should we take? In this post, learn about the technique of Stronger Induction.

You may first choose to read about Induction and Strong Induction, if you haven't already done so.

How would you use Stronger Induction to solve the following problem?

Comment below to discuss your approach.Prove that for all positive integers \(n\),

\[\frac{1}{2} \times \frac{3}{4} \times \cdots \times \frac{2n-1} {2n} \leq \frac {1} {\sqrt{3n}} \]

## Comments

Sort by:

TopNewest\[\frac{1}{2} \times \frac{3}{4} \times \frac{5}{6} \times \ldots \times \frac{2n-1}{2n} \leq \frac{1}{\sqrt{3n}}\]

Consider: \(A_{n}=\frac{1}{2} \times \frac{3}{4} \times \frac{5}{6} \times \ldots \times \frac{2n-1}{2n}\)

Because we want to prove for all \(positive\) integer \(n\), we can say that

\[A_{n} \leq \frac{1}{\sqrt{3n+1}} \ldots (1)\]

For \(n = 1,\)

\[A_{1} = \frac{1}{2} = \frac{1}{\sqrt{3 \times 1 + 1}}\]

For \(n = 2,\)

\[A_{2} = \frac{1}{2} \times \frac{3}{4} = \frac{3}{8} < \frac{1}{\sqrt{3 \times 2 + 1}} = \frac{1}{\sqrt{7}}\]

\(\vdots\)

For \(n = k, (1)\) holds

\[A_{k} < \frac{1}{\sqrt{3k+1}}\]

Now, prove that for \(n = k+1, (1)\) also holds

\[A_{k+1} < \frac{1}{\sqrt{3(k+1)+1}} = \frac{1}{\sqrt{3k+4}} \ldots (2)\]

Since \(A_{k+1} = A_{k} \times \frac{2k+1}{2k+2},\) then

\[A_{k+1} < \frac{2k+1}{2k+2} \times \frac{1}{\sqrt{3k+1}} \ldots (3)\]

By squares RHS in \((3)\)

\[(\frac{2k+1}{2k+2} \times \frac{1}{\sqrt{3k+1}})^2 \]

\[= \frac{(2k+1)^2}{(2k+2)^2(3k+1)} = \frac{(2k+1)^2}{(2k+1)^2(3k+4)+k} < \frac{(2k+1)^2}{(2k+1)^2(3k+4)} = \frac{1}{3k+4}\]

Which proved RHS in \((2).\) Hence,

\[A_{n} \leq \frac{1}{\sqrt{3n+1}} \leq \frac{1}{\sqrt{3n}} \]

Edit:

I just realized in this post it is mention there are \(3\) types of induction. Then what is the induction I use here? It is confusing :/ – Fariz Azmi Pratama · 4 years, 1 month ago

Log in to reply

– Calvin Lin Staff · 4 years ago

Read the posts and you will know what type of induction this is called. Note that there are actually much more than these 3 types of induction.Log in to reply

\[A_{n} \leq \frac{1}{\sqrt{3n+1}} \leq \frac{1}{\sqrt{3n}}\]

So cool! – Nabila Nida Rafida · 4 years, 1 month ago

Log in to reply

To make our life simple, we can try \( f(n) = \sqrt{3n+a} \) where \(a \) is a positive number. We can then solve this as a usual inequality, and find that \( a > \frac{6}{7} \) works if we want \( n \geq 1 \). Of course, choosing \(a= 1 \) simplifies the algebra, while still making the base case true.

As you can see, the simplification of \( f(n) = \sqrt{3n+a} \) could also be modified. Can we use \( f(n) = \sqrt{ \pi n + a } \) instead? – Calvin Lin Staff · 4 years ago

Log in to reply

Wow, that took me a very long time to solve, but it was worth it! For that exact reason I won't post my solution here, as the temptation to read it without trying long enough for yourself might be too big.

Here's my (cryptic) hint: proving something harder might be easier! – Tim Vermeulen · 4 years, 1 month ago

Log in to reply

Log in to reply

It's quite surprising that trying to prove the 'easy' statement is a lot harder than proving the 'hard' one. – Tim Vermeulen · 4 years, 1 month ago

Log in to reply

Well one of the best ways to figure out the induction hypothesis is to try the sum or product to a certain extent and try to see a pattern. Sometimes one can even find the pattern through finite differences. – Tanishq Aggarwal · 4 years, 1 month ago

Log in to reply

– Tanishq Aggarwal · 4 years, 1 month ago

For example, trying out the sum of the first \(k\) odd integers seems to always give \(k^2\). This is simple to prove by induction.Log in to reply

In the example question that I gave, since \( \frac{1}{ \sqrt{3n} } \times \frac{ 2n+1}{2n+2} > \frac {1} { \sqrt{3n+3} } \), you would be unable to prove the induction step. What else can you do? – Calvin Lin Staff · 4 years, 1 month ago

Log in to reply

– Kishan K · 4 years, 1 month ago

Is it for natural no.?Log in to reply

– Tim Vermeulen · 4 years, 1 month ago

Yup.Log in to reply

Another hint would be to try to replace the RHS with a constant and try to prove the inequality. – Edwin Ma · 4 years, 1 month ago

Log in to reply

– Tim Vermeulen · 4 years, 1 month ago

That wouldn't make much sense, as the smallest constant that would work is \(\frac{1}{2}\), and that doesn't really help.Log in to reply