What Comes Next: 1, 2, 4, 8, 16, … hint it’s not 32

A Kick in the Discovery

, ,

A Strenuous Sequence

Published by

Valt

on

Thank you for coming to see a more challenging example! I commend your enthusiasm! For those not sure what I mean by this, check out this post before you read this one! One last thing, remember that:

Let’s get into it!

Practice makes Perfect

Here’s a trickier sequence than the one in the last post. Let’s define a_{n} in the following manner:

Let a_{1} = \frac{1}{8} and a_{n+1} = a_n^2 + \frac{1}{8} . Does a_{n} converge? If so, what is its limit?

I recommend you give this a go before we discuss it! Make a guess, does it converge? Is this one more challenging because it doesn’t converge???????

Step 0: Getting a Grip

I will not list elements in the sequence a_{n} only because I know you can do it! (At least with a calculators help!)

We will get a grip by studying the form of the inductive definition a_{n+1} = a_n^2 + \frac{1}{8} . First, off because I’m lazy and it’s quite an effort to type fractions, I will denote \frac{1}{8} by the Greek letter \xi (my favorite letter to write! I mean look at it, it’s a squiggle).1

Ok, let’s look at a_{2} and a_{1} .

a_{1} = \xi,

a_{2} = a_1^2 + \xi = \xi^2 + \xi > \xi = a_1 .

So it at least looks like we might have a monotone-increasing sequence. This is a bold claim since all we looked at was the first term! But, if you keep this going you’ll notice this sequence does indeed increase monotonically (a_{n+1} \geq a_n )

Next, does a_{n} seem to be bounded? Hmmmm it’s hard to see. You could argue, since you are always adding a positive quantity, \xi , to a_{n}^2 , we could think a_{n} might go to infinity. On the other hand, if you’ve studied infinite series, you know that adding positive quantities forever doesn’t mean the sum goes to infinity.2 So, what’s happening here with a_{n} ?

Keep pondering this. We’ll come back to it in step 2.

Ok game time.

Our game plan is the following: (i) Show that a_{n} is monotone increasing using induction (ii) Show that a_{n} is either bounded or unbounded using induction. From there we use the monotone convergence theorem (increasing case) to conclude a_{n} \rightarrow \infty or a_{n} \rightarrow L for some finite L. (iii) If a_{n} \rightarrow \infty then take a nap because we’re already done! Or, use some limit tricks if a_{n} \rightarrow L.

Step 1: Incremental Increase

We induct on n .

We already took care of our base case. But since we want a complete and localized induction proof I copied it here again.

For our base case, we must show a_{2} \geq a_1 . Indeed, since a_{1} = \xi, and

a_{2} = a_1^2 + \xi = \xi^2 + \xi \geq \xi = a_1 .

Now assume a_{n+1} \geq a_n . We aim to show, a_{n+2} \geq a_{n+1} . Actually, we will show the equivalent: a_{n+1} \leq a_{n+2} . Observe,

a_{n+1} = a_n^2 + \xi \leq a_{n+1}^2 + \xi = a_{n+2},\qquad\qquad\mathrm{since}\;\mathrm{we}\;\mathrm{assumed}\;\; a_{n}\leq a_{n+1}.

Great! By induction, we conclude a_{n+1} \geq a_n for all n .

Step 2: To Bound or Not To Bound? That is the question…

Ok, did you make up your mind yet? Or did you just wait to read the answer haha! Either way, a_{n} is bounded. The best way to see this is by guessing! For me, I asked whether I could show a_{n}\leq 1 , or maybe a_{n} \leq \frac{1}{2}, etc

I found that I couldn’t show a_{n}\leq 1 , because 1^2 = 1. However, I could show a_{n} \leq \frac{1}{2} since \left(\frac{1}{2}\right)^2 < \frac{1}{2}. As we will see, this is crucial.

Our base case is simply that, a_{1} = \xi = \frac{1}{8} \leq \frac{1}{2}. Now let’s assume a_{n} \leq \frac{1}{2} and show a_{n+1} \leq \frac{1}{2}. This is the case since,

a_{n+1} = a_n^2 + \xi \leq \left(\frac{1}{2}\right)^2 + \xi = \frac{1}{4} + \frac{1}{8} \leq \frac{1}{2}.

By induction, we conclude a_{n} \leq \frac{1}{2} for all n .

Step 3: Tricks of the Trade

We will do the exact same thing we did in the main blog post.

We have shown a_{n} is a bounded monotonically increasing sequence. Thus, by the monotone convergence theorem a_{n} \rightarrow L for finite L.

Thus, we have the chain of logic:

a_{n} \rightarrow L

a_n^2 \rightarrow L^2

a_n^2 + \frac{1}{8} \rightarrow L^2 + \frac{1}{8}

a_{n+1} \rightarrow L

Thus, \Bigg(a_{n+1} = a_n^2 + \frac{1}{8}\Bigg) \rightarrow \Bigg(L = L^2 + \frac{1}{8}\Bigg). This is a quadratic equation with solutions:

L = \frac{1+ \sqrt{1/2}}{2} and L = \frac{1- \sqrt{1/2}}{2} .

The last step is to decide which L is the limit. Got any ideas?

We already know that L \leq \frac{1}{2}, and we can see that L = \frac{1+ \sqrt{1/2}}{2} = \frac{1}{2} + (positive \; number)>\frac{1}{2}. Thus, L is the smaller solution. We conclude:

a_n \rightarrow L = \frac{1- \sqrt{1/2}}{2} .

\square

And we’re done!

Closing Remarks

You should be proud! This was no mean feat! I hope seeing another example was helpful. Please let me know if you have any questions, or if I made a mistake/could have done a better job explaining the work!

  1. Pro-tip: Pronounce \xi as ksi. ↩︎
  2. A famous case is the sum \sum_{n=1}^{\infty}\frac{1}{n^2} = \frac{\pi^2}{6}. See 3Blue1Brown’s AMAZING video if this astounds you! Actually, check it out even if it doesn’t! ↩︎

 

2 responses to “A Strenuous Sequence”

  1. Incredibly Serious, Inductive Sequences – A Kick in the Discovery Avatar
    Incredibly Serious, Inductive Sequences – A Kick in the Discovery

    […] If you want more practice check out my next post! […]

    Like

    Reply
  2. Let’s Get Real… Analysis (Part 5): the Monotone Convergence Theorem – A Kick in the Discovery Avatar
    Let’s Get Real… Analysis (Part 5): the Monotone Convergence Theorem – A Kick in the Discovery

    […] a new one! For those interested check out Incredibly Serious, Inductive Sequences and then A Strenuous Sequence mentioned at the […]

    Like

    Reply

Leave a reply to Let’s Get Real… Analysis (Part 5): the Monotone Convergence Theorem – A Kick in the Discovery Cancel reply