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

A Kick in the Discovery

, ,

Incredibly Serious, Inductive Sequences

Published by

Valt

on

In my last blog, we discussed how to use the awesome tool of induction to prove a countably infinite number of statements P(n). So, if you are unfamiliar with induction, I recommend you check it out (or another resource)!

This blog post is about using induction in a different situation. Instead of having a formula we want to prove true for all natural numbers, we define a sequence of numbers through induction.

Intuitively Inductive

A classic and very well-known example of such a sequence is the Fibonacci sequence. When you first learn of the Fibonacci sequence you probably heard something like, Start with the numbers 0 and 1. Add them to get 1. Now we have 0, 1, 1. Take the last two numbers and add them (1+1=2). Now we have 0, 1, 1, 2. Do the same thing, add the last two numbers (1+2=3) to get 0, 1, 1, 2, 3. Continue this process and you get the sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, . . .

The “continue this process” is code for: continue inductively. Another way we could have described the construction of the Fibonacci sequence is the following:

Let us define the sequence of real numbers F_n . Define F_1 = 0 and F_2 = 1 . Then define inductively F_{n} = F_{n-1}+F_{n-2} . Thus, F_3 = F_2 + F_1 = 1 + 0 = 1 . Then, F_4 = F_3 + F_2 = 1 + 1 = 2 . And so on…

This is an inductive definition because we defined how to start F_1=0,\;F_2=1 , and we defined how to find every other element based on the previous term(s) of the sequence, F_{n} = F_{n-1}+F_{n-2} .

Laborious Limits

One reason why you might use induction to define a sequence is so that you can find the sequence’s limit. The Fibonacci sequence grows larger and larger, so its limit is infinity. Not that interesting. However, there are some great sequences that do converge to something finite. Let’s take the example:

Let a_n denote the sequence defined inductively as follows: Set a_1 = \sqrt{2} and a_{n+1} = \sqrt{2+a_n} .

It’s always a great idea to look at some elements to get an idea of what’s happening. The first few are:

a_n \;:\; \sqrt{2} ,\;\sqrt{2+\sqrt{2}},\; \sqrt{2+\sqrt{2+\sqrt{2}}},\cdots

Which are approximately,

a_n \;:\; 1.414 ,\; 1.848,\; 1.962,\;1.990,\;1.998,\cdots

If we compute even more elements, we notice that the sequence always increases and seems to level off at 2. Maybe this is the limit?

Let’s try to prove a_n \rightarrow 2 . How do we do such a thing? We need to use what is known as The Monotone Convergence Theorem. We won’t prove it here, but here’s the idea;

The Monotone Convergence Theorem (increasing case):

If you have a sequence s_n that has only elements that increase or stay the same ie s_{n+1}\geq s_n , then (i) when s_n is unbounded above the limit diverges to infinity s_n \rightarrow \infty, or (ii) when s_n is bounded above the limit exists and is finite: s_n \rightarrow L for some finite L\in \mathbb{R}.1

The Monotone Convergence Theorem (decreasing case):

If you have a sequence s_n that has only elements that decrease or stay the same ie s_{n+1}\leq s_n , then (i) when s_n is unbounded from below the limit diverges to infinity s_n \rightarrow -\infty, or (ii) when s_n is bounded below the limit exists and is finite: s_n \rightarrow L for some finite L\in \mathbb{R}.

The first case makes sense, if each term gets larger and larger without bound, then of course it goes to infinity! It’s like what we had with F_n , namely F_n \rightarrow \infty.

The second situation is like what we have with a_n. As we will show, a_n is bounded above by 2 and is always increasing. This means a_n \leq 2 for all n and a_{n+1}\geq a_n. Combining these two pieces of information we conclude a_n must converge to something. We can think of the sequence as getting closer and closer and closer to its limit L. One analogy can come from everyday life.

Well, kind of…

Imagine you are walking towards a wall. It’s 16 feet in front of you. First, you walk 8 feet towards the wall. Then, you pause, take a breath, and then travel 4 feet closer to the wall. Again, pause. Now move 2 feet closer to the wall. Pause again. Then move 1 foot closer to the wall. Then move half a foot closer to the wall. Then a quarter foot closer to the wall. Etc. So far, you traveled 8 feet, then 4 feet, then 2 feet, then 1 foot, then half a foot etc. Notice that you are always moving forward, and so you don’t hit the wall you are always only traveling half the distance needed to reach the wall.

Thus, you never reach the wall, so you are bounded by the wall, and you will always have traveled less than 16 feet. But you are approaching 16 feet of travel. This is the exact same situation as some bounded monotone sequences! The elements of the sequence get closer and closer to their wall but never reach it. (Actually, sometimes they will reach the wall. But in those cases, it’s easier to see that the limit is the wall they get to).

A more mathy analogy can be seen by thinking back to when you learned about asymptotes. Your function can always be increasing, but since it’s bounded by the asymptote, all it can do is get closer and closer to its asymptote.

With the Monotone Convergence Theorem as a tool, our task is this: Show that a_n is monotone increasing and is bounded above. Then, by the monotone convergence theorem a_n converges to something finite. After we’re done with that, we have tricks that we can employ to actually find the value of the limit.

