# Nonlinear recurrence relation

1. Jan 16, 2008

### foxjwill

1. The problem statement, all variables and given/known data
Solve the following for a_n in terms of x:
$$a_{n+1} = \sqrt{x + a_n}$$

2. Relevant equations

3. The attempt at a solution
Besides getting rid of the radical, I have no idea how to solve this.

2. Jan 17, 2008

### HallsofIvy

First, you can't do it if you don't have a given value for a0 to start the process! Even then, what reason do you have to think it has a "simple" solution (i.e. one that can be written in any simple formula)?

3. Jan 17, 2008

### foxjwill

Sorry. I meant for any given $$a_0$$.

I think Brahmagupta came up with something for it. I was reading about him in this book I got, and it mentioned it. However, the book was geared towards people who hadn't even taken calculus yet, so it didn't even show the solution let alone the process. It might be a series solution, for all I know. I also could be incorrectly remembering.

4. Jan 17, 2008

### dalle

dear foxjwill
supose the limit a_n does exist and is$$a$$. then because the square root is a contious function , the limit $$a$$ must be a solution of
$$a = \sqrt{x+a}$$
which you should be able to solve. Next you will have to show that a_n is
constant if a_0 =a
monoton increasing when -x<a_0 < a and a is an upper bound of a_n
monoton decreasIng when a_0>a and a is an lower bound of a_n

Last edited: Jan 17, 2008
5. Jan 18, 2008

### foxjwill

So,

$$a=\frac{1+ \sqrt{4x+1}}{2}.$$ ​

I threw out

$$a = \frac{1- \sqrt{4x+1}}{2},$$​

which is negative, because $$\forall x \in \mathbb{R}, \sqrt{x+a}\geq 0.$$

Is this correct?

EDIT:
I don't really understand why we have to show this. Well, actually, I don't think I really undertstand what we're trying to show. Could you possibly give a more detailed explanation?

Last edited: Jan 18, 2008
6. Jan 19, 2008

### dalle

dear foxjwill
your solution is correct( more on this at the end) . Why can't we stop there? we know that that if a_1=a then we will get a constant sequence. we do not know if it will converge to a if we start at any other number! we will have to prove it!

Let's consider an example:

$$a_{n+1} = 1 + x a_n$$
solving $$a = 1 + x a$$ we get $$a = \frac{1}{1-x}$$. Lets consider the the case where x=2 . a quick calculation will show that a=-1. now lets consider $$a_1=10$$. Then $$a_2=21$$ and so on. so althought a=-1 is a solution you will only reach it if you start with a_1=-1! Try a_1=-10
So it is not trivial that the sequence $$a_{n+1} = \sqrt{x+a_n}$$ will converge if you don't start with a_1=a!!

How can you prove that a sequence converges? well if a sequence is monoton increasing and bounded from above then it is convergent. (if a sequence is monoton decreasing and bounded from below it is also convergent). if you don't know that theorem then try to prove it! it is an important one!

How do we know that our sequence will be monoton? Well I will give you a visual prove! Without loss of generality let us asume that x=2 . we will study $$a_{n+1} = \sqrt{2+a_n}$$. What is the value if a?

Get a piece of paper with a plot of the functions
$$f(x)=\sqrt{2+x}$$
$$g(x) = x$$
$$h(x)=2$$
on it. Note that $$f(a)=f(2)=g(2)=2$$ so the intersection of f and g is the Point $$P=(2,2)$$.

let's see what happens when we start with $$a_1 = 1$$. Make a mark at the point $$P_1= (1,1)$$. draw a line through $$P_1$$ which is paralell to the y-axis.
This line will intersect the the graph of f in the point $$Q_1 = (1,\sqrt{3})$$. Draw a line through $$Q_1$$ which is paralell to the x-axis. This line will intersect the graph of g in the point $$P_2= (\sqrt{3},\sqrt{3}) = (a_2,a_2)$$. Repeat that instruction and find $$P_3,P_4,...$$. Those points will be on g and the will get closer to P from below. Why will we get closer to P? Because the graph of f is above the graph of g in (-2,2)! Why can't we get to the right of P? Because the graph of f is below the graph of h in (-2,2). Why is it impossible that we stop at a Point $$B=(b,b)$$ with $$b < 2$$? If start at $$a_1=b-\epsilon$$ then $$a_2=\sqrt{2+b-\epsilon} >b$$ for $$\epsilon$$ sufficently small.

What will happen when you start with $$a_1=10$$? your sequence will be decreasing and I will leave the details to you.

Was our assumption x=2 special? No the only thing that changes is that the graph of f will move to the right or to the left. ( Well as long as x>0 nothing changes. If x=0 then you will get 2 solutions for a and the case where x<0 is quite complicated because the series may not be defined for all choices of a_1 and I don't think you are expected to consider that case)
An algebraic prove of convergence will look quite similar to our visual prove but you may not get the same insight.

Last edited: Jan 19, 2008
7. Jan 19, 2008

### HallsofIvy

dalle, you seem to be assuming that the problem is to find the limit of the sequence. It was originally phrased as asking to find a closed form formula for an.

8. Jan 20, 2008

### foxjwill

Come to think of it, I had actually forgotten that I'd asked for that! >_< Does anyone know how to do that?

9. Aug 31, 2011

### Surajit93

Square term Polynomial help ??

a0^2+a1^2*x+a3^2*x^3+................, i.e. Sum(a(i)^2*x^i) {for i=1:Inf}

can this be given any functional form ??

like , suppose , the generating function g(x)=a0+a1*x+a2*x^2+a3*x^3+.........

look, the coefficients in "Sum(a(i)^2*x^i) {for i=1:Inf}" are square of the coefficients of "g(x)".

I want to know that can "Sum(a(i)^2*x^i) {for i=1:Inf}" be represented anyhow in terms of "g(x)" or "f(g(x))" ?????

10. Aug 31, 2011

### Surajit93

Re: Square term Polynomial help ??

a0^2+a1^2*x+a3^2*x^3+................, i.e. Sum(a(i)^2*x^i) {for i=1:Inf}

can this be given any functional form ??

like , suppose , the generating function g(x)=a0+a1*x+a2*x^2+a3*x^3+.........

look, the coefficients in "Sum(a(i)^2*x^i) {for i=1:Inf}" are square of the coefficients of "g(x)".

I want to know that can "Sum(a(i)^2*x^i) {for i=1:Inf}" be represented anyhow in terms of "g(x)" or "f(g(x))" ?????