# Convergence of the sequence $a_{{n+1}} = (1/3)(1+a_n+(a_{n-1})^2)$

Prove that $a_n$ converges: $a_1 = 0$ , $a_2 = 1/2$, $a_{{n+1}} = (1/3)(1+a_n+(a_{n-1})^2)$

My game plan is to prove that this sequence is monotonic rising and then bounded to prove convergence, but I can't even prove that its monotonic rising. (My question is relating to first proving that the sequence is monotonic so please don't give me the answer for the rest of the proof I want to still try it myself)

I'm trying to prove this by induction. I've found the first few $n$'s : $(n_1 = 0,n_2 = 1/2,n_3= 1/2,n_4= 7/12)$ so it looks like this is indeed rising. I've decided to assume that for $n=k$, $a_{{k+1}}>a_{{k}}$ and to show that it's rising for all $k$'s and therefore all $n$'s. Not sure what to do now. I've searched online and on youtube for examples on proving convergence for recursive sequences but only found very trivial examples of induction (a method I admittedly don't completely understand)

again, don't post how to prove the convergence I want to try to figure this out still.

Thanks, nofe

-
Some tips: 1) Understanding induction well is more important than knowing this sequence (not series) converges. Read your textbook, google some references or ask your teachers. 2) There are many ways to show something converges, there is no cookbook way to go about it every time. I would compute a few more terms to see if it really is monotone and also to see what it looks like its heading to. 3) If the sequence does converge and $a_n\to A$, then $a_{n-1} \to A$ and $a_{n+1} \to A$ as well. Take limits of both sides of the recursion you have to find something about A. –  Ragib Zaman Feb 3 '12 at 16:13
thanks for the tips, I am trying to do that. I'm simultaneously reading this source: science.kennesaw.edu/~plaval/math4381/seqcauchy.pdf and trying to figure it out not just for this specific problem but in general. –  nofe Feb 3 '12 at 16:22
@RagibZaman I have to respectfully disagree with you on this: 1) understanding induction in the broad is more important, but induction isn't actually much help for this particular sequence, and knowing how to prove things about inequalities is an essential skill. 2) While there are plenty of ways to show something converges, nofe is on basically the right path here (not with induction per se, but with showing that it's monotone increasing), and I think it's worth continuing to plug through this problem; and 3) that shows the result, but it doesn't show convergence. –  Steven Stadnicki Feb 3 '12 at 16:35
everyone keeps talking about inequalities. I'm not able to reduce anything to one variable. I'm always stuck with 2 variables in the end. I tried looking at the difference of two consecutive terms, $a_{{n+1}} - a_{{n}}$ but I end up with something like: $(1/2)(1+a_{{n-1}}^2)$ which doesn't prove that the difference is a positive value... –  nofe Feb 3 '12 at 16:44
@StevenStadnicki, then we have agreed :) My comment in 1) was indeed intended for the broad, though also for this particular problem. I was thinking of solutions similar to Andre, David and rob's below. Also, for 3), I understand it doesn't show convergence but it tells you what you want to show it converges to, which helps when you want to show the sequence is bounded. Since the limit should be $1$, we can try to prove it is bounded by $1$ by induction. This is what rob suggests in his answer, I was just explaining how one would see that $1$ is the bound. –  Ragib Zaman Feb 4 '12 at 1:12

Hint: Write down the recurrence you were given, and the recurrence for $a_{n+2}$, and look.

We were told that for all $n$,

(i) $a_{n+1}=\frac{1}{3}(1+a_n+a_{n-1}^2)$.

From this it follows immediately that

(ii) $a_{n+2}=\frac{1}{3}(1+a_{n+1}+a_n^2)$.

Suppose that we already know that $a_{k+1} >a_k$ for all $k \le n$. (Actually, we only need it for $k=n$ and $k=n-1$.) We want to show that $a_{n+2}>a_{n+1}$.

Compare the two expressions term by term, forgetting about the $\frac{1}{3}$, because it is common, so makes no difference in determining who is bigger.

First terms are $1$, equal. Second term is $a_{n+1}$ in (ii) and $a_n$ in (i), and we already know that $a_{n+1}>a_n$. Third term is $a_n^2$ in (ii) and $a_{n-1}^2$ in (i). We already know that $a_n>a_{n-1}$. All our numbers are obviously non-negative, so $a_n^2>a_{n-1}^2$.

Conclusion: $a_{n+2}>a_{n+1}$.

We have given a pretty full outline of a formal induction proof. But at the informal level, it is instant, first terms equal, second terms we went up, third terms we went up. So it's up. And up. Forever.

Somewhat more formally, we know $a_1$ and $a_2$. Compute $a_3$. Observe that $a_2>a_1$ and $a_3>a_2$. this gives the base of the induction.

By what we did above, because $a_2>a_1$ and $a_3>a_2$, we have $a_4>a_3$. But now because $a_3>a_2$ and $a_4>a_3$, we have $a_5>a_4$. But now because $a_4>a_3$ and $a_5>a_4$, we have $a_6>a_5$. And so on. Forever.