Being Bounded

Let’s begin by showing that a_{n} is bounded by 2 for all n .

We do this by induction on n… how surprising!

We already did our base case, a_{1} = \sqrt{2} \leq 2. Now, let’s assume that a_{n}\leq 2 for some n. We need to show a_{n+1}\leq 2. Indeed, since a_{n+1} = \sqrt{2+a_n} \leq \sqrt{2+2} = \sqrt{4} = 2 . Where we used that a_{n}\leq 2 to complete our induction. Ok, so we now know that a_{n} is bounded above by 2.

Incessantly Increasing

Next, let’s show that a_n is an increasing sequence.

Guess how we do this? Yup, through induction on n again!

Our base case was done when we listed some elements earlier: a_2 = \sqrt{2+\sqrt{2}}\geq \sqrt{2} = a_1 .2 Now we assume for some n that a_{n}\geq a_{n-1} to show a_{n+1}\geq a_{n} . Indeed, since a_{n+1}= \sqrt{2+a_{n}}\geq \sqrt{2+a_{n-1}} = a_{n} . Where we used a_{n}\geq a_{n-1} to complete our induction.

Landing on the Limit

Great, we now know that a_{n}‘s limit exits. How do we find it?

Let me ask you this: if a_{n}\rightarrow L does it make sense that a_{n-1}\rightarrow L? Or that a_{n+1}\rightarrow L too? Sure! We’re using the same sequence but now we’re indexing by n\pm 1 and not n. In other words, if a_{n} \rightarrow L then a_{n+1} \rightarrow L. And by some limit arithmetic, we know (2+a_{n}) \rightarrow (2 + L) as well. Similarly, \sqrt{2+a_{n}} \rightarrow \sqrt{2+L} too.

Thus, since a_{n+1} = \sqrt{2+a_n} we deduce, \lim{a_{n+1}} = \lim{\sqrt{2+a_n}} or, L = \sqrt{2+L} . This is only true because we know a_{n}\rightarrow L must exist and is finite by the monotone convergence theorem. All we need to do is solve for L.

L = \sqrt{2+L} \implies L ^2 = 2 + L \implies L = -1,\;2.

We have shown that L is positive ie, 0< L \leq 2 since a_1 >0 and a_n is monotone increasing. We conclude L = 2 .

Improper Inducting

There must always be caution when using induction see the end of my last blog post for a classic example. We have to make sure our limit exists before we can plug L into the inductive formula. If not, we can prove incorrect things. For example, the sequence defined by a_{1} = 4 and inductively define a_{n+1} = 2a_n^2 -1 . Some elements are: 4, 39, 1921, 7380481, … Which goes to infinity. However, if we just assumed a_{n}\rightarrow L , then we would conclude that

a_{n+1}\rightarrow L

\;\;\;\;a_{n}^2\rightarrow L^2 \;\;\;\;, and

a_{n}^2-1\rightarrow L^2 -1 .

Eventually concluding, L = 2L^2 -1 which implies L = -\frac{1}{2} or L = 1. Clearly, something is wrong since we know that a_{n}\rightarrow \infty! It stems from our assumption that L is finite. This is similar to the trouble you get when you do something like: \infty \times 2 = \infty \times 3 so that you cancel the \infty and get 2=3.

Moral of the story: You must somehow show that the limit a_{n}\rightarrow L exists and is finite. Once you do that, then you can plug L into the inductive definition of a_{n} .

If you want more practice check out my next post!

 

Finale

I hope this was helpful to at least one person! I have a plan to do a blog post on the monotone convergence theorem soon; however, I thought that introducing a need for it first would motivate someone to learn it. It’s a very useful theorem when discussing the convergence of sequences. It also plays a crucial role in the development of calculus. But that’s a story for another day!

Footnote:

  1. For those of you in the know about supremum and infimum, L = \sup{\{a_n\;:\;n\in\mathbb{N}\}} . For the decreasing case L = \inf{\{a_n\;:\;n\in \mathbb{N}\}}. If not don’t worry! We don’t need this level of detail in most cases. ↩︎
  2. If you don’t have a calculator to show \sqrt{2+\sqrt{2}}\geq \sqrt{2} . You can do it the following way:
    \sqrt{2}\geq 0 which implies 2 + \sqrt{2}\geq 2 which implies \sqrt{2+\sqrt{2}}\geq \sqrt{2} . ↩︎

2 responses to “Incredibly Serious, Inductive Sequences”

  1. A Strenuous Sequence – A Kick in the Discovery Avatar
    A Strenuous Sequence – A Kick in the Discovery

    […] challenging example! I commend your enthusiasm! For those not sure what I mean by this, check out this post before you read this […]

    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

    […] mentioned the monotone convergence theorem wayyy back in December of 2024 in the article, “Incredibly Serious, Inductive Sequences“. It’s now time to tackle this once and for all! Oh, and by no means do you have to […]

    Like

    Reply

Leave a reply to A Strenuous Sequence – A Kick in the Discovery Cancel reply