10
$\begingroup$

Does equation $a_n=\sqrt{a_{n-1}+6}$ with $a_1=6$ have a closed form? I've found no linearization method. Any suggestion or hint will be highly appreciated.

  • 1
    It [seems](http://tinyurl.com/cw2p36y) to converge to $3$...2012-08-03
  • 1
    @draks: It does converge to $3$ (roughly like a geometric series of ratio $1/6$).2012-08-03
  • 1
    I would guess not, but it is going to be close to $3 + \frac{k_1}{6^n} + \frac{k_2}{6^{2n}} + \cdots$ for some $k_1,k_2,\ldots$ (in this case it seems $k_1 \approx 16.4558$ and $k_2 \approx 0.614$).2012-08-03
  • 0
    If the question is $a_n=\sqrt{a_{n-1}+2}$ instead I can solve this explicitally.2012-08-04
  • 0
    @doraemonpaul Then you should post this here (and probably mention that your solution is direct when $|a_1|\leqslant2$ but that it needs some adjustment otherwise).2012-09-08

4 Answers 4

7

There is no hope to find an explicit formula for $a_n$, but the asymptotics is clear.

One has $a_n=u(a_{n-1})$ where the function $u:x\mapsto\sqrt{x+6}$ has a unique fixed point $a=3$, hence $a_n-a=u(a_{n-1})-a=u(a_{n-1})-u(a)$ and one can suspect that $a_n\to a$. As a matter of fact, $u(a_n)-a=b_n\,(a_{n-1}-a)$ with $b_n=1/(u(a_{n-1})+a)$ hence $0\lt b_n\lt1/a$ hence $|a_n-a|\leqslant a^{-n}\,|a_0-a|$. Since $a\gt1$, this shows that $a_n\to a$.

More is true: since $b_n\to b=1/(2a)=1/6$, $a_n-a=b^{n+o(n)}$. In other words, since $a_n\gt a$ for every $n$, $$ \lim\limits_{n\to\infty}\frac{\log(a_n-a)}n=\log(b)=-\log(6), $$ and a little more work shows that $a_n-a=c\,b^n\,(1+o(1))$, where $c$ depends on $a_0$ and has no simple explicit form.

Edit: The algebraic trick used above to compute $b$ might hide the fact that $b=u'(a)$, where $a=u(a)$ is the fixed point of $u$.

  • 0
    @J.M. About your first Edit: I seem to encounter the construction *the asymptotics* + *is* regularly. Could you indicate an authoritative source which forbids this usage?2012-08-03
  • 0
    I'll have to get back to you on that, but if memory serves: "asymptotics" the subject matter being studied is singular, but "asymptotics" as in the behavior of the function is plural. A bit like "statistics" in that regard...2012-08-03
  • 0
    @J.M. Until then, let me stick to my idiom (and to `\lim\limits`, by the way), if you don't mind.2012-08-03
  • 0
    Well, on the matter of `\lim\limits`, since you have the thing enclosed in `$$`, whether `\limits` is there or not, the display is the same, so it'd seem `\limits` is moot (unless there is some hidden benefit of this idiom of yours). I'd have left the thing if it were enclosed in `$`...2012-08-03
  • 0
    You essentially prove that the iteration $x_{n + 1} = g(x_n)$ converges linearly to the fixed point $\zeta$ if $g'(\zeta) \ne 0$, $\lvert g'(\zeta) \rvert < 1$, and you start "close enough" to $\zeta$. Standard numerical analysis fare...2013-03-17
  • 0
    @vonbrand Replace "linearly" by "geometrically".2013-03-17
  • 0
    @Did, the numerical analysis people call it "linear convergence" when $x_{n + 2} - x_{n + 1} \approx \alpha (x_{n + 1} - x_n)$, "quadratic convergence" when $x_{n + 2} - x_{n + 1} \approx \alpha (x_{n + 1} - x_n)^2$, and so on.2013-03-17
  • 1
    @vonbrand Thanks for the explanation on [this terminology](http://en.wikipedia.org/wiki/Rate_of_convergence#Convergence_speed_for_iterative_methods).2013-03-17
1

Rewrite it as $$ a_n^2=a_{n-1}+6\\ a_{n}-a_{n-1}=a_n-a_n^2+6 $$ and approximate it as $$ a_n'-a_n+a_n^2-6=0, $$ which is solved by

$$a_n = \frac{3 e^{5 n}+2 e^{5 c_1}}{e^{5 n}-e^{5 c_1}},$$ with $c_1= \frac15 \left(5-3 \log(2)+\log(3)\right)\;\;$ such that $a_1=6$. Here's a plot...

  • 2
    I've checked your hidden solution with Mathematica. It didn't satisfy the given recursion.2012-08-03
  • 0
    i think that $a_{n-1}=\sqrt{7}$ and $a_{n-2}=1$2012-08-03
  • 0
    @ChristianBlatter no, it's an approximation...2012-08-03
  • 0
    *it's an approximation*... In which sense?2012-08-03
  • 0
    @did to the values of $a_n=\sqrt{a_{n-1}+6}$. I derived it using $a_{n}-a_{n-1}\approx a_n'$. The approximation is always a little less (or equal) than $a_n=\sqrt{a_{n-1}+6}$...but I'm not sure if this is the knid of answer, you expected from me.2012-08-03
  • 1
    Not *an approximation of what?* (this is clear) but *an approximation in which sense?* As you know, approximating discrete iterations by solutions of differential equations is a tricky business. In the case at hand, the limit $a_\infty=3$ is correct but not much more, for example $a_n-a_\infty$ is not of the order of $\mathrm e^{-5n}$.2012-08-03
  • 0
    @did $a_1=6$ is also correct. but in total you say, my answer is not useful? If so, I have no problem to delete it and take with me, that *approximating discrete iterations by solutions of differential equations is a tricky business*...2012-08-03
  • 0
    @did what makes this example tricky?2012-08-10
  • 0
    @draks Chaotic dynamics.2012-09-08
1

I think I found closed-form solution for this equation.

We need to find solution for this one ($a_0$ as a first element): $$ a_n = \sqrt{a_{n-1}+6}, \quad a_0=6. $$ We convert equation to this: $$ a_{n-1} = a_n^2 - 6, \quad a_0=6. $$ I always can change direction of element index and rewrite last equation in the next form (we call that equation "eq1"): $$ F_{n+1} = F_n^2 - 6, \quad F_0=6. $$

If we find solution (as function $F(n)$) for that equation we can use it to express the closed-form solution for your problem. If $F_n = F(n)$ then $a_n = F(-n)$. How can we found $F(n)$?

Solution for equation $b_{n+1} = b_n^2, \ \ b_0=\beta$ is $b_n = \beta^{2^n}$. We will seek the solution of the eq1 in this form: $$ F_n = F(n) = f(X^{2^n}) $$ where $f(x)$ is some unknown function and $X$ is some number.

For $f$ we know that $$ f(x^2) = f^2(x) - 6, $$ because we must satisfy the eq1 $$ F_{n+1} = f(X^{2^{n+1}}) = f((X^{2^n})^2) = f(X^{2^n})^2 - 6 = F_n^2 - 6. $$

We use this property and we find $f(x)$ as a fixed point (without proof of existence) $$ f(x) = \sqrt{6 + f(x^2)} $$ $$ f(x) = \lim\limits_{k -> \infty} \sqrt{6 + ... \sqrt{6 + f_0(x^{2^k})}}, $$ (number $6$ in this expression used $k$ times)
where $f_0(x)$ is some random function ($f_0(x) = x$ for example).

Function $f(x)$ are very interesting (it's not elementary or analytic). Here is some of its properties:

  1. $f(x^2) = f^2(x) - 6$.

  2. $f(0) = f(1) = 3$. $f(x^2) = f^2(x) - 6$ => $f(0) = f^2(0) - 6$ => $f(0) = \frac{1}{2}(1 + \sqrt{1 + 4 \cdot 6})$ => $f(0) = 3.$
    (another proof is to using the formula $\sqrt{c+\sqrt{c+...}} = \frac{1}{2}(1 + \sqrt{1 + 4 c})$.. you can find this on http://en.wikipedia.org/wiki/Nested_radical )

  3. $f(a) = 3$ for all $a : |a|<1$. (it's very easy to prove)

  4. $f(-x) = f(x)$.

  5. $f(x)$ is continuous in all real $x$. (without proof)

Here is a plot of this function:

plot

Now we can write the solution of eq1: $$ F_n = F(n) = f(X^{2^n}) $$ where $X$ is positive solution of equation $f(X) = 6$ (because we need satisfy initials $F_0 = f(X) = 6$). ($x \approx 5.46806882358680646837316643$)

Finally we can write the solution for you equation $$ a_n = F(-n). $$

($a_n -> 3$ because $F(-n) = f(X^{2^{-n}}) -> f(1) = 3$)

Same method we can use to find closed-form solution in more general cases!


If you have Mathematica you can use my code for check solution:


c = 6; (*constant adder in square root*)
b = 6; (*initial value (for F_0)*)
f0[x_] := x;

(*finding f(x)*)
N1 = 10; (*precision*)
g[x_] := Sqrt[c + x];
f[x_] := Nest[g, f0[x^2^N1], N1];

(*findinf X*)
N2 = 10; (*precision*)
res1 = FindRoot[f[x] == b, {x, c}, WorkingPrecision -> 1000];
X = x /. res1;

F[n_] := f[X^2^n]

(* you can use this function for comparing (this for eq1) *)
F2[n_] := F2[n - 1]^2 - c;
F2[0] := b;

For example:


F[0]
F[-1]
F[-2]

gets


6.00000000000000000000000000000000000000000000000000000000000000000000...
3.46410161513775458705489268301174473388561050762076125611161395890386...
3.07637800264170309696602586393672241931859085772505962544063421316756...

  • 0
    Indeed one *always can change direction of element index*, but, if one does, one obtains a completely different problem. Thus, this answer addresses a, possibly interesting but, quite unrelated question.2012-09-08
  • 1
    **did**: It's not completely different problem. It is a same one problem in some sence. I use is solution to express the solution for initial problem. See below my another answer! Also you always can check my solution. It's really work!2012-09-08
  • 0
    For example above some one write that he can find solution for $a_n=\sqrt{a_{n-1}+2}$. First we find solution for $F_n = F^2_{n-1}-2$. The solution is $F_n = x^{2^n} + x^{-2^n}$ (where $x$ we find from equation $x+\frac{1}{x}=a_0$). We also automatic get the solution for $a_n$. $a_n = F_{-n} = x^{2^{-n}} + x^{-2^{-n}}$. ($x=3+2\sqrt{2}$).2012-09-08
  • 0
    Also we can use the same general method. In this case we have function $f(x)$ that is equal to $g(x)=x+\frac{1}{x}$ for all $x \ge 0$ (http://img193.imageshack.us/img193/1260/nonlinear03.png). We get the same numeric result!2012-09-08
  • 0
    As I said, your answer brings zero information about the initial problem. As long as you play with words as when saying that *If $F_n=F(n)$ then $a_n=F(-n)$* (??) *where $f(x)$ is some unknown function* (indeed, $f$ is quite **unknown**...), I see no way in which one would *use i(t)s solution to express the solution for initial problem*. Sorry.2012-09-08
  • 0
    I think you don't understand my answer. $f(x)$ is not a unknown function. It is defined as a limit (you can get good aproximation for it if you take some big $k$). Also $F_n = a_{-n} => F_{-n}=a_{n}$. Just check my solutions if you don't belive. (It's really work. Check it for $a_n = \sqrt{a_{n-1}+2}$ for example).2012-09-08
  • 1
    You are not listening: I know that your $f$ is defined as a limit and this is precisely my point: what **explicit** information does that get you about $f$? Pretty much none, you are almost merely rephrasing the question. // *Also $F_n=a_{-n}\implies F_{-n}=a_n$* is an empty statement as well since at this point, you seem to have information about $F_n$ **for $n$ positive** (and not much, in fact) hence this tells you nothing about $a_n$ **for $n$ positive**. // Empty formalism can be a nicely intoxicating game, at times, but to confuse it with anything else is dangerous.2012-09-08
  • 0
    The $a_n=\sqrt{a_{n-1}+2}$ example is indeed a good one of my point since you could "solve" it as in your answer, that is, aligning formulas with no information about the solution, although one can describe the solution explicitely and get quite precise information about its asymptotics, which you would miss entirely.2012-09-08
  • 0
    How can you explain that fact that formula for $a_n=\sqrt{a_n{n-1}+2}$ have found in that way? You check my solutions or not? I know that I not justify some steps but you cannot deny that is that really work!2012-09-08
  • 0
    *for $a_n=\sqrt{a_{n-1}+2}$2012-09-08
  • 0
    There exists several methods to solve the case $a_n=\sqrt{a_{n-1}+2}$. One I like is that if $a_1=2\cos(\alpha/2)$ with $|\alpha|\leqslant2\pi$ then $a_n=2\cos(\alpha/2^n)$ for every $n\geqslant1$. As far as I can see, none of these methods applies to $a_n=\sqrt{a_{n-1}+6}$ and you show no formula of this kind for $a_n$. You wrote in a comment that *Also we can use the same general method*... OK, then just do it and *write down an explicit formula for $a_n$*. Otherwise, I fail to see what we are discussing.2012-09-08
  • 0
    $a_n = \lim\limits_{k->\infty} \sqrt{6 + ... \sqrt{6 + X^{2^{k-n}}} ...}$ (sqrt is taken $k$ times), where X ~ 5.468068823586806468373166430087481950365896815359497236419447227913502212357071231112355709045536589629246396900886973303044664...2012-09-08
  • 0
    Is this what you call explicit? Then you are using the word in a rather idiosyncratic way. Here is another "explicit closed form" which you might like: $a_n=g^{\circ n-1}(6)$ with $g(x)=\sqrt{x+6}$. It is almost as enlightening as yours. Well, anyway, this is enough for me.2012-09-09
-1

Zegalur: I followed your interesting post but cannot see the final closed form. My first question is why to "change direction of element index" when the changed recurrence Fn+1=F2n−6 is as hard as the original a2n=an−1+6? Has this backward recurrence, say, something to do with symmmetries in a further elaboration? Would you please clarify a bit?

Strange. I can't write any comments.. so I wrote a new answer.. Anyway...

I take a square of two parts of equation and move $6$ to the left side of equation.
$$ a_n = \sqrt{a_{n-1}+6} \ \ \ => \ \ \ a^2_n - 6 = a_{n-1} \ \ \ => \ \ \ a_{n-1}=a^2_{n} - 6. $$ If we have $a_0$ we now can find $a_{-1}, a_{-2}, ...$ ($a_{-1}=30$).

I've changed direction of index because it's more native to work with something like this: $$ F_n = Q(F_{n-1}). $$ (when the next element of sequence is expressed through previous one).

Now $F_{n} = a_{-n}$. If I will find solution in a closed-form $F_{n} = W(n)$ then I can use it to express solution for $a_n$. $$ a_n = F_{-n} = W(-n). $$

It is exactly what I did.


You also write that you can't find a final result. That is because solution is expressed by non elementary function $f(x)$ (see my answer). But you can't even find a Taylor series for it. But that function exist and it is continuous (see for example the plot of it).

Final result is $$ a_n = F_{-n} = f(X^{2^{-n}}) $$ where $f$ and $X$ are defined in my previous answer.

  • 0
    Almost forgot. $f(x)$ is defined as a limit. But we don't need to find it. If we take some big $k$ we can find a very good approximation for it (in my example if I take $k=10$ it is such good approximation that all significant digits for $F_{10}$ is good). We also need to find $X$ with good accuracy.2012-09-07
  • 0
    Zegalur: I followed your interesting post but cannot see the final closed form. My first question is why to "change direction of element index" when the changed recurrence $F_{n+1}=F_n^2-6$ is as hard as the original $a_n^2=a_{n-1}+6$? Has this backward recurrence, say, something to do with symmmetries in a further elaboration? Would you please clarify a bit?2012-09-07