Remark: One can write down a fully persuasive argument that ostensibly doesn't use induction. However, induction is in principle unavoidable. Roughly speaking, whenever one sees $\dots$ in anything but a finite sequence, induction is n principle needed. And to prove anything general about a sequence defined by a recurrence, induction is in principle needed.

-
do I ignore the given $a_1$ and $a_2$ ? are they completely trivial ? –  nofe Feb 3 '12 at 16:54
just did that. I compared $a_{{n+2}}$ with $a_{{n+1}}$ by doing a quotient and checking if the quotient is greater than zero. I got this: $(1+a_{{n+1}}+a_n^2)/(1+a_n+a_{{2-1}}^2)$...this doesn't tell me anything since there are too many variables –  nofe Feb 3 '12 at 17:01
@nofe: Because it is easier to type in a post, I will add something there. –  André Nicolas Feb 3 '12 at 17:08
this is very counter-intuitive. I'm assuming something, and then proving the larger premise based on that assumption? I know that's the basis for induction but its still very hard for me to grasp the concept. Anyone have any ideas or sources for a stronger understanding of induction? (keep in mind this is my first year taking a more rigorous math course and I'm not majoring in math) @Andre I would ask you this in a private message but I haven't figured out how to do that on this site. –  nofe Feb 3 '12 at 17:47
@nofe: We don't ignore $a_1$ and $a_2$. In fact, we also calculate $a_3$. That gives a start to the induction, because by observation $a_2>a_1$ and $a_3>a_2$. –  André Nicolas Feb 3 '12 at 17:48

Hint:

1. Prove by induction that $0\le a_n<1$ for all $n\ge1$.
2. Using $a_n-a_{n-1}=\frac13(a_{n-1}-a_{n-2}+a_{n-2}^2-a_{n-3}^2)$, prove by induction that $a_{n+1}\ge a_n$ for all $n\ge1$.

What do you know about bounded increasing sequences in $\mathbb{R}$?

-

You can show that the sequence in monotonically increasing by using a somewhat stronger form of the induction principle. Here, you need to show:

$\ \ \ \ 1)\ a_1\le a_2$

and

$\ \ \ \ 2)\$If $a_{m-1}\le a_{m }$ for all $2\lt m\le n$, then $a_{n }\le a_{n+1}$.

Note that in 2), you assume that the inequality is true for all terms of the sequence, up to the $(n-1)^{\rm st}$-term. Then, you must show that the inequality must be true for the $n^{\rm th}$ term. Once you show this can be done, and once you show 1) is true, it will follow that the inequality is true for all $n$.

So:

Condition 1) is satisfied: $a_1=0<{1\over2}=a_2$.

Now, fix a value of $n\gt 2$, and assume that $$a_{m-1}\le a_{m},\quad \text{ whenever }2\lt m\le n .$$ We need to show that $a_n\le a_{n+1}$.

Towards this end, we have: $$a_n={1\over3}(1+a_{n-1}+(a_{n-2})^2 );$$ and since we assumed $a_{n-1} \le a_n$ and $a_{n-2} \le a_{n-1}$, we have, noting that all the $a_j$ are nonnegative (which may require a separate proof), that

\eqalign{ a_n&={1\over3}(1+a_{n-1}+(a_{n-2})^2 )\cr &\le{1\over3}(1+a_{n }+(a_{n-1})^2 )\cr &=a_{n+1}, } as desired.

We have shown that 1) and 2) are satisfied; thus the sequence is monotone increasing.

-

The easiest way to prove an inequality like this is to simplify it as much as possible, collect all the terms to one side and see if something falls out (sometimes with a condition on your $a_n$.) In this case, to show that $a_{n+1}\gt a_n$, multiply both sides by three, express in terms of $a_n$ and start collecting terms: $a_{n+1} \gt a_n$; $3a_{n+1} \gt 3a_n$; $1+a_n+a_n^2 \gt 3a_n$; $1-2a_n+a_n^2 \gt 0$. Now, can you see why the last result is always zero or positive (and under what circumstances it's zero)? Hint: what's a good condition on an expression that assures you it's always greater than or equal to zero?

-
i don't understand how you got to $1-2a_n + a_n^2$...what happened to all the $a_{{n-1}}$ and $a_{{n-2}}$ ? –  nofe Feb 3 '12 at 16:52
You don't need $a_{n-1}$ or $a_{n-2}$ (or in fact, induction) at all - the steps there are (1) write the condition that $a_{n+1} \gt a_n$; (2) Multiply both sides by 3, which doesn't change the inequality at all; (3) rewrite the left hand side in terms of $a_n$ using the recurrence equation that you have; (4) subtract $3a_n$ from both sides. In other words, you know that $a_{n+1}$ is greater than $a_n$ if and only if $1-2a_n+a_n^2$ is greater than zero. –  Steven Stadnicki Feb 3 '12 at 18:32