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

In summary, the conversation revolves around a recurrence relation and the possibility of finding a closed-form solution for it. The participants discuss techniques from differential equations and linear algebra, and the concept of a "private solution" or particular solution. There is disagreement about whether a closed-form solution is possible for the given recurrence relation. Some participants express doubt while others suggest using substitution and methods for finding a closed-form solution for linear homogeneous recurrence relations. The conversation ends with a question about the absence of experts in the discussion.
  • #1
daveyinaz
225
0
Hey, I came across this recurrence relation and was wondering if there was a closed-form solution for it.

[tex] a_n = \sqrt{2 + a_{n-1}}, a_0 = \sqrt{3}[/tex]

Assuming [tex]n \in \mathbb{N}[/tex], 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:
Mathematics news on Phys.org
  • #2
Well the solution you get it is obviously:

[tex] a_n = \sqrt{2 + \sqrt{2 + \sqrt{ 2 + \sqrt{\ldots + \sqrt{3}}}}}[/tex]

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:
  • #3
Something like this (probably misplaced the bracket though).

[tex] a_n = \sqrt{\underbrace{2 + \sqrt{2 + \sqrt{ 2 + \sqrt{\ldots + \sqrt{3}}}}}_{(n - 1) \times} }[/tex]
 
  • #4
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

[tex] F_n = F_{n-1} + F_{n-2}, F_0 = 1, F_1 = 1 [/tex]

For all [tex] n \in \mathbb{N} [/tex]

Yet the closed form solution is

[tex] f(n) = \frac{\phi^n - (1 - \phi)^n}{\sqrt{5}} [/tex]

where

[tex] \phi = \frac{1 + \sqrt{5}}{2} [/tex]

The f(n) equation is what I want to find out of the recurrence relation I initially posted.
 
Last edited:
  • #5
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.
 
  • #6
btw the techniques you said you know aren't ODE but from linear algebra.
 
  • #7
Using what quantum loop gravity said.

We get [tex] a_n^2 = a_{n-1} + 2 [/tex]

and finding the homogenous solution for

[tex]b_n = \frac{1}{2}b_{n-1}, b_0 = \ln a_0 = \ln \sqrt{3} [/tex]

So [tex] b_n = \left( \frac{1}{2} \right)^n \ln \sqrt{3} [/tex]

Now solving for [tex] a_n [/tex], we get [tex]a_n = e^{\left( \frac{1}{2} \right)^n \ln \sqrt{3}} [/tex] 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:
  • #8
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:
[tex]a_n=c_1a_{n-1}+...+c_ra_{n-r}[/tex]
you need to find the roots of the equation:
[tex]x^r-c_1x^r-1-...-c_r=0[/tex]
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:
[tex]\lambda_1,...,\lambda_r[/tex]
then the solution is:
[tex]a_n=b_1\lambda_1^n+...+b_r\lambda_r^n[/tex]
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
Well, now I know I can't take you seriously. Thanks for trying to help anyways.
 
  • #10
daveyinaz said:
Well, now I know I can't take you seriously. Thanks for trying to help anyways.

:confused: 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:

[tex]{a_n}^2 = 2 + a_{n-1}[/tex]

[tex]b_n = \ln a_n[/tex]

[tex]e^{\ln \left({a_n}^2\right)} = e^{\ln \left( 2 + a_{n-1} \right) }[/tex]

[tex]e^{2 \ln a_n} = e^{\ln \left( 2 + a_{n-1} \right) }[/tex]

The substitution is easy enough on the LHS, but I don't see how it's possible on the RHS.
 
Last edited:
  • #11
If you have the "supposedly" linear homogenous recurrence relation (the reason I say supposedly is because of the square)

[tex] a_n^2 = a_{n-1} [/tex]

then we have [tex] 2 \ln a_n = \ln a_{n-1} [/tex]

Now if [tex] b_n = \ln a_n [/tex] then we end up with [tex] 2 b_n = b_{n-1} [/tex]

Correct?

Now solve for [tex] b_n [/tex] 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 [tex] b_n [/tex] from [tex] a_0 = \sqrt{3} [/tex]

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:
  • #12
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.
 

1. What is a recurrence relation?

A recurrence relation is a mathematical relationship that defines the value of a sequence based on previous terms in the sequence. It is often used to model and solve problems in various fields, including computer science, physics, and economics.

2. How do I solve a recurrence relation?

To solve a recurrence relation, you need to find a closed-form solution for the sequence. This can be done through various methods such as substitution, iteration, or using generating functions. In the case of the given recurrence relation, we can use substitution and solve for the general term of the sequence.

3. What is the general term for the given recurrence relation?

The general term for the given recurrence relation is a_n = \sqrt{2+a_{n-1}}. This means that the value of a_n is equal to the square root of 2 plus the value of the previous term a_{n-1}.

4. How do I find the value of a specific term in the sequence?

To find the value of a specific term in the sequence, you can use the general term and plug in the value of n. For example, to find the value of a_5, you would substitute 5 for n in the general term a_n = \sqrt{2+a_{n-1}}.

5. What is the initial value for the given recurrence relation?

The initial value for the given recurrence relation is a_0 = \sqrt{3}. This means that the first term in the sequence is equal to the square root of 3. This value is important as it helps us find the value of the subsequent terms in the sequence.

Similar threads

  • General Math
Replies
12
Views
2K
Replies
3
Views
1K
  • General Math
Replies
1
Views
1K
  • General Math
Replies
11
Views
1K
Replies
4
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
18
Views
2K
Replies
1
Views
657
  • General Math
Replies
2
Views
1K
Replies
1
Views
2K
  • General Math
Replies
4
Views
2K
Back
Top