2
$\begingroup$

I am trying to prove the following...

A sequence $a_0,a_1,a_2,...$ is defined recursively as follows:

$a_0 = 0;$

$\forall n \in \mathbb{N}, a_{n+1}=(a_n)^2+\frac{1}{4}$

Prove that $\forall n \ge 1, 0 < a_n < 1$.

Now, I have tried approaching the problem a few ways but it seems like in order to solve this I need to find a closed form expression for the recurrence relation (please advise if this approach is not correct). I have done a bit of work in the past with homogeneous linear recurrence relations and usually the characteristic polynomial simply falls out of the definition of the recurrence relation.

Can someone give me some hints on how to find a closed form expression for this recurrence relation?

I think that once I have a closed form I can prove the result fairly easily.

$\endgroup$
  • $\begingroup$ A closed form will be useless I guess. $\endgroup$ – lhf Dec 27 '16 at 16:23
7
$\begingroup$

Hint: Prove by induction a stronger claim: $0 < a_n < \frac12$. This is easier!

$\endgroup$
1
$\begingroup$

Prove by induction.

Part 1:

  • Base case: $a_{1}<\frac12$
  • Assumption: $a_{n}<\frac12$
  • Inductive step: $a_{n+1}=(a_{n})^2+\frac14<\left(\frac12\right)^2+\frac14=\frac12$

Part 2:

  • Base case: $a_{1}\geq\frac14$
  • Assumption: $a_{n}\geq\frac14$
  • Inductive step: $a_{n+1}=(a_{n})^2+\frac14\geq\left(\frac14\right)^2+\frac14>\frac14$

Hence $\forall{n\geq1}:a_{n}\in[\frac14,\frac12)\subset(0,1)$.

$\endgroup$
  • $\begingroup$ Why down-vote? What is wrong with my answer? $\endgroup$ – goodvibration Dec 27 '16 at 16:31
  • $\begingroup$ No need for the second part since clearly $a_{n+1} > 0$. No downvote from me, though. $\endgroup$ – lhf Dec 27 '16 at 16:31
1
$\begingroup$

$$ \forall n \ge 1, 0 < a_n $$
as $a_{n+1} = (a_n)^2 + \frac {1}{4} $ and $(a_n)^2 >= 0 , \forall n $ implying $(a_n)^2 + \frac {1}{4} > 0 $.

Now if $ \forall n \ge 1 , a_n < 1$ $$ \forall n \ge 0, (a_n)^2 + \frac {1}{4} < 1 $$ implying $$ \forall n \ge 0, (a_n)^2 < \frac {3}{4} $$ is true.

If we can prove the above statement , we will get the required result.

$$a_0 < 3/4$$ implies $$a_1 = \frac {1}{4} < 3/4$$.

Thus our proposition is true for $n=1$. Now assuming $a_{n-1} < 3/4$ we get $$a_n < (3/4)^2 + 1/4 = 13/16$$ and $$(a_n)^2 < (13/16)^2$$ which is approximately $0.66$ less than $3/4$.

Thus by principle of mathematical induction we get $$ \forall n \ge 0, (a_n)^2 < \frac {3}{4} $$ to be true which ultimately proves $$ \forall n \ge 1 , a_n < 1$$

$\endgroup$
1
$\begingroup$

Hint : the sequence is increasing and whenever terms are less than 1/2, next term will also be less than 1/2. Even if one term becomes 1/2 then next terms will stay at 1/2.

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