# Recurrence Relation

1. Oct 14, 2007

### daveyinaz

Hey, I came across this recurrence relation and was wondering if there was a closed-form solution for it.

$$a_n = \sqrt{2 + a_{n-1}}, a_0 = \sqrt{3}$$

Assuming $$n \in \mathbb{N}$$, of course.

I know that's it's possible to solve homogenous and inhomogenous recurrence relations using certain differential equation techniques, some of which I referenced in trying to figure this one out. I'm hoping that someone might have some insight into if this one even has a closed-form solution.

Last edited: Oct 14, 2007
2. Oct 14, 2007

### Zurtex

Well the solution you get it is obviously:

$$a_n = \sqrt{2 + \sqrt{2 + \sqrt{ 2 + \sqrt{\ldots + \sqrt{3}}}}}$$

The only thing I can see that you can nicely do with this is work out its limit as it approaches infinity (Been a long time since I used tex, otherwise I would have put a nice curly bracket with n-1 times written underneath).

Last edited: Oct 14, 2007
3. Oct 15, 2007

### CompuChip

Something like this (probably misplaced the bracket though).

$$a_n = \sqrt{\underbrace{2 + \sqrt{2 + \sqrt{ 2 + \sqrt{\ldots + \sqrt{3}}}}}_{(n - 1) \times} }$$

4. Oct 15, 2007

### daveyinaz

I think you guys mistook what I meant for a closed-form solution.

Closed form solution means a non-recursive function of n.

So the Fibonacci numbers have a recursive solution of

$$F_n = F_{n-1} + F_{n-2}, F_0 = 1, F_1 = 1$$

For all $$n \in \mathbb{N}$$

Yet the closed form solution is

$$f(n) = \frac{\phi^n - (1 - \phi)^n}{\sqrt{5}}$$

where

$$\phi = \frac{1 + \sqrt{5}}{2}$$

The f(n) equation is what I want to find out of the recurrence relation I initially posted.

Last edited: Oct 15, 2007
5. Oct 15, 2007

### MathematicalPhysicist

well yes, square and let a_n^2=2+a_n-1
now solve this homogeneuos:
a_n^2=a_n-1
2ln(a_n)=ln(a_n-1)
let b_n=ln(a_n) solve this recursive formula.
now for the private solution first find the homogeneous solution afterwards if it doesnt equal 2, then you can guess that a_n private is a constant and solve the quadratic equation.

6. Oct 15, 2007

### MathematicalPhysicist

btw the techniques you said you know aren't ODE but from linear algebra.

7. Oct 15, 2007

### daveyinaz

Using what quantum loop gravity said.

We get $$a_n^2 = a_{n-1} + 2$$

and finding the homogenous solution for

$$b_n = \frac{1}{2}b_{n-1}, b_0 = \ln a_0 = \ln \sqrt{3}$$

So $$b_n = \left( \frac{1}{2} \right)^n \ln \sqrt{3}$$

Now solving for $$a_n$$, we get $$a_n = e^{\left( \frac{1}{2} \right)^n \ln \sqrt{3}}$$ for our closed-form solution for the homogenous of this.

Ok. Now you said find a "private" solution, do you mean particular solution?

So this is what I was referring to when I said DE techniques. Seems like we'd be using the method of undetermined coefficients which I've only encountered in DE and not linear algebra....but what do i know.

Last edited: Oct 15, 2007
8. Oct 16, 2007

### MathematicalPhysicist

i don't know if youv'e taken a course in discrete maths or combinatorics.
but there we deal with linear recurrence relations which are homogeneous and non homogeneous (there are ofcourse other relations whcih are not covered in a basic course of undergraduate).

anyway, in this you guess a private solution, for example if you have the equation:
a_n=2+a_n-1
then the private solution you will guess a solution of the form a_n=Cn
cause there's already a solution in the form of a constant:
so the general solution would be: a_n=A+2n A a constant.

i said that in here you can guess that a_n is a constant for the particular solution.
I said that you need to know linear algebra cause it provides the theory behind the fact that the solution is a combination of the particualr and homogeneous solutions.
and ofcourse the theory behind finding a solution for linear recurrence equations, you need to know stuff about the characteristic polynomial, for example a solution for:
$$a_n=c_1a_{n-1}+...+c_ra_{n-r}$$
you need to find the roots of the equation:
$$x^r-c_1x^r-1-...-c_r=0$$
and if there are no multiple roots, i.e of algebraic multiplicity other than 1, then the solution is a linear combination of the roots, if the roots are:
$$\lambda_1,...,\lambda_r$$
then the solution is:
$$a_n=b_1\lambda_1^n+...+b_r\lambda_r^n$$
there's another solution if one root has multiplicity other than 1, but i believe that you neeed to take a textbook and read about it, you only need to know the basics of linear algebra for the theory.

9. Oct 16, 2007

### daveyinaz

Well, now I know I can't take you seriously. Thanks for trying to help anyways.

10. Oct 17, 2007

### Zurtex

Why on earth do you say that? loop quantum gravity isn't using the terminology I learnt, but it all sounds very familiar from the course I took in discrete maths.

Anyway going back to your earlier point, I understand what closed form is, I just don't think there is a closed form solution of this problem.

I don't think you applied the substitution bn = ln(an) correctly, but then I'm not sure how you do apply it correctly:

$${a_n}^2 = 2 + a_{n-1}$$

$$b_n = \ln a_n$$

$$e^{\ln \left({a_n}^2\right)} = e^{\ln \left( 2 + a_{n-1} \right) }$$

$$e^{2 \ln a_n} = e^{\ln \left( 2 + a_{n-1} \right) }$$

The substitution is easy enough on the LHS, but I don't see how it's possible on the RHS.

Last edited: Oct 17, 2007
11. Oct 17, 2007

### daveyinaz

If you have the "supposedly" linear homogenous recurrence relation (the reason I say supposedly is because of the square)

$$a_n^2 = a_{n-1}$$

then we have $$2 \ln a_n = \ln a_{n-1}$$

Now if $$b_n = \ln a_n$$ then we end up with $$2 b_n = b_{n-1}$$

Correct?

Now solve for $$b_n$$ and utilize the method for finding a closed-form solution of the linear homogenous recurrence relation. Which is exactly what I got in my post, we get the "base case" for $$b_n$$ from $$a_0 = \sqrt{3}$$

What I did was correct. But exactly what I was doing does nothing to help the situation as I don't even agree with it at all. Unless someone can prove to me anything that has to do with my initial problem, I stand by my statement of doubt.

Plus I'm wondering where all the big dogs are at? Like Hurkyl and Halls of Ivy? I see them posting like all kinds to everyone else, so then where is there expertise now?

Last edited: Oct 17, 2007
12. Oct 18, 2007

### MathematicalPhysicist

well i see that this doesnt work, usually when this doesnt work then you try with generating functions, although i don't see how to use it here, it could be helpful if you tell us from where you got this question?
anyway, one thing that i think but don't know if it would make sense.
but perhaps you can expand the thing in the root by taylor expansion, i mean i think the sequence is bounded by two so a_n-1/2<1 so you can use here this expansion, does it help? don't know, but you got rid of the root, which in this case is the big difficulty.

but don't take my word, iv'e just taken an introductory course in combinatorics and graph theory, i havent seen such questions, usually you can solve if you have as i said a_n=sqrt(a_n-1) or something else that can be interpreted by linear relation.