Solving Recurrence Relation: a_n = \sqrt{2+a_{n-1}}, a_0 = \sqrt{3}

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

 

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

 

[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} }

 

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

 

[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 doesn't equal 2, then you can guess that a_n private is a constant and solve the quadratic equation.

 

[MathematicalPhysicist]

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

 

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

 

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

 

[daveyinaz]

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

 

[Zurtex]

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

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 b_n = ln(a_n) 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.

 

[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?

 

[MathematicalPhysicist]

well i see that this doesn't work, usually when this doesn't 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 haven't 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.