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

Question

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.

2. 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$.

3. 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...

Answer 1

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

Answer 2

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.

Answer 3

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.

---

2. 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$.