3
$\begingroup$

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

$\endgroup$
  • 6
    $\begingroup$ Prove the stronger $a_n \leqslant \frac{1}{2}$. $\endgroup$ – Daniel Fischer Nov 21 '14 at 15:42
  • $\begingroup$ @DanielFischer ok, but what about if $a_n$ is $0.999999999999999999999999999999999999999999...$? $\endgroup$ – nbro Nov 21 '14 at 15:46
  • 1
    $\begingroup$ What he's trying to say is: Pretend that the problem was "Prove that $0\leq a_n \leq \frac{1}{2}$". $\endgroup$ – Arthur Nov 21 '14 at 15:54
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Daniel Fischer Nov 21 '14 at 15:54
  • 1
    $\begingroup$ @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 $\endgroup$ – mvggz Nov 21 '14 at 15:55
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – nbro Nov 21 '14 at 16:58
  • $\begingroup$ @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 $\endgroup$ – mvggz Nov 21 '14 at 19:09
  • $\begingroup$ 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? $\endgroup$ – nbro Nov 21 '14 at 19:21
  • $\begingroup$ @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 $\endgroup$ – mvggz Nov 21 '14 at 20:04
  • $\begingroup$ I've edited my answer, tell me if it makes more sense to you, but I can assure you that my reasoning is correct :) $\endgroup$ – mvggz Nov 21 '14 at 20:10
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.