# How to prove $0 < a_n < 1$ by induction

I know $n \in \mathbb{N}$ and...

$$a_n = \begin{cases} 0 & \text{ if } n = 0 \\ a_{n-1}^{2} + \frac{1}{4} & \text{ if } n > 0 \end{cases}$$

1. Base Case:

$$a_1 = a^2_0 + \frac{1}{4}$$

$$a_1 = 0^2 + \frac{1}{4} = \frac{1}{4}$$

Thus, we have that $0 < a_1 < 1$. So our base case is ok.

1. Inductive hypothesis:

Assume $n$ is arbitrary. Suppose $$0 < a_{n} < 1$$ $$0 < a_{n-1}^{2} + \frac{1}{4} < 1$$ is true, when $n > 1$.

1. Inductive step:

Let's prove $$0 < a_{n+1} < 1$$ $$0 < a_{n}^{2} + \frac{1}{4} < 1$$

is also true when $n > 1$.

My guess is that we have to prove that $a^2_{n}$ has to be less than $\frac{3}{4}$, which otherwise would make $a_{n+1}$ equal or greater than $1$.

So we have $(a_{n-1}^{2} + \frac{1}{4})^2 < \frac{3}{4}$... I don't know if this is correct, and how to continue...

• Prove the stronger $a_n \leqslant \frac{1}{2}$. – Daniel Fischer Nov 21 '14 at 15:42
• @DanielFischer ok, but what about if $a_n$ is $0.999999999999999999999999999999999999999999...$? – nbro Nov 21 '14 at 15:46
• What he's trying to say is: Pretend that the problem was "Prove that $0\leq a_n \leq \frac{1}{2}$". – Arthur Nov 21 '14 at 15:54
• No. When you are inductively proving $0 \leqslant a_n \leqslant \frac{1}{2}$, in the induction step, you have the stronger assumption $0 \leqslant a_n \leqslant \frac{1}{2}$, which suffices to conclude $0 \leqslant a_{n+1} \leqslant \frac{1}{2}$. – Daniel Fischer Nov 21 '14 at 15:54
• @nbro what Daniel is telling you to do is to prove something that implies what you want to prove. Instead of proving by induction that 0< $a_n$ < 1, you prove by induction that 0 < $a_n$ < $\frac{1}{2}$. And the latter implies that 0 < $a_n$ < 1 – mvggz Nov 21 '14 at 15:55

Ok I'll right it down so that it's clear to you :)

I want to prove the property P: " 0 < $a_n$ < 1 "

I look at the property A: $0 < a_n < \frac{1}{2}$

A => P, that is : If A is true then P is true

I'll prove A using induction (so technically I don't prove P by induction, but by implication).

$a_o = 0$ < $\frac{1}{2}$

If $0 < a_n < \frac{1}{2}$ , then :

$a_{n+1} = a_n^2 + \frac{1}{4}$ > $a_n^2$ > 0

And : $a_{n+1} = a_n^2 + \frac{1}{4}$ < $(\frac{1}{2})^2 + \frac{1}{4} = \frac{1}{2}$

Hence you get : 0 < $a_{n+1}$ < $\frac{1}{2}$ : the hypothesis holds for the rank n+1

So you have proven using induction that for every n positive integer you have :

0 < $a_n$ < $\frac{1}{2}$

But since : $\frac{1}{2}$ < 1 , you also have:

0 < $a_n$ < $\frac{1}{2}$ < 1 ie 0 < $a_n$ < 1

• But your proof does not make sense, because you assume at the beginning $0 < a_n < \frac{1}{2}$ to prove the same. Of course, if you assume $0 < a_n < \frac{1}{2}$, it also implies $0 < a_n < 1$, you don't have to prove anything. – nbro Nov 21 '14 at 16:58
• @nbro , I think you need to get things straight with induction. It's only a tool, and the fact a property implies an other is totally unrelated to the fact that you will use induction to prove one of these property. I just said at the beginning: "If A is true, then P is true also because A implies P". Indeed, if a< b and b < c, then by transitivity a < c. So 1/2 < 1 is always true, but if $a_n$ < 1/2, then likewise $a_n$ < 1. Now how I am going to prove that $a_n$ is indeed < 1/2 doesn't change anything I've said just before. I don't assume A at the beginning I just state something always true – mvggz Nov 21 '14 at 19:09
• I agree with all the things you said, but my point is that you start saying "if $0 < a_n < \frac{1}{2}$, then...", so you are supposing, right? But then you arrive at the end saying "$0 < a_n < \frac{1}{2} < 1$", but of course if what you supposed before was true, then your proof is not necessary, since we don't have to prove that $\frac{1}{2} < 1$, we know this!! You based your proof on this $0 < a_n < \frac{1}{2}$, ok, but why, how can you know? – nbro Nov 21 '14 at 19:21
• @nbro Of course I do, that's what the induction step is. The principle of induction is that you verify the property for the first terms , and then you suppose it is true for a arbitrary rank , usually called "n". Then, if you can prove that the hypothesis at the rank "n" implies that it is true for the rank n+1, you can conclude that it is true for every n integer. So I have to start the induction by saying "if the property 0 < $a_n$ < $\frac{1}{2}$ is true, then ..." and I finally conclude by something like " then.. 0< $a_{n+1}$ < $\frac{1}{2}$ . That's the process, you've got to grasp this – mvggz Nov 21 '14 at 20:04
• I've edited my answer, tell me if it makes more sense to you, but I can assure you that my reasoning is correct :) – mvggz Nov 21 '14 at 20:10

Starting with $a_0 = 0$, it is easier to show the stronger inequality, $0 < a_n < 1/2$ for $n \in \mathbb{Z}^+$. This conclusion immediately falls out from the recurrence relation.

Note: Base on the mvggz's answer, I will try to give also my complete with a lot of explanations answer. If something is wrong, please write in the comment section below ;)

Let $$a_n = \begin{cases} 0 & \text{ if } n = 0 \\ a_{n-1}^{2} + \frac{1}{4} & \text{ if } n > 0 \end{cases}$$

For all $n \in \mathbb{N}$ and $n \geq 1$

1. Basis:

Our base case is when $n = 1$, so let's verify the following statement $$0 < a_1 < 1$$ We know that $a_1 = a^2_0 + \frac{1}{4}$, so we have: $$0 < a^2_0 + \frac{1}{4} < 1$$ $a_0$ is 0, from the definition of $a_n$, so we have: $$0 < 0^2 + \frac{1}{4} < 1$$ $$0 < \frac{1}{4} < 1$$ which is clearly true, so our base case is proved.

1. Inductive step

Let's assume that $0 < a_n < \frac{1}{2}$ (this is a stronger case, because we are assuming that $a_n < \frac{1}{2}$ instead of $<1$)

We want to prove that $0 < a_{n+1} < 1$, but if we prove $0 < a_{n+1} < \frac{1}{2}$, then we prove also the first one, because $\frac{1}{2} < 1$.

We know that:

$$a_{n+1} = a^2_n + \frac{1}{4} > a^2_n > 0$$

We know $a^2_n > 0$, because $a_n$ is a positive number, and even though it wasn't, it would become positive, because raised to the power of $2$, would make it positive.

Since we assume that $a_n < \frac{1}{2}$, suppose we replace $a_n$ with $\frac{1}{2}$, and we say that (note the $<$ sign):

$$a_{n+1} = a^2_n + \frac{1}{4} < \left( \frac{1}{2} \right)^2 + \frac{1}{4}$$ $$a_{n+1} = a^2_n + \frac{1}{4} < \frac{1}{4}+ \frac{1}{4}$$ which simplified becomes: $$a_{n+1} = a^2_n + \frac{1}{4} < \frac{1}{2}$$

and we have just proved that $a_{n + 1} < \frac{1}{2}$, so it must also be less than $1$. Note that $a_{n+1} > 0$, because $a^2_n > 0$ and also $\frac{1}{4} > 0$.