Stronger Induction

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 nn,

12×34××2n12n13n\frac{1}{2} \times \frac{3}{4} \times \cdots \times \frac{2n-1} {2n} \leq \frac {1} {\sqrt{3n}}

Note by Calvin Lin
6 years, 3 months ago

No vote yet
22 votes

  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](https://brilliant.org)example 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}

Comments

Sort by:

Top Newest

12×34×56××2n12n13n\frac{1}{2} \times \frac{3}{4} \times \frac{5}{6} \times \ldots \times \frac{2n-1}{2n} \leq \frac{1}{\sqrt{3n}}

Consider: An=12×34×56××2n12nA_{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 positivepositive integer nn, we can say that

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

For n=1,n = 1,

A1=12=13×1+1A_{1} = \frac{1}{2} = \frac{1}{\sqrt{3 \times 1 + 1}}

For n=2,n = 2,

A2=12×34=38<13×2+1=17A_{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)n = k, (1) holds

Ak<13k+1A_{k} < \frac{1}{\sqrt{3k+1}}

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

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

Since Ak+1=Ak×2k+12k+2,A_{k+1} = A_{k} \times \frac{2k+1}{2k+2}, then

Ak+1<2k+12k+2×13k+1(3)A_{k+1} < \frac{2k+1}{2k+2} \times \frac{1}{\sqrt{3k+1}} \ldots (3)

By squares RHS in (3)(3)

(2k+12k+2×13k+1)2(\frac{2k+1}{2k+2} \times \frac{1}{\sqrt{3k+1}})^2

=(2k+1)2(2k+2)2(3k+1)=(2k+1)2(2k+1)2(3k+4)+k<(2k+1)2(2k+1)2(3k+4)=13k+4= \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).(2). Hence,

An13n+113nA_{n} \leq \frac{1}{\sqrt{3n+1}} \leq \frac{1}{\sqrt{3n}}

Edit:

I just realized in this post it is mention there are 33 types of induction. Then what is the induction I use here? It is confusing :/

Fariz Azmi Pratama - 6 years, 2 months ago

Log in to reply

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.

Calvin Lin Staff - 6 years, 2 months ago

Log in to reply

How can come up with:

An13n+113nA_{n} \leq \frac{1}{\sqrt{3n+1}} \leq \frac{1}{\sqrt{3n}}

So cool!

Nabila Nida Rafida - 6 years, 2 months ago

Log in to reply

The basic idea is that we want a function f(n)3n f(n) \geq \sqrt{3n} such that 2n+12n+2f(n)f(n+1) \frac{2n+1}{2n+2} \leq \frac{ f(n) }{f(n+1)}

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

As you can see, the simplification of f(n)=3n+a f(n) = \sqrt{3n+a} could also be modified. Can we use f(n)=πn+a f(n) = \sqrt{ \pi n + a } instead?

Calvin Lin Staff - 6 years, 2 months ago

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 - 6 years, 2 months ago

Log in to reply

That wouldn't make much sense, as the smallest constant that would work is 12\frac{1}{2}, and that doesn't really help.

Tim Vermeulen - 6 years, 2 months 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 - 6 years, 3 months ago

Log in to reply

Indeed, and as I stated:

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.

Calvin Lin Staff - 6 years, 2 months ago

Log in to reply

Oh, I'm sorry, I wasn't aware of the difference between "Stronger Induction" and "Strong Induction", I thought they linked to te same article. That does make the problem a little easier.

It's quite surprising that trying to prove the 'easy' statement is a lot harder than proving the 'hard' one.

Tim Vermeulen - 6 years, 2 months 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 - 6 years, 3 months ago

Log in to reply

For example, trying out the sum of the first kk odd integers seems to always give k2k^2. This is simple to prove by induction.

Tanishq Aggarwal - 6 years, 3 months ago

Log in to reply

You are referring to the basic idea of induction. In this post, we are exploring scenarios where Induction doesn't immediately work, and it's uncertain if / how it could work.

In the example question that I gave, since 13n×2n+12n+2>13n+3 \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 - 6 years, 3 months ago

Log in to reply

@Calvin Lin Is it for natural no.?

Kishan k - 6 years, 3 months ago

Log in to reply

@Kishan K Yup.

Tim Vermeulen - 6 years, 3 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...