Closed form for the sequence defined by $a_0=1$ and $a_n+1 = a_n + a_n^-1$Upper bound of $a_n+1=a_n + frac1a_n$If $a_n+1=a_n+1/a_n$ and $a_0 = 1$, show $a_n/H_n^4to infty$ but $a_n/H_n^4to 0$Find the general formula of $a_n$$a_n+1=a_n+frac1a_n$ where $a_1=1$. Is $f(n)=a_n$ an elementary function?Concerning the sequence $ x_1=1 ,space x_n+1=x_n+dfrac1x_n $Find a general formula for $c_n+1=c_n+frac1c_n$ (Recursive)How to solve $a_n+1=a_n+frac1a_n$Is a closed-form expression of this non-linear expression attainable?Is the sequence $x_n$ convergent, where $x_n= a_n - sqrt2n$ and $a_n=a_n-1+frac1a_n-1$Closed form estimation for f(n) in the recursive formula $f(x+1)=f(x)+1 over f(x)$closed form for $d(4)=2$, $d(n+1)=d(n)+n-1$?$a_n$ converges to $a$, but why $frac1n+1(a_0+a_1+cdots+a_n)$ also?Closed form for a sequence defined recursivelyClosed Form for a SequenceFinding a closed-form formula for a sequence that is defined recursivelyHow to find a recursive formula for some sequencefinding a closed form for $a_0=0,a_n =a_n-1+n^2$Closed form solution for Quadratic Recurrence RelationsIs the sequence $a_n+1=a_n-frac1a_n$, $a_0=2$ bounded?Finding a closed form formula for a recursive sequence.

Why doesn't H₄O²⁺ exist?

Is it unprofessional to ask if a job posting on GlassDoor is real?

Do VLANs within a subnet need to have their own subnet for router on a stick?

What does "Puller Prush Person" mean?

Minkowski space

Service Entrance Breakers Rain Shield

Is this a crack on the carbon frame?

Risk of getting Chronic Wasting Disease (CWD) in the United States?

What are these boxed doors outside store fronts in New York?

What defenses are there against being summoned by the Gate spell?

A newer friend of my brother's gave him a load of baseball cards that are supposedly extremely valuable. Is this a scam?

How did the USSR manage to innovate in an environment characterized by government censorship and high bureaucracy?

How to test if a transaction is standard without spending real money?

Which models of the Boeing 737 are still in production?

What does it mean to describe someone as a butt steak?

What would happen to a modern skyscraper if it rains micro blackholes?

Dragon forelimb placement

How to say job offer in Mandarin/Cantonese?

Why are 150k or 200k jobs considered good when there are 300k+ births a month?

Why are electrically insulating heatsinks so rare? Is it just cost?

Why was the small council so happy for Tyrion to become the Master of Coin?

Accidentally leaked the solution to an assignment, what to do now? (I'm the prof)

"to be prejudice towards/against someone" vs "to be prejudiced against/towards someone"

LaTeX closing $ signs makes cursor jump



Closed form for the sequence defined by $a_0=1$ and $a_n+1 = a_n + a_n^-1$


Upper bound of $a_n+1=a_n + frac1a_n$If $a_n+1=a_n+1/a_n$ and $a_0 = 1$, show $a_n/H_n^4to infty$ but $a_n/H_n^4to 0$Find the general formula of $a_n$$a_n+1=a_n+frac1a_n$ where $a_1=1$. Is $f(n)=a_n$ an elementary function?Concerning the sequence $ x_1=1 ,space x_n+1=x_n+dfrac1x_n $Find a general formula for $c_n+1=c_n+frac1c_n$ (Recursive)How to solve $a_n+1=a_n+frac1a_n$Is a closed-form expression of this non-linear expression attainable?Is the sequence $x_n$ convergent, where $x_n= a_n - sqrt2n$ and $a_n=a_n-1+frac1a_n-1$Closed form estimation for f(n) in the recursive formula $f(x+1)=f(x)+1 over f(x)$closed form for $d(4)=2$, $d(n+1)=d(n)+n-1$?$a_n$ converges to $a$, but why $frac1n+1(a_0+a_1+cdots+a_n)$ also?Closed form for a sequence defined recursivelyClosed Form for a SequenceFinding a closed-form formula for a sequence that is defined recursivelyHow to find a recursive formula for some sequencefinding a closed form for $a_0=0,a_n =a_n-1+n^2$Closed form solution for Quadratic Recurrence RelationsIs the sequence $a_n+1=a_n-frac1a_n$, $a_0=2$ bounded?Finding a closed form formula for a recursive sequence.













28












$begingroup$


Today, we had a math class, where we had to show, that $a_100 > 14$ for



$$a_0 = 1;qquad a_n+1 = a_n + a_n^-1$$



Apart from this task, I asked myself: Is there a closed form for this sequence? Since I didn't find an answer by myself, can somebody tell me, whether such a closed form exists, and if yes what it is?










share|cite|improve this question











$endgroup$







  • 4




    $begingroup$
    A little Googling leads to mathworld.wolfram.com/MycielskiGraph.html (scroll to the bottom)
    $endgroup$
    – user940
    Mar 29 '11 at 19:18










  • $begingroup$
    Rereading this some years later... I am still bemused that you chose to accept the answer you did accept. Already the other answer posted by the same user is more in line with the site's purpose (even though it cannot pass for a rigorous piece of mathematics either, but at least it does try to explain how to get the result), not to mention answers by two other users... I must be missing something.
    $endgroup$
    – Did
    Sep 2 '16 at 7:20










  • $begingroup$
    @Did Look at the timestamps. The answer I accepted was the first good one I got.
    $endgroup$
    – FUZxxl
    Sep 2 '16 at 8:08










  • $begingroup$
    "Look at the timestamps. The answer I accepted was the first good one I got." Interesting argument: since three other answers were already posted when you accepted this one, I understand that you systematically accept the first "good" answer you receive, on principle? Then you should mention the fact explicitely, to avoid that poor souls lose their time answering your questions for nothing. You might also make apparent somewhere that mathematical justifications are entirely irrelevant for an answer to be declared "good" by you, since the whole site kind of assumes the opposite.
    $endgroup$
    – Did
    Sep 2 '16 at 8:16






  • 1




    $begingroup$
    @Did I don't “systematically accept the first good answer I get.” I did that time and that was five years ago. I was hoping for a closed form and Robert Israel's answer was the closed to that. I did however upvote the other answers.
    $endgroup$
    – FUZxxl
    Sep 2 '16 at 8:22















28












$begingroup$


Today, we had a math class, where we had to show, that $a_100 > 14$ for



$$a_0 = 1;qquad a_n+1 = a_n + a_n^-1$$



Apart from this task, I asked myself: Is there a closed form for this sequence? Since I didn't find an answer by myself, can somebody tell me, whether such a closed form exists, and if yes what it is?










share|cite|improve this question











$endgroup$







  • 4




    $begingroup$
    A little Googling leads to mathworld.wolfram.com/MycielskiGraph.html (scroll to the bottom)
    $endgroup$
    – user940
    Mar 29 '11 at 19:18










  • $begingroup$
    Rereading this some years later... I am still bemused that you chose to accept the answer you did accept. Already the other answer posted by the same user is more in line with the site's purpose (even though it cannot pass for a rigorous piece of mathematics either, but at least it does try to explain how to get the result), not to mention answers by two other users... I must be missing something.
    $endgroup$
    – Did
    Sep 2 '16 at 7:20










  • $begingroup$
    @Did Look at the timestamps. The answer I accepted was the first good one I got.
    $endgroup$
    – FUZxxl
    Sep 2 '16 at 8:08










  • $begingroup$
    "Look at the timestamps. The answer I accepted was the first good one I got." Interesting argument: since three other answers were already posted when you accepted this one, I understand that you systematically accept the first "good" answer you receive, on principle? Then you should mention the fact explicitely, to avoid that poor souls lose their time answering your questions for nothing. You might also make apparent somewhere that mathematical justifications are entirely irrelevant for an answer to be declared "good" by you, since the whole site kind of assumes the opposite.
    $endgroup$
    – Did
    Sep 2 '16 at 8:16






  • 1




    $begingroup$
    @Did I don't “systematically accept the first good answer I get.” I did that time and that was five years ago. I was hoping for a closed form and Robert Israel's answer was the closed to that. I did however upvote the other answers.
    $endgroup$
    – FUZxxl
    Sep 2 '16 at 8:22













28












28








28


11



$begingroup$


Today, we had a math class, where we had to show, that $a_100 > 14$ for



$$a_0 = 1;qquad a_n+1 = a_n + a_n^-1$$



Apart from this task, I asked myself: Is there a closed form for this sequence? Since I didn't find an answer by myself, can somebody tell me, whether such a closed form exists, and if yes what it is?










share|cite|improve this question











$endgroup$




Today, we had a math class, where we had to show, that $a_100 > 14$ for



$$a_0 = 1;qquad a_n+1 = a_n + a_n^-1$$



Apart from this task, I asked myself: Is there a closed form for this sequence? Since I didn't find an answer by myself, can somebody tell me, whether such a closed form exists, and if yes what it is?







sequences-and-series recurrence-relations closed-form






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Jul 23 '15 at 14:43









Did

249k23227466




249k23227466










asked Mar 29 '11 at 19:00









FUZxxlFUZxxl

3,80052143




3,80052143







  • 4




    $begingroup$
    A little Googling leads to mathworld.wolfram.com/MycielskiGraph.html (scroll to the bottom)
    $endgroup$
    – user940
    Mar 29 '11 at 19:18










  • $begingroup$
    Rereading this some years later... I am still bemused that you chose to accept the answer you did accept. Already the other answer posted by the same user is more in line with the site's purpose (even though it cannot pass for a rigorous piece of mathematics either, but at least it does try to explain how to get the result), not to mention answers by two other users... I must be missing something.
    $endgroup$
    – Did
    Sep 2 '16 at 7:20










  • $begingroup$
    @Did Look at the timestamps. The answer I accepted was the first good one I got.
    $endgroup$
    – FUZxxl
    Sep 2 '16 at 8:08










  • $begingroup$
    "Look at the timestamps. The answer I accepted was the first good one I got." Interesting argument: since three other answers were already posted when you accepted this one, I understand that you systematically accept the first "good" answer you receive, on principle? Then you should mention the fact explicitely, to avoid that poor souls lose their time answering your questions for nothing. You might also make apparent somewhere that mathematical justifications are entirely irrelevant for an answer to be declared "good" by you, since the whole site kind of assumes the opposite.
    $endgroup$
    – Did
    Sep 2 '16 at 8:16






  • 1




    $begingroup$
    @Did I don't “systematically accept the first good answer I get.” I did that time and that was five years ago. I was hoping for a closed form and Robert Israel's answer was the closed to that. I did however upvote the other answers.
    $endgroup$
    – FUZxxl
    Sep 2 '16 at 8:22












  • 4




    $begingroup$
    A little Googling leads to mathworld.wolfram.com/MycielskiGraph.html (scroll to the bottom)
    $endgroup$
    – user940
    Mar 29 '11 at 19:18










  • $begingroup$
    Rereading this some years later... I am still bemused that you chose to accept the answer you did accept. Already the other answer posted by the same user is more in line with the site's purpose (even though it cannot pass for a rigorous piece of mathematics either, but at least it does try to explain how to get the result), not to mention answers by two other users... I must be missing something.
    $endgroup$
    – Did
    Sep 2 '16 at 7:20










  • $begingroup$
    @Did Look at the timestamps. The answer I accepted was the first good one I got.
    $endgroup$
    – FUZxxl
    Sep 2 '16 at 8:08










  • $begingroup$
    "Look at the timestamps. The answer I accepted was the first good one I got." Interesting argument: since three other answers were already posted when you accepted this one, I understand that you systematically accept the first "good" answer you receive, on principle? Then you should mention the fact explicitely, to avoid that poor souls lose their time answering your questions for nothing. You might also make apparent somewhere that mathematical justifications are entirely irrelevant for an answer to be declared "good" by you, since the whole site kind of assumes the opposite.
    $endgroup$
    – Did
    Sep 2 '16 at 8:16






  • 1




    $begingroup$
    @Did I don't “systematically accept the first good answer I get.” I did that time and that was five years ago. I was hoping for a closed form and Robert Israel's answer was the closed to that. I did however upvote the other answers.
    $endgroup$
    – FUZxxl
    Sep 2 '16 at 8:22







4




4




$begingroup$
A little Googling leads to mathworld.wolfram.com/MycielskiGraph.html (scroll to the bottom)
$endgroup$
– user940
Mar 29 '11 at 19:18




$begingroup$
A little Googling leads to mathworld.wolfram.com/MycielskiGraph.html (scroll to the bottom)
$endgroup$
– user940
Mar 29 '11 at 19:18












$begingroup$
Rereading this some years later... I am still bemused that you chose to accept the answer you did accept. Already the other answer posted by the same user is more in line with the site's purpose (even though it cannot pass for a rigorous piece of mathematics either, but at least it does try to explain how to get the result), not to mention answers by two other users... I must be missing something.
$endgroup$
– Did
Sep 2 '16 at 7:20




$begingroup$
Rereading this some years later... I am still bemused that you chose to accept the answer you did accept. Already the other answer posted by the same user is more in line with the site's purpose (even though it cannot pass for a rigorous piece of mathematics either, but at least it does try to explain how to get the result), not to mention answers by two other users... I must be missing something.
$endgroup$
– Did
Sep 2 '16 at 7:20












$begingroup$
@Did Look at the timestamps. The answer I accepted was the first good one I got.
$endgroup$
– FUZxxl
Sep 2 '16 at 8:08




$begingroup$
@Did Look at the timestamps. The answer I accepted was the first good one I got.
$endgroup$
– FUZxxl
Sep 2 '16 at 8:08












$begingroup$
"Look at the timestamps. The answer I accepted was the first good one I got." Interesting argument: since three other answers were already posted when you accepted this one, I understand that you systematically accept the first "good" answer you receive, on principle? Then you should mention the fact explicitely, to avoid that poor souls lose their time answering your questions for nothing. You might also make apparent somewhere that mathematical justifications are entirely irrelevant for an answer to be declared "good" by you, since the whole site kind of assumes the opposite.
$endgroup$
– Did
Sep 2 '16 at 8:16




$begingroup$
"Look at the timestamps. The answer I accepted was the first good one I got." Interesting argument: since three other answers were already posted when you accepted this one, I understand that you systematically accept the first "good" answer you receive, on principle? Then you should mention the fact explicitely, to avoid that poor souls lose their time answering your questions for nothing. You might also make apparent somewhere that mathematical justifications are entirely irrelevant for an answer to be declared "good" by you, since the whole site kind of assumes the opposite.
$endgroup$
– Did
Sep 2 '16 at 8:16




1




1




$begingroup$
@Did I don't “systematically accept the first good answer I get.” I did that time and that was five years ago. I was hoping for a closed form and Robert Israel's answer was the closed to that. I did however upvote the other answers.
$endgroup$
– FUZxxl
Sep 2 '16 at 8:22




$begingroup$
@Did I don't “systematically accept the first good answer I get.” I did that time and that was five years ago. I was hoping for a closed form and Robert Israel's answer was the closed to that. I did however upvote the other answers.
$endgroup$
– FUZxxl
Sep 2 '16 at 8:22










6 Answers
6






active

oldest

votes


















14












$begingroup$

I agree, a closed form is very unlikely.
As for more precise asymptotics, I think $a_n = sqrt2n + 1/8,frac sqrt 2ln left( n right) sqrt n-frac 1
128,frac sqrt 2 left( ln left( n right) -2 right) ^2 + o(1)
n^3/2$






share|cite|improve this answer









$endgroup$








  • 4




    $begingroup$
    +1: The first two terms seem to match what I have :-) Can you please elaborate on how you got this? Seems like the $C$ in my answer can probably be given in "closed form" using your answer.
    $endgroup$
    – Aryabhata
    Mar 29 '11 at 20:03











  • $begingroup$
    It seems you are also this guy. Mysterious stranger. :)
    $endgroup$
    – Wok
    Mar 29 '11 at 21:23










  • $begingroup$
    @Robert: You can ask a moderator to merge your two accounts.
    $endgroup$
    – Bill Dubuque
    Mar 30 '11 at 19:41










  • $begingroup$
    @Bill: thanks for the headsup.
    $endgroup$
    – Willie Wong
    Mar 30 '11 at 20:31










  • $begingroup$
    @Robert: since I'm pretty sure you are who you are, I've taken the liberty to merge your old unregistered account into your new one.
    $endgroup$
    – Willie Wong
    Mar 30 '11 at 20:40


















21












$begingroup$

A closed form I doubt there is. But asymptotics are easy:
$$
a_n+1^2=a_n^2+2+1/a_n^2,
$$

hence, for every $nge1$,
$$
a_n^2=2n+1+sum_k=0^n-1frac1a_k^2.qquadqquadqquadqquad (*)
$$

This shows that $a_n^2ge2n+2$ for every $nge1$, for example $a_100gesqrt202>10sqrt2>14$. In particular, $a_nto+infty$. Plugging this into $(*)$ yields $a_n^2=2n+1+o(n)$ hence
$$
sqrt2nle a_nlesqrt2n+o(sqrtn).
$$

At this point, we know that $a_n^2ge2n+2$ for every $nge1$. Using $(*)$ again, one sees that, for every $nge1$,
$$
a_n^2le2n+2+sum_k=1^n-1frac12+2kle2n+2+frac12log(n).
$$

Which already shows that $$14.2<a_100<14.3$$
Plugging this upper bound of $a_n^2$ into $(*)$ would yield a refined lower bound of $a_n^2$. And one could then plug this refined lower bound into $(*)$ again to get a refined upper bound. And so on, back and forth between better and better upper bounds and better and better lower bounds. (No more asymptotics here.)






share|cite|improve this answer











$endgroup$












  • $begingroup$
    I just tried to understand this answer again, but I didn't understood, why $2n+1+sum_0le k<na_k^-2=2n+1+o(n)$
    $endgroup$
    – FUZxxl
    May 10 '11 at 20:15






  • 3




    $begingroup$
    The result is quite general: for every nonnegative sequence $(x_n)$ such that $x_n=o(1)$, $sum_kle nx_k=o(n)$. You could try to prove this by the usual epsilon-delta method.
    $endgroup$
    – Did
    May 11 '11 at 5:30










  • $begingroup$
    @FUZxxl: what's more, since $a_k>sqrt2k+1$, we have that $sum_0le k<na_k^-2<frac12gamma+log(2)+frac12log(n)+frac148n^2$
    $endgroup$
    – robjohn
    Aug 16 '11 at 12:07



















10












$begingroup$

To elaborate on how I got my answer: I started with @Did's $a(n) approx sqrt2n$ and looked for a next term. $a(n) = sqrt2n$ would make $ a(n+1) - (a(n) + a(n)^-1) = sqrt 2,n+2-sqrt 2sqrt n-1/2,frac sqrt 2sqrt n = - fracsqrt28 n^-3/2 + O(n^-5/2)$. With $a(n) = sqrt2n + c n^-1/2$ I don't get a change in the $n^-3/2$ term, so I tried $a(n) = sqrt2n + c ln(n) n^-1/2$ and got
$a(n+1) - (a(n) + a(n)^-1) = (-frac2sqrt8 + c) n^-3/2 + ldots$. So to get rid of the $n^-3/2$ term I want $c = frac2sqrt8$. Then look at the leading term for
$a(n) = sqrt2n + frac2sqrt8 ln(n) n^-1/2$ and continue in that vein...






share|cite|improve this answer











$endgroup$












  • $begingroup$
    Not sure this try-and-guess procedure constitutes a proof. The argument in my post proves that $a_n=sqrt2n+o(sqrtn)$.
    $endgroup$
    – Did
    Apr 1 '11 at 6:36










  • $begingroup$
    @Didier: Do you disagree with my answer?
    $endgroup$
    – Aryabhata
    Apr 1 '11 at 14:35






  • 3




    $begingroup$
    You should edit your other answer, rather than adding a new one.
    $endgroup$
    – Aryabhata
    Apr 1 '11 at 14:36


















6












$begingroup$

From my answer here: Given $a_1=1, a_n+1=a_n+frac1a_n$, find $lim limits_ntoinftyfraca_nn$



Reposting here, as it is kind of lost in that thread and this thread is more suitable for it.



Note: I have no clue if a closed form exists, but here is an asymptotic estimate...



I think we can show that $$displaystyle a_n^2 sim 2n + dfraclog n2 - C$$ for some constant $displaystyle C gt 0$



By $displaystyle x_n sim y_n$ I mean $displaystyle lim_n to infty (x_n - y_n) = 0$



Consider $b_n = a_n^2 - 2n$



Then we have that $displaystyle b_n+1 = b_n + dfrac1b_n + 2n$



Notice that $b_0 gt 0$ and thus $displaystyle b_n gt 0$.



(Note that the other thread linked above starts with $a_1 = 1$ and not $a_0 = 1$.)



We can easily show that $b_n lt 2 + log n$, as



$b_n+1 - b_n = dfrac1b_n + 2n lt dfrac12n$



Adding up gives us the easy upper bound. Note, even though we can give tighter bounds, this is sufficient for our purposes.



Now we have that, for sufficiently large $displaystyle m,n$



$displaystyle b_m+1 - b_n = sum_k=n^m dfrac1b_k + 2k$



we have that



$displaystyle sum_k=n^m dfrac12k gt b_m+1 - b_n gt sum_k=n^m dfrac12k(1- dfracb_k2k)$



(Here we used $displaystyle dfrac11+x gt 1-x, 1 gt x gt 0$)



Now Since $b_k lt 2 + log k$, we have that



$displaystyle sum_k=n^m dfrac12k gt b_m+1 - b_n gt sum_k=n^m dfrac12k - sum_k=n^m dfrac2 + log k 4k^2$



Using the fact that $displaystyle H_m - H_n = log(dfracm+1n) + O(dfrac1n) + O(dfrac1n - dfrac1m)$, where $displaystyle H_n = sum_k=1^n dfrac1k$ is the $displaystyle n^th$ harmonic number.



We see that,



if $c_n = b_n - dfraclog n2$, then



$displaystyle O(dfrac1n -dfrac1m) + O(dfrac1n) gt c_m+1 - c_n gt O(dfrac1n -dfrac1m) + O(dfrac1n) -sum_k=n^m dfrac2 + log k 4k^2$



Now $displaystyle sum_k=1^infty dfrac2 + log kk^2$ is convergent and so by the Cauchy convergence criteria, we have that $displaystyle c_n$ is convergent.



Thus the sequence $displaystyle a_n^2 - 2n - dfraclog n2$ converges and hence, for some $displaystyle C$ we have that



$$displaystyle a_n^2 sim 2n + dfraclog n2 - C$$



or in other words



$$displaystyle a_n sim sqrt2n + dfraclog n2 - C$$



A quick (possibly incorrect) computer simulation seems to show a very slow convergence to $displaystyle C = 1.47812676429749dots$



Note: Didier suggested an alternate proof in the comments below, which might simpler.






share|cite|improve this answer











$endgroup$












  • $begingroup$
    That's still only an asymptotic.
    $endgroup$
    – FUZxxl
    Mar 29 '11 at 19:33






  • 1




    $begingroup$
    @Fuz: Yes, I doubt if there is a known closed form for it. But being able to peg down the difference from $2n + log n/2$ to be a constant should be reasonably useful, I would say.
    $endgroup$
    – Aryabhata
    Mar 29 '11 at 19:42











  • $begingroup$
    @Moron This is to answer to the question you asked in a comment on Robert's post. First, do we agree that you ask me to check the mathematical accuracy of your answer? And that I only do that and state publicly the result of the checking because you asked me to? If I misunderstood you, please say so and I will delete my comment right away. So... here we go. To summarize, the general line of your proof is correct but some details annoy me, most often because you make some unnecessary détours where a more direct path exists. .../...
    $endgroup$
    – Did
    Apr 2 '11 at 10:04










  • $begingroup$
    .../... For example: (1) $b_n>0$ for every $nge0$ and not only for $nge3$. (2) The easy argument I can think of to bound $b_n$ is based on the inequality $b_n+2nge1$ for every $nge0$, it leads to $b_nle n+1$ and not to $b_n<2n$. Comment on (2): as a consequence, when I read that you will use $b_n<2n$ and that there is an easy argument to prove it, I am puzzled and worried that I missed something or that my argument leading to $b_nle n+1$ is wrong, so, ultimately, I am distracted. And this is bad. :-) .../...
    $endgroup$
    – Did
    Apr 2 '11 at 10:05










  • $begingroup$
    .../... (3) The easy argument I can think of to bound $b_n$ by a $log$ is based on he inequality $b_n+2nge2n$ for every $nge1$ and leads to an upper bound of leading term $frac12log(n)$ and not $log(n)$. So the comment on (2) applies here as well, mutatis mutandis. (3') You should expand this step. (4) The bound $b_k<log(k)$ is not useful the first time you invoke it (but it is useful the second time). (5) I would postpone the introduction of $log(n)$ to as late a point as possible. If you define $c_n$ by $c_n=b_n-frac12H_n$, $(c_n)$ is nonincreasing and bounded below by .../...
    $endgroup$
    – Did
    Apr 2 '11 at 10:06


















4












$begingroup$

Let us consider the functional formulation. Given $y(0)=1$, $y' = frac1y$ yields $ y(x) = sqrt2x+1$.




I am not saying $a(n)=y(n)$. Yet there is a link between the two approaches (finite difference).






share|cite|improve this answer











$endgroup$








  • 1




    $begingroup$
    What are you saying? That $a_n=y(n)$? Clearly not, since $a_n$ is always rational and $y(n)$ is typically irrational. There's no reason why replacing a difference by a derivative should work.
    $endgroup$
    – joriki
    Mar 29 '11 at 19:28






  • 2




    $begingroup$
    @joriki: Actually, it could be useful. If I recollect correctly, Donald J Newman recommends this as a rough method to guess the asymptotic behaviour of certain sequences, in one of his books.
    $endgroup$
    – Aryabhata
    Mar 29 '11 at 19:39











  • $begingroup$
    @joriki Indeed one can compare the solution $y$ of the ODE $y'=varphi(y)$ with the sequence $(a_n)$ defined by $a_n+1=a_n+varphi(a_n)$. For $varphi(y)=-2y$ the result is interesting.
    $endgroup$
    – Did
    Apr 4 '11 at 17:51










  • $begingroup$
    @Moron See comment above.
    $endgroup$
    – Did
    Apr 4 '11 at 17:52










  • $begingroup$
    @Didier: Thanks for the example :-)
    $endgroup$
    – Aryabhata
    Apr 4 '11 at 17:58


















0












$begingroup$

Let $b_n=a_n^-1$, so that $b_n+1=(b_n+b_n^-1)^-1$ is the $n$th iterate of $$f(x)=(x+x^-1)^-1=x-x^3+x^5-x^7+cdots$$
The correct asymptotics have been given elsewhere, but this answer is to point out that there is a general method applicable to any function $f$ analytic at 0 with a series expansion $x+a_kx^k+a_k+1x^k+1+cdots$ with $k>1$ and $a_k<0$: I learned about it in Chapter 8 of de Bruijn's Asymptotic Methods in Analysis, where it is shown that if the starting value is small enough, the $n$th iterate of $f$ is asymptotically equivalent to $((1-k)a_kn)^-1/(k-1)$. In our case, $k=3$ and $a_k=-1$ so $b_n sim (2n)^-1/2$ and $a_n sim (2n)^1/2$.



A sketch of the proof in the case at hand is as follows. First, show by induction that if $u_n$ is any sequence tending to zero and such that
$$u_n+1=u_n-u_n^2+O(u_n^3)$$
then $u_n = n^-1 + O(n^-2log n)$. This is the tricky part of the proof.



Next make a substitution $z_n= 2b_n^2$. We have
$$ b_n+1=b_n(1-b_n^2+b_n^4-cdots)$$
so
$$z_n+1=z_nleft(1-frac12z_n + frac14z_n^2+ cdotsright)^2 = z_n-z_n^2 + frac34z_n^3 + cdots$$
from which we get $z_n = n^-1+O(n^-2log n)$ and the asymptotics for $b_n$ follow.



Incidentally, the sequence $b_n$ is what you get by using Newton's method to find a root of $xe^-x^-2/2$. But I couldn't find a way to make that shed any light on the asymptotics...






share|cite|improve this answer











$endgroup$













    Your Answer





    StackExchange.ifUsing("editor", function ()
    return StackExchange.using("mathjaxEditing", function ()
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    );
    );
    , "mathjax-editing");

    StackExchange.ready(function()
    var channelOptions =
    tags: "".split(" "),
    id: "69"
    ;
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function()
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled)
    StackExchange.using("snippets", function()
    createEditor();
    );

    else
    createEditor();

    );

    function createEditor()
    StackExchange.prepareEditor(
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader:
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    ,
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    );



    );













    draft saved

    draft discarded


















    StackExchange.ready(
    function ()
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f29777%2fclosed-form-for-the-sequence-defined-by-a-0-1-and-a-n1-a-n-a-n-1%23new-answer', 'question_page');

    );

    Post as a guest















    Required, but never shown

























    6 Answers
    6






    active

    oldest

    votes








    6 Answers
    6






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    14












    $begingroup$

    I agree, a closed form is very unlikely.
    As for more precise asymptotics, I think $a_n = sqrt2n + 1/8,frac sqrt 2ln left( n right) sqrt n-frac 1
    128,frac sqrt 2 left( ln left( n right) -2 right) ^2 + o(1)
    n^3/2$






    share|cite|improve this answer









    $endgroup$








    • 4




      $begingroup$
      +1: The first two terms seem to match what I have :-) Can you please elaborate on how you got this? Seems like the $C$ in my answer can probably be given in "closed form" using your answer.
      $endgroup$
      – Aryabhata
      Mar 29 '11 at 20:03











    • $begingroup$
      It seems you are also this guy. Mysterious stranger. :)
      $endgroup$
      – Wok
      Mar 29 '11 at 21:23










    • $begingroup$
      @Robert: You can ask a moderator to merge your two accounts.
      $endgroup$
      – Bill Dubuque
      Mar 30 '11 at 19:41










    • $begingroup$
      @Bill: thanks for the headsup.
      $endgroup$
      – Willie Wong
      Mar 30 '11 at 20:31










    • $begingroup$
      @Robert: since I'm pretty sure you are who you are, I've taken the liberty to merge your old unregistered account into your new one.
      $endgroup$
      – Willie Wong
      Mar 30 '11 at 20:40















    14












    $begingroup$

    I agree, a closed form is very unlikely.
    As for more precise asymptotics, I think $a_n = sqrt2n + 1/8,frac sqrt 2ln left( n right) sqrt n-frac 1
    128,frac sqrt 2 left( ln left( n right) -2 right) ^2 + o(1)
    n^3/2$






    share|cite|improve this answer









    $endgroup$








    • 4




      $begingroup$
      +1: The first two terms seem to match what I have :-) Can you please elaborate on how you got this? Seems like the $C$ in my answer can probably be given in "closed form" using your answer.
      $endgroup$
      – Aryabhata
      Mar 29 '11 at 20:03











    • $begingroup$
      It seems you are also this guy. Mysterious stranger. :)
      $endgroup$
      – Wok
      Mar 29 '11 at 21:23










    • $begingroup$
      @Robert: You can ask a moderator to merge your two accounts.
      $endgroup$
      – Bill Dubuque
      Mar 30 '11 at 19:41










    • $begingroup$
      @Bill: thanks for the headsup.
      $endgroup$
      – Willie Wong
      Mar 30 '11 at 20:31










    • $begingroup$
      @Robert: since I'm pretty sure you are who you are, I've taken the liberty to merge your old unregistered account into your new one.
      $endgroup$
      – Willie Wong
      Mar 30 '11 at 20:40













    14












    14








    14





    $begingroup$

    I agree, a closed form is very unlikely.
    As for more precise asymptotics, I think $a_n = sqrt2n + 1/8,frac sqrt 2ln left( n right) sqrt n-frac 1
    128,frac sqrt 2 left( ln left( n right) -2 right) ^2 + o(1)
    n^3/2$






    share|cite|improve this answer









    $endgroup$



    I agree, a closed form is very unlikely.
    As for more precise asymptotics, I think $a_n = sqrt2n + 1/8,frac sqrt 2ln left( n right) sqrt n-frac 1
    128,frac sqrt 2 left( ln left( n right) -2 right) ^2 + o(1)
    n^3/2$







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    answered Mar 29 '11 at 19:44









    Robert IsraelRobert Israel

    330k23219473




    330k23219473







    • 4




      $begingroup$
      +1: The first two terms seem to match what I have :-) Can you please elaborate on how you got this? Seems like the $C$ in my answer can probably be given in "closed form" using your answer.
      $endgroup$
      – Aryabhata
      Mar 29 '11 at 20:03











    • $begingroup$
      It seems you are also this guy. Mysterious stranger. :)
      $endgroup$
      – Wok
      Mar 29 '11 at 21:23










    • $begingroup$
      @Robert: You can ask a moderator to merge your two accounts.
      $endgroup$
      – Bill Dubuque
      Mar 30 '11 at 19:41










    • $begingroup$
      @Bill: thanks for the headsup.
      $endgroup$
      – Willie Wong
      Mar 30 '11 at 20:31










    • $begingroup$
      @Robert: since I'm pretty sure you are who you are, I've taken the liberty to merge your old unregistered account into your new one.
      $endgroup$
      – Willie Wong
      Mar 30 '11 at 20:40












    • 4




      $begingroup$
      +1: The first two terms seem to match what I have :-) Can you please elaborate on how you got this? Seems like the $C$ in my answer can probably be given in "closed form" using your answer.
      $endgroup$
      – Aryabhata
      Mar 29 '11 at 20:03











    • $begingroup$
      It seems you are also this guy. Mysterious stranger. :)
      $endgroup$
      – Wok
      Mar 29 '11 at 21:23










    • $begingroup$
      @Robert: You can ask a moderator to merge your two accounts.
      $endgroup$
      – Bill Dubuque
      Mar 30 '11 at 19:41










    • $begingroup$
      @Bill: thanks for the headsup.
      $endgroup$
      – Willie Wong
      Mar 30 '11 at 20:31










    • $begingroup$
      @Robert: since I'm pretty sure you are who you are, I've taken the liberty to merge your old unregistered account into your new one.
      $endgroup$
      – Willie Wong
      Mar 30 '11 at 20:40







    4




    4




    $begingroup$
    +1: The first two terms seem to match what I have :-) Can you please elaborate on how you got this? Seems like the $C$ in my answer can probably be given in "closed form" using your answer.
    $endgroup$
    – Aryabhata
    Mar 29 '11 at 20:03





    $begingroup$
    +1: The first two terms seem to match what I have :-) Can you please elaborate on how you got this? Seems like the $C$ in my answer can probably be given in "closed form" using your answer.
    $endgroup$
    – Aryabhata
    Mar 29 '11 at 20:03













    $begingroup$
    It seems you are also this guy. Mysterious stranger. :)
    $endgroup$
    – Wok
    Mar 29 '11 at 21:23




    $begingroup$
    It seems you are also this guy. Mysterious stranger. :)
    $endgroup$
    – Wok
    Mar 29 '11 at 21:23












    $begingroup$
    @Robert: You can ask a moderator to merge your two accounts.
    $endgroup$
    – Bill Dubuque
    Mar 30 '11 at 19:41




    $begingroup$
    @Robert: You can ask a moderator to merge your two accounts.
    $endgroup$
    – Bill Dubuque
    Mar 30 '11 at 19:41












    $begingroup$
    @Bill: thanks for the headsup.
    $endgroup$
    – Willie Wong
    Mar 30 '11 at 20:31




    $begingroup$
    @Bill: thanks for the headsup.
    $endgroup$
    – Willie Wong
    Mar 30 '11 at 20:31












    $begingroup$
    @Robert: since I'm pretty sure you are who you are, I've taken the liberty to merge your old unregistered account into your new one.
    $endgroup$
    – Willie Wong
    Mar 30 '11 at 20:40




    $begingroup$
    @Robert: since I'm pretty sure you are who you are, I've taken the liberty to merge your old unregistered account into your new one.
    $endgroup$
    – Willie Wong
    Mar 30 '11 at 20:40











    21












    $begingroup$

    A closed form I doubt there is. But asymptotics are easy:
    $$
    a_n+1^2=a_n^2+2+1/a_n^2,
    $$

    hence, for every $nge1$,
    $$
    a_n^2=2n+1+sum_k=0^n-1frac1a_k^2.qquadqquadqquadqquad (*)
    $$

    This shows that $a_n^2ge2n+2$ for every $nge1$, for example $a_100gesqrt202>10sqrt2>14$. In particular, $a_nto+infty$. Plugging this into $(*)$ yields $a_n^2=2n+1+o(n)$ hence
    $$
    sqrt2nle a_nlesqrt2n+o(sqrtn).
    $$

    At this point, we know that $a_n^2ge2n+2$ for every $nge1$. Using $(*)$ again, one sees that, for every $nge1$,
    $$
    a_n^2le2n+2+sum_k=1^n-1frac12+2kle2n+2+frac12log(n).
    $$

    Which already shows that $$14.2<a_100<14.3$$
    Plugging this upper bound of $a_n^2$ into $(*)$ would yield a refined lower bound of $a_n^2$. And one could then plug this refined lower bound into $(*)$ again to get a refined upper bound. And so on, back and forth between better and better upper bounds and better and better lower bounds. (No more asymptotics here.)






    share|cite|improve this answer











    $endgroup$












    • $begingroup$
      I just tried to understand this answer again, but I didn't understood, why $2n+1+sum_0le k<na_k^-2=2n+1+o(n)$
      $endgroup$
      – FUZxxl
      May 10 '11 at 20:15






    • 3




      $begingroup$
      The result is quite general: for every nonnegative sequence $(x_n)$ such that $x_n=o(1)$, $sum_kle nx_k=o(n)$. You could try to prove this by the usual epsilon-delta method.
      $endgroup$
      – Did
      May 11 '11 at 5:30










    • $begingroup$
      @FUZxxl: what's more, since $a_k>sqrt2k+1$, we have that $sum_0le k<na_k^-2<frac12gamma+log(2)+frac12log(n)+frac148n^2$
      $endgroup$
      – robjohn
      Aug 16 '11 at 12:07
















    21












    $begingroup$

    A closed form I doubt there is. But asymptotics are easy:
    $$
    a_n+1^2=a_n^2+2+1/a_n^2,
    $$

    hence, for every $nge1$,
    $$
    a_n^2=2n+1+sum_k=0^n-1frac1a_k^2.qquadqquadqquadqquad (*)
    $$

    This shows that $a_n^2ge2n+2$ for every $nge1$, for example $a_100gesqrt202>10sqrt2>14$. In particular, $a_nto+infty$. Plugging this into $(*)$ yields $a_n^2=2n+1+o(n)$ hence
    $$
    sqrt2nle a_nlesqrt2n+o(sqrtn).
    $$

    At this point, we know that $a_n^2ge2n+2$ for every $nge1$. Using $(*)$ again, one sees that, for every $nge1$,
    $$
    a_n^2le2n+2+sum_k=1^n-1frac12+2kle2n+2+frac12log(n).
    $$

    Which already shows that $$14.2<a_100<14.3$$
    Plugging this upper bound of $a_n^2$ into $(*)$ would yield a refined lower bound of $a_n^2$. And one could then plug this refined lower bound into $(*)$ again to get a refined upper bound. And so on, back and forth between better and better upper bounds and better and better lower bounds. (No more asymptotics here.)






    share|cite|improve this answer











    $endgroup$












    • $begingroup$
      I just tried to understand this answer again, but I didn't understood, why $2n+1+sum_0le k<na_k^-2=2n+1+o(n)$
      $endgroup$
      – FUZxxl
      May 10 '11 at 20:15






    • 3




      $begingroup$
      The result is quite general: for every nonnegative sequence $(x_n)$ such that $x_n=o(1)$, $sum_kle nx_k=o(n)$. You could try to prove this by the usual epsilon-delta method.
      $endgroup$
      – Did
      May 11 '11 at 5:30










    • $begingroup$
      @FUZxxl: what's more, since $a_k>sqrt2k+1$, we have that $sum_0le k<na_k^-2<frac12gamma+log(2)+frac12log(n)+frac148n^2$
      $endgroup$
      – robjohn
      Aug 16 '11 at 12:07














    21












    21








    21





    $begingroup$

    A closed form I doubt there is. But asymptotics are easy:
    $$
    a_n+1^2=a_n^2+2+1/a_n^2,
    $$

    hence, for every $nge1$,
    $$
    a_n^2=2n+1+sum_k=0^n-1frac1a_k^2.qquadqquadqquadqquad (*)
    $$

    This shows that $a_n^2ge2n+2$ for every $nge1$, for example $a_100gesqrt202>10sqrt2>14$. In particular, $a_nto+infty$. Plugging this into $(*)$ yields $a_n^2=2n+1+o(n)$ hence
    $$
    sqrt2nle a_nlesqrt2n+o(sqrtn).
    $$

    At this point, we know that $a_n^2ge2n+2$ for every $nge1$. Using $(*)$ again, one sees that, for every $nge1$,
    $$
    a_n^2le2n+2+sum_k=1^n-1frac12+2kle2n+2+frac12log(n).
    $$

    Which already shows that $$14.2<a_100<14.3$$
    Plugging this upper bound of $a_n^2$ into $(*)$ would yield a refined lower bound of $a_n^2$. And one could then plug this refined lower bound into $(*)$ again to get a refined upper bound. And so on, back and forth between better and better upper bounds and better and better lower bounds. (No more asymptotics here.)






    share|cite|improve this answer











    $endgroup$



    A closed form I doubt there is. But asymptotics are easy:
    $$
    a_n+1^2=a_n^2+2+1/a_n^2,
    $$

    hence, for every $nge1$,
    $$
    a_n^2=2n+1+sum_k=0^n-1frac1a_k^2.qquadqquadqquadqquad (*)
    $$

    This shows that $a_n^2ge2n+2$ for every $nge1$, for example $a_100gesqrt202>10sqrt2>14$. In particular, $a_nto+infty$. Plugging this into $(*)$ yields $a_n^2=2n+1+o(n)$ hence
    $$
    sqrt2nle a_nlesqrt2n+o(sqrtn).
    $$

    At this point, we know that $a_n^2ge2n+2$ for every $nge1$. Using $(*)$ again, one sees that, for every $nge1$,
    $$
    a_n^2le2n+2+sum_k=1^n-1frac12+2kle2n+2+frac12log(n).
    $$

    Which already shows that $$14.2<a_100<14.3$$
    Plugging this upper bound of $a_n^2$ into $(*)$ would yield a refined lower bound of $a_n^2$. And one could then plug this refined lower bound into $(*)$ again to get a refined upper bound. And so on, back and forth between better and better upper bounds and better and better lower bounds. (No more asymptotics here.)







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited Sep 21 '18 at 18:01

























    answered Mar 29 '11 at 19:10









    DidDid

    249k23227466




    249k23227466











    • $begingroup$
      I just tried to understand this answer again, but I didn't understood, why $2n+1+sum_0le k<na_k^-2=2n+1+o(n)$
      $endgroup$
      – FUZxxl
      May 10 '11 at 20:15






    • 3




      $begingroup$
      The result is quite general: for every nonnegative sequence $(x_n)$ such that $x_n=o(1)$, $sum_kle nx_k=o(n)$. You could try to prove this by the usual epsilon-delta method.
      $endgroup$
      – Did
      May 11 '11 at 5:30










    • $begingroup$
      @FUZxxl: what's more, since $a_k>sqrt2k+1$, we have that $sum_0le k<na_k^-2<frac12gamma+log(2)+frac12log(n)+frac148n^2$
      $endgroup$
      – robjohn
      Aug 16 '11 at 12:07

















    • $begingroup$
      I just tried to understand this answer again, but I didn't understood, why $2n+1+sum_0le k<na_k^-2=2n+1+o(n)$
      $endgroup$
      – FUZxxl
      May 10 '11 at 20:15






    • 3




      $begingroup$
      The result is quite general: for every nonnegative sequence $(x_n)$ such that $x_n=o(1)$, $sum_kle nx_k=o(n)$. You could try to prove this by the usual epsilon-delta method.
      $endgroup$
      – Did
      May 11 '11 at 5:30










    • $begingroup$
      @FUZxxl: what's more, since $a_k>sqrt2k+1$, we have that $sum_0le k<na_k^-2<frac12gamma+log(2)+frac12log(n)+frac148n^2$
      $endgroup$
      – robjohn
      Aug 16 '11 at 12:07
















    $begingroup$
    I just tried to understand this answer again, but I didn't understood, why $2n+1+sum_0le k<na_k^-2=2n+1+o(n)$
    $endgroup$
    – FUZxxl
    May 10 '11 at 20:15




    $begingroup$
    I just tried to understand this answer again, but I didn't understood, why $2n+1+sum_0le k<na_k^-2=2n+1+o(n)$
    $endgroup$
    – FUZxxl
    May 10 '11 at 20:15




    3




    3




    $begingroup$
    The result is quite general: for every nonnegative sequence $(x_n)$ such that $x_n=o(1)$, $sum_kle nx_k=o(n)$. You could try to prove this by the usual epsilon-delta method.
    $endgroup$
    – Did
    May 11 '11 at 5:30




    $begingroup$
    The result is quite general: for every nonnegative sequence $(x_n)$ such that $x_n=o(1)$, $sum_kle nx_k=o(n)$. You could try to prove this by the usual epsilon-delta method.
    $endgroup$
    – Did
    May 11 '11 at 5:30












    $begingroup$
    @FUZxxl: what's more, since $a_k>sqrt2k+1$, we have that $sum_0le k<na_k^-2<frac12gamma+log(2)+frac12log(n)+frac148n^2$
    $endgroup$
    – robjohn
    Aug 16 '11 at 12:07





    $begingroup$
    @FUZxxl: what's more, since $a_k>sqrt2k+1$, we have that $sum_0le k<na_k^-2<frac12gamma+log(2)+frac12log(n)+frac148n^2$
    $endgroup$
    – robjohn
    Aug 16 '11 at 12:07












    10












    $begingroup$

    To elaborate on how I got my answer: I started with @Did's $a(n) approx sqrt2n$ and looked for a next term. $a(n) = sqrt2n$ would make $ a(n+1) - (a(n) + a(n)^-1) = sqrt 2,n+2-sqrt 2sqrt n-1/2,frac sqrt 2sqrt n = - fracsqrt28 n^-3/2 + O(n^-5/2)$. With $a(n) = sqrt2n + c n^-1/2$ I don't get a change in the $n^-3/2$ term, so I tried $a(n) = sqrt2n + c ln(n) n^-1/2$ and got
    $a(n+1) - (a(n) + a(n)^-1) = (-frac2sqrt8 + c) n^-3/2 + ldots$. So to get rid of the $n^-3/2$ term I want $c = frac2sqrt8$. Then look at the leading term for
    $a(n) = sqrt2n + frac2sqrt8 ln(n) n^-1/2$ and continue in that vein...






    share|cite|improve this answer











    $endgroup$












    • $begingroup$
      Not sure this try-and-guess procedure constitutes a proof. The argument in my post proves that $a_n=sqrt2n+o(sqrtn)$.
      $endgroup$
      – Did
      Apr 1 '11 at 6:36










    • $begingroup$
      @Didier: Do you disagree with my answer?
      $endgroup$
      – Aryabhata
      Apr 1 '11 at 14:35






    • 3




      $begingroup$
      You should edit your other answer, rather than adding a new one.
      $endgroup$
      – Aryabhata
      Apr 1 '11 at 14:36















    10












    $begingroup$

    To elaborate on how I got my answer: I started with @Did's $a(n) approx sqrt2n$ and looked for a next term. $a(n) = sqrt2n$ would make $ a(n+1) - (a(n) + a(n)^-1) = sqrt 2,n+2-sqrt 2sqrt n-1/2,frac sqrt 2sqrt n = - fracsqrt28 n^-3/2 + O(n^-5/2)$. With $a(n) = sqrt2n + c n^-1/2$ I don't get a change in the $n^-3/2$ term, so I tried $a(n) = sqrt2n + c ln(n) n^-1/2$ and got
    $a(n+1) - (a(n) + a(n)^-1) = (-frac2sqrt8 + c) n^-3/2 + ldots$. So to get rid of the $n^-3/2$ term I want $c = frac2sqrt8$. Then look at the leading term for
    $a(n) = sqrt2n + frac2sqrt8 ln(n) n^-1/2$ and continue in that vein...






    share|cite|improve this answer











    $endgroup$












    • $begingroup$
      Not sure this try-and-guess procedure constitutes a proof. The argument in my post proves that $a_n=sqrt2n+o(sqrtn)$.
      $endgroup$
      – Did
      Apr 1 '11 at 6:36










    • $begingroup$
      @Didier: Do you disagree with my answer?
      $endgroup$
      – Aryabhata
      Apr 1 '11 at 14:35






    • 3




      $begingroup$
      You should edit your other answer, rather than adding a new one.
      $endgroup$
      – Aryabhata
      Apr 1 '11 at 14:36













    10












    10








    10





    $begingroup$

    To elaborate on how I got my answer: I started with @Did's $a(n) approx sqrt2n$ and looked for a next term. $a(n) = sqrt2n$ would make $ a(n+1) - (a(n) + a(n)^-1) = sqrt 2,n+2-sqrt 2sqrt n-1/2,frac sqrt 2sqrt n = - fracsqrt28 n^-3/2 + O(n^-5/2)$. With $a(n) = sqrt2n + c n^-1/2$ I don't get a change in the $n^-3/2$ term, so I tried $a(n) = sqrt2n + c ln(n) n^-1/2$ and got
    $a(n+1) - (a(n) + a(n)^-1) = (-frac2sqrt8 + c) n^-3/2 + ldots$. So to get rid of the $n^-3/2$ term I want $c = frac2sqrt8$. Then look at the leading term for
    $a(n) = sqrt2n + frac2sqrt8 ln(n) n^-1/2$ and continue in that vein...






    share|cite|improve this answer











    $endgroup$



    To elaborate on how I got my answer: I started with @Did's $a(n) approx sqrt2n$ and looked for a next term. $a(n) = sqrt2n$ would make $ a(n+1) - (a(n) + a(n)^-1) = sqrt 2,n+2-sqrt 2sqrt n-1/2,frac sqrt 2sqrt n = - fracsqrt28 n^-3/2 + O(n^-5/2)$. With $a(n) = sqrt2n + c n^-1/2$ I don't get a change in the $n^-3/2$ term, so I tried $a(n) = sqrt2n + c ln(n) n^-1/2$ and got
    $a(n+1) - (a(n) + a(n)^-1) = (-frac2sqrt8 + c) n^-3/2 + ldots$. So to get rid of the $n^-3/2$ term I want $c = frac2sqrt8$. Then look at the leading term for
    $a(n) = sqrt2n + frac2sqrt8 ln(n) n^-1/2$ and continue in that vein...







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited Sep 2 '16 at 7:15









    Did

    249k23227466




    249k23227466










    answered Apr 1 '11 at 5:27









    Robert IsraelRobert Israel

    330k23219473




    330k23219473











    • $begingroup$
      Not sure this try-and-guess procedure constitutes a proof. The argument in my post proves that $a_n=sqrt2n+o(sqrtn)$.
      $endgroup$
      – Did
      Apr 1 '11 at 6:36










    • $begingroup$
      @Didier: Do you disagree with my answer?
      $endgroup$
      – Aryabhata
      Apr 1 '11 at 14:35






    • 3




      $begingroup$
      You should edit your other answer, rather than adding a new one.
      $endgroup$
      – Aryabhata
      Apr 1 '11 at 14:36
















    • $begingroup$
      Not sure this try-and-guess procedure constitutes a proof. The argument in my post proves that $a_n=sqrt2n+o(sqrtn)$.
      $endgroup$
      – Did
      Apr 1 '11 at 6:36










    • $begingroup$
      @Didier: Do you disagree with my answer?
      $endgroup$
      – Aryabhata
      Apr 1 '11 at 14:35






    • 3




      $begingroup$
      You should edit your other answer, rather than adding a new one.
      $endgroup$
      – Aryabhata
      Apr 1 '11 at 14:36















    $begingroup$
    Not sure this try-and-guess procedure constitutes a proof. The argument in my post proves that $a_n=sqrt2n+o(sqrtn)$.
    $endgroup$
    – Did
    Apr 1 '11 at 6:36




    $begingroup$
    Not sure this try-and-guess procedure constitutes a proof. The argument in my post proves that $a_n=sqrt2n+o(sqrtn)$.
    $endgroup$
    – Did
    Apr 1 '11 at 6:36












    $begingroup$
    @Didier: Do you disagree with my answer?
    $endgroup$
    – Aryabhata
    Apr 1 '11 at 14:35




    $begingroup$
    @Didier: Do you disagree with my answer?
    $endgroup$
    – Aryabhata
    Apr 1 '11 at 14:35




    3




    3




    $begingroup$
    You should edit your other answer, rather than adding a new one.
    $endgroup$
    – Aryabhata
    Apr 1 '11 at 14:36




    $begingroup$
    You should edit your other answer, rather than adding a new one.
    $endgroup$
    – Aryabhata
    Apr 1 '11 at 14:36











    6












    $begingroup$

    From my answer here: Given $a_1=1, a_n+1=a_n+frac1a_n$, find $lim limits_ntoinftyfraca_nn$



    Reposting here, as it is kind of lost in that thread and this thread is more suitable for it.



    Note: I have no clue if a closed form exists, but here is an asymptotic estimate...



    I think we can show that $$displaystyle a_n^2 sim 2n + dfraclog n2 - C$$ for some constant $displaystyle C gt 0$



    By $displaystyle x_n sim y_n$ I mean $displaystyle lim_n to infty (x_n - y_n) = 0$



    Consider $b_n = a_n^2 - 2n$



    Then we have that $displaystyle b_n+1 = b_n + dfrac1b_n + 2n$



    Notice that $b_0 gt 0$ and thus $displaystyle b_n gt 0$.



    (Note that the other thread linked above starts with $a_1 = 1$ and not $a_0 = 1$.)



    We can easily show that $b_n lt 2 + log n$, as



    $b_n+1 - b_n = dfrac1b_n + 2n lt dfrac12n$



    Adding up gives us the easy upper bound. Note, even though we can give tighter bounds, this is sufficient for our purposes.



    Now we have that, for sufficiently large $displaystyle m,n$



    $displaystyle b_m+1 - b_n = sum_k=n^m dfrac1b_k + 2k$



    we have that



    $displaystyle sum_k=n^m dfrac12k gt b_m+1 - b_n gt sum_k=n^m dfrac12k(1- dfracb_k2k)$



    (Here we used $displaystyle dfrac11+x gt 1-x, 1 gt x gt 0$)



    Now Since $b_k lt 2 + log k$, we have that



    $displaystyle sum_k=n^m dfrac12k gt b_m+1 - b_n gt sum_k=n^m dfrac12k - sum_k=n^m dfrac2 + log k 4k^2$



    Using the fact that $displaystyle H_m - H_n = log(dfracm+1n) + O(dfrac1n) + O(dfrac1n - dfrac1m)$, where $displaystyle H_n = sum_k=1^n dfrac1k$ is the $displaystyle n^th$ harmonic number.



    We see that,



    if $c_n = b_n - dfraclog n2$, then



    $displaystyle O(dfrac1n -dfrac1m) + O(dfrac1n) gt c_m+1 - c_n gt O(dfrac1n -dfrac1m) + O(dfrac1n) -sum_k=n^m dfrac2 + log k 4k^2$



    Now $displaystyle sum_k=1^infty dfrac2 + log kk^2$ is convergent and so by the Cauchy convergence criteria, we have that $displaystyle c_n$ is convergent.



    Thus the sequence $displaystyle a_n^2 - 2n - dfraclog n2$ converges and hence, for some $displaystyle C$ we have that



    $$displaystyle a_n^2 sim 2n + dfraclog n2 - C$$



    or in other words



    $$displaystyle a_n sim sqrt2n + dfraclog n2 - C$$



    A quick (possibly incorrect) computer simulation seems to show a very slow convergence to $displaystyle C = 1.47812676429749dots$



    Note: Didier suggested an alternate proof in the comments below, which might simpler.






    share|cite|improve this answer











    $endgroup$












    • $begingroup$
      That's still only an asymptotic.
      $endgroup$
      – FUZxxl
      Mar 29 '11 at 19:33






    • 1




      $begingroup$
      @Fuz: Yes, I doubt if there is a known closed form for it. But being able to peg down the difference from $2n + log n/2$ to be a constant should be reasonably useful, I would say.
      $endgroup$
      – Aryabhata
      Mar 29 '11 at 19:42











    • $begingroup$
      @Moron This is to answer to the question you asked in a comment on Robert's post. First, do we agree that you ask me to check the mathematical accuracy of your answer? And that I only do that and state publicly the result of the checking because you asked me to? If I misunderstood you, please say so and I will delete my comment right away. So... here we go. To summarize, the general line of your proof is correct but some details annoy me, most often because you make some unnecessary détours where a more direct path exists. .../...
      $endgroup$
      – Did
      Apr 2 '11 at 10:04










    • $begingroup$
      .../... For example: (1) $b_n>0$ for every $nge0$ and not only for $nge3$. (2) The easy argument I can think of to bound $b_n$ is based on the inequality $b_n+2nge1$ for every $nge0$, it leads to $b_nle n+1$ and not to $b_n<2n$. Comment on (2): as a consequence, when I read that you will use $b_n<2n$ and that there is an easy argument to prove it, I am puzzled and worried that I missed something or that my argument leading to $b_nle n+1$ is wrong, so, ultimately, I am distracted. And this is bad. :-) .../...
      $endgroup$
      – Did
      Apr 2 '11 at 10:05










    • $begingroup$
      .../... (3) The easy argument I can think of to bound $b_n$ by a $log$ is based on he inequality $b_n+2nge2n$ for every $nge1$ and leads to an upper bound of leading term $frac12log(n)$ and not $log(n)$. So the comment on (2) applies here as well, mutatis mutandis. (3') You should expand this step. (4) The bound $b_k<log(k)$ is not useful the first time you invoke it (but it is useful the second time). (5) I would postpone the introduction of $log(n)$ to as late a point as possible. If you define $c_n$ by $c_n=b_n-frac12H_n$, $(c_n)$ is nonincreasing and bounded below by .../...
      $endgroup$
      – Did
      Apr 2 '11 at 10:06















    6












    $begingroup$

    From my answer here: Given $a_1=1, a_n+1=a_n+frac1a_n$, find $lim limits_ntoinftyfraca_nn$



    Reposting here, as it is kind of lost in that thread and this thread is more suitable for it.



    Note: I have no clue if a closed form exists, but here is an asymptotic estimate...



    I think we can show that $$displaystyle a_n^2 sim 2n + dfraclog n2 - C$$ for some constant $displaystyle C gt 0$



    By $displaystyle x_n sim y_n$ I mean $displaystyle lim_n to infty (x_n - y_n) = 0$



    Consider $b_n = a_n^2 - 2n$



    Then we have that $displaystyle b_n+1 = b_n + dfrac1b_n + 2n$



    Notice that $b_0 gt 0$ and thus $displaystyle b_n gt 0$.



    (Note that the other thread linked above starts with $a_1 = 1$ and not $a_0 = 1$.)



    We can easily show that $b_n lt 2 + log n$, as



    $b_n+1 - b_n = dfrac1b_n + 2n lt dfrac12n$



    Adding up gives us the easy upper bound. Note, even though we can give tighter bounds, this is sufficient for our purposes.



    Now we have that, for sufficiently large $displaystyle m,n$



    $displaystyle b_m+1 - b_n = sum_k=n^m dfrac1b_k + 2k$



    we have that



    $displaystyle sum_k=n^m dfrac12k gt b_m+1 - b_n gt sum_k=n^m dfrac12k(1- dfracb_k2k)$



    (Here we used $displaystyle dfrac11+x gt 1-x, 1 gt x gt 0$)



    Now Since $b_k lt 2 + log k$, we have that



    $displaystyle sum_k=n^m dfrac12k gt b_m+1 - b_n gt sum_k=n^m dfrac12k - sum_k=n^m dfrac2 + log k 4k^2$



    Using the fact that $displaystyle H_m - H_n = log(dfracm+1n) + O(dfrac1n) + O(dfrac1n - dfrac1m)$, where $displaystyle H_n = sum_k=1^n dfrac1k$ is the $displaystyle n^th$ harmonic number.



    We see that,



    if $c_n = b_n - dfraclog n2$, then



    $displaystyle O(dfrac1n -dfrac1m) + O(dfrac1n) gt c_m+1 - c_n gt O(dfrac1n -dfrac1m) + O(dfrac1n) -sum_k=n^m dfrac2 + log k 4k^2$



    Now $displaystyle sum_k=1^infty dfrac2 + log kk^2$ is convergent and so by the Cauchy convergence criteria, we have that $displaystyle c_n$ is convergent.



    Thus the sequence $displaystyle a_n^2 - 2n - dfraclog n2$ converges and hence, for some $displaystyle C$ we have that



    $$displaystyle a_n^2 sim 2n + dfraclog n2 - C$$



    or in other words



    $$displaystyle a_n sim sqrt2n + dfraclog n2 - C$$



    A quick (possibly incorrect) computer simulation seems to show a very slow convergence to $displaystyle C = 1.47812676429749dots$



    Note: Didier suggested an alternate proof in the comments below, which might simpler.






    share|cite|improve this answer











    $endgroup$












    • $begingroup$
      That's still only an asymptotic.
      $endgroup$
      – FUZxxl
      Mar 29 '11 at 19:33






    • 1




      $begingroup$
      @Fuz: Yes, I doubt if there is a known closed form for it. But being able to peg down the difference from $2n + log n/2$ to be a constant should be reasonably useful, I would say.
      $endgroup$
      – Aryabhata
      Mar 29 '11 at 19:42











    • $begingroup$
      @Moron This is to answer to the question you asked in a comment on Robert's post. First, do we agree that you ask me to check the mathematical accuracy of your answer? And that I only do that and state publicly the result of the checking because you asked me to? If I misunderstood you, please say so and I will delete my comment right away. So... here we go. To summarize, the general line of your proof is correct but some details annoy me, most often because you make some unnecessary détours where a more direct path exists. .../...
      $endgroup$
      – Did
      Apr 2 '11 at 10:04










    • $begingroup$
      .../... For example: (1) $b_n>0$ for every $nge0$ and not only for $nge3$. (2) The easy argument I can think of to bound $b_n$ is based on the inequality $b_n+2nge1$ for every $nge0$, it leads to $b_nle n+1$ and not to $b_n<2n$. Comment on (2): as a consequence, when I read that you will use $b_n<2n$ and that there is an easy argument to prove it, I am puzzled and worried that I missed something or that my argument leading to $b_nle n+1$ is wrong, so, ultimately, I am distracted. And this is bad. :-) .../...
      $endgroup$
      – Did
      Apr 2 '11 at 10:05










    • $begingroup$
      .../... (3) The easy argument I can think of to bound $b_n$ by a $log$ is based on he inequality $b_n+2nge2n$ for every $nge1$ and leads to an upper bound of leading term $frac12log(n)$ and not $log(n)$. So the comment on (2) applies here as well, mutatis mutandis. (3') You should expand this step. (4) The bound $b_k<log(k)$ is not useful the first time you invoke it (but it is useful the second time). (5) I would postpone the introduction of $log(n)$ to as late a point as possible. If you define $c_n$ by $c_n=b_n-frac12H_n$, $(c_n)$ is nonincreasing and bounded below by .../...
      $endgroup$
      – Did
      Apr 2 '11 at 10:06













    6












    6








    6





    $begingroup$

    From my answer here: Given $a_1=1, a_n+1=a_n+frac1a_n$, find $lim limits_ntoinftyfraca_nn$



    Reposting here, as it is kind of lost in that thread and this thread is more suitable for it.



    Note: I have no clue if a closed form exists, but here is an asymptotic estimate...



    I think we can show that $$displaystyle a_n^2 sim 2n + dfraclog n2 - C$$ for some constant $displaystyle C gt 0$



    By $displaystyle x_n sim y_n$ I mean $displaystyle lim_n to infty (x_n - y_n) = 0$



    Consider $b_n = a_n^2 - 2n$



    Then we have that $displaystyle b_n+1 = b_n + dfrac1b_n + 2n$



    Notice that $b_0 gt 0$ and thus $displaystyle b_n gt 0$.



    (Note that the other thread linked above starts with $a_1 = 1$ and not $a_0 = 1$.)



    We can easily show that $b_n lt 2 + log n$, as



    $b_n+1 - b_n = dfrac1b_n + 2n lt dfrac12n$



    Adding up gives us the easy upper bound. Note, even though we can give tighter bounds, this is sufficient for our purposes.



    Now we have that, for sufficiently large $displaystyle m,n$



    $displaystyle b_m+1 - b_n = sum_k=n^m dfrac1b_k + 2k$



    we have that



    $displaystyle sum_k=n^m dfrac12k gt b_m+1 - b_n gt sum_k=n^m dfrac12k(1- dfracb_k2k)$



    (Here we used $displaystyle dfrac11+x gt 1-x, 1 gt x gt 0$)



    Now Since $b_k lt 2 + log k$, we have that



    $displaystyle sum_k=n^m dfrac12k gt b_m+1 - b_n gt sum_k=n^m dfrac12k - sum_k=n^m dfrac2 + log k 4k^2$



    Using the fact that $displaystyle H_m - H_n = log(dfracm+1n) + O(dfrac1n) + O(dfrac1n - dfrac1m)$, where $displaystyle H_n = sum_k=1^n dfrac1k$ is the $displaystyle n^th$ harmonic number.



    We see that,



    if $c_n = b_n - dfraclog n2$, then



    $displaystyle O(dfrac1n -dfrac1m) + O(dfrac1n) gt c_m+1 - c_n gt O(dfrac1n -dfrac1m) + O(dfrac1n) -sum_k=n^m dfrac2 + log k 4k^2$



    Now $displaystyle sum_k=1^infty dfrac2 + log kk^2$ is convergent and so by the Cauchy convergence criteria, we have that $displaystyle c_n$ is convergent.



    Thus the sequence $displaystyle a_n^2 - 2n - dfraclog n2$ converges and hence, for some $displaystyle C$ we have that



    $$displaystyle a_n^2 sim 2n + dfraclog n2 - C$$



    or in other words



    $$displaystyle a_n sim sqrt2n + dfraclog n2 - C$$



    A quick (possibly incorrect) computer simulation seems to show a very slow convergence to $displaystyle C = 1.47812676429749dots$



    Note: Didier suggested an alternate proof in the comments below, which might simpler.






    share|cite|improve this answer











    $endgroup$



    From my answer here: Given $a_1=1, a_n+1=a_n+frac1a_n$, find $lim limits_ntoinftyfraca_nn$



    Reposting here, as it is kind of lost in that thread and this thread is more suitable for it.



    Note: I have no clue if a closed form exists, but here is an asymptotic estimate...



    I think we can show that $$displaystyle a_n^2 sim 2n + dfraclog n2 - C$$ for some constant $displaystyle C gt 0$



    By $displaystyle x_n sim y_n$ I mean $displaystyle lim_n to infty (x_n - y_n) = 0$



    Consider $b_n = a_n^2 - 2n$



    Then we have that $displaystyle b_n+1 = b_n + dfrac1b_n + 2n$



    Notice that $b_0 gt 0$ and thus $displaystyle b_n gt 0$.



    (Note that the other thread linked above starts with $a_1 = 1$ and not $a_0 = 1$.)



    We can easily show that $b_n lt 2 + log n$, as



    $b_n+1 - b_n = dfrac1b_n + 2n lt dfrac12n$



    Adding up gives us the easy upper bound. Note, even though we can give tighter bounds, this is sufficient for our purposes.



    Now we have that, for sufficiently large $displaystyle m,n$



    $displaystyle b_m+1 - b_n = sum_k=n^m dfrac1b_k + 2k$



    we have that



    $displaystyle sum_k=n^m dfrac12k gt b_m+1 - b_n gt sum_k=n^m dfrac12k(1- dfracb_k2k)$



    (Here we used $displaystyle dfrac11+x gt 1-x, 1 gt x gt 0$)



    Now Since $b_k lt 2 + log k$, we have that



    $displaystyle sum_k=n^m dfrac12k gt b_m+1 - b_n gt sum_k=n^m dfrac12k - sum_k=n^m dfrac2 + log k 4k^2$



    Using the fact that $displaystyle H_m - H_n = log(dfracm+1n) + O(dfrac1n) + O(dfrac1n - dfrac1m)$, where $displaystyle H_n = sum_k=1^n dfrac1k$ is the $displaystyle n^th$ harmonic number.



    We see that,



    if $c_n = b_n - dfraclog n2$, then



    $displaystyle O(dfrac1n -dfrac1m) + O(dfrac1n) gt c_m+1 - c_n gt O(dfrac1n -dfrac1m) + O(dfrac1n) -sum_k=n^m dfrac2 + log k 4k^2$



    Now $displaystyle sum_k=1^infty dfrac2 + log kk^2$ is convergent and so by the Cauchy convergence criteria, we have that $displaystyle c_n$ is convergent.



    Thus the sequence $displaystyle a_n^2 - 2n - dfraclog n2$ converges and hence, for some $displaystyle C$ we have that



    $$displaystyle a_n^2 sim 2n + dfraclog n2 - C$$



    or in other words



    $$displaystyle a_n sim sqrt2n + dfraclog n2 - C$$



    A quick (possibly incorrect) computer simulation seems to show a very slow convergence to $displaystyle C = 1.47812676429749dots$



    Note: Didier suggested an alternate proof in the comments below, which might simpler.







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited Apr 13 '17 at 12:21









    Community

    1




    1










    answered Mar 29 '11 at 19:27









    AryabhataAryabhata

    70.2k6157247




    70.2k6157247











    • $begingroup$
      That's still only an asymptotic.
      $endgroup$
      – FUZxxl
      Mar 29 '11 at 19:33






    • 1




      $begingroup$
      @Fuz: Yes, I doubt if there is a known closed form for it. But being able to peg down the difference from $2n + log n/2$ to be a constant should be reasonably useful, I would say.
      $endgroup$
      – Aryabhata
      Mar 29 '11 at 19:42











    • $begingroup$
      @Moron This is to answer to the question you asked in a comment on Robert's post. First, do we agree that you ask me to check the mathematical accuracy of your answer? And that I only do that and state publicly the result of the checking because you asked me to? If I misunderstood you, please say so and I will delete my comment right away. So... here we go. To summarize, the general line of your proof is correct but some details annoy me, most often because you make some unnecessary détours where a more direct path exists. .../...
      $endgroup$
      – Did
      Apr 2 '11 at 10:04










    • $begingroup$
      .../... For example: (1) $b_n>0$ for every $nge0$ and not only for $nge3$. (2) The easy argument I can think of to bound $b_n$ is based on the inequality $b_n+2nge1$ for every $nge0$, it leads to $b_nle n+1$ and not to $b_n<2n$. Comment on (2): as a consequence, when I read that you will use $b_n<2n$ and that there is an easy argument to prove it, I am puzzled and worried that I missed something or that my argument leading to $b_nle n+1$ is wrong, so, ultimately, I am distracted. And this is bad. :-) .../...
      $endgroup$
      – Did
      Apr 2 '11 at 10:05










    • $begingroup$
      .../... (3) The easy argument I can think of to bound $b_n$ by a $log$ is based on he inequality $b_n+2nge2n$ for every $nge1$ and leads to an upper bound of leading term $frac12log(n)$ and not $log(n)$. So the comment on (2) applies here as well, mutatis mutandis. (3') You should expand this step. (4) The bound $b_k<log(k)$ is not useful the first time you invoke it (but it is useful the second time). (5) I would postpone the introduction of $log(n)$ to as late a point as possible. If you define $c_n$ by $c_n=b_n-frac12H_n$, $(c_n)$ is nonincreasing and bounded below by .../...
      $endgroup$
      – Did
      Apr 2 '11 at 10:06
















    • $begingroup$
      That's still only an asymptotic.
      $endgroup$
      – FUZxxl
      Mar 29 '11 at 19:33






    • 1




      $begingroup$
      @Fuz: Yes, I doubt if there is a known closed form for it. But being able to peg down the difference from $2n + log n/2$ to be a constant should be reasonably useful, I would say.
      $endgroup$
      – Aryabhata
      Mar 29 '11 at 19:42











    • $begingroup$
      @Moron This is to answer to the question you asked in a comment on Robert's post. First, do we agree that you ask me to check the mathematical accuracy of your answer? And that I only do that and state publicly the result of the checking because you asked me to? If I misunderstood you, please say so and I will delete my comment right away. So... here we go. To summarize, the general line of your proof is correct but some details annoy me, most often because you make some unnecessary détours where a more direct path exists. .../...
      $endgroup$
      – Did
      Apr 2 '11 at 10:04










    • $begingroup$
      .../... For example: (1) $b_n>0$ for every $nge0$ and not only for $nge3$. (2) The easy argument I can think of to bound $b_n$ is based on the inequality $b_n+2nge1$ for every $nge0$, it leads to $b_nle n+1$ and not to $b_n<2n$. Comment on (2): as a consequence, when I read that you will use $b_n<2n$ and that there is an easy argument to prove it, I am puzzled and worried that I missed something or that my argument leading to $b_nle n+1$ is wrong, so, ultimately, I am distracted. And this is bad. :-) .../...
      $endgroup$
      – Did
      Apr 2 '11 at 10:05










    • $begingroup$
      .../... (3) The easy argument I can think of to bound $b_n$ by a $log$ is based on he inequality $b_n+2nge2n$ for every $nge1$ and leads to an upper bound of leading term $frac12log(n)$ and not $log(n)$. So the comment on (2) applies here as well, mutatis mutandis. (3') You should expand this step. (4) The bound $b_k<log(k)$ is not useful the first time you invoke it (but it is useful the second time). (5) I would postpone the introduction of $log(n)$ to as late a point as possible. If you define $c_n$ by $c_n=b_n-frac12H_n$, $(c_n)$ is nonincreasing and bounded below by .../...
      $endgroup$
      – Did
      Apr 2 '11 at 10:06















    $begingroup$
    That's still only an asymptotic.
    $endgroup$
    – FUZxxl
    Mar 29 '11 at 19:33




    $begingroup$
    That's still only an asymptotic.
    $endgroup$
    – FUZxxl
    Mar 29 '11 at 19:33




    1




    1




    $begingroup$
    @Fuz: Yes, I doubt if there is a known closed form for it. But being able to peg down the difference from $2n + log n/2$ to be a constant should be reasonably useful, I would say.
    $endgroup$
    – Aryabhata
    Mar 29 '11 at 19:42





    $begingroup$
    @Fuz: Yes, I doubt if there is a known closed form for it. But being able to peg down the difference from $2n + log n/2$ to be a constant should be reasonably useful, I would say.
    $endgroup$
    – Aryabhata
    Mar 29 '11 at 19:42













    $begingroup$
    @Moron This is to answer to the question you asked in a comment on Robert's post. First, do we agree that you ask me to check the mathematical accuracy of your answer? And that I only do that and state publicly the result of the checking because you asked me to? If I misunderstood you, please say so and I will delete my comment right away. So... here we go. To summarize, the general line of your proof is correct but some details annoy me, most often because you make some unnecessary détours where a more direct path exists. .../...
    $endgroup$
    – Did
    Apr 2 '11 at 10:04




    $begingroup$
    @Moron This is to answer to the question you asked in a comment on Robert's post. First, do we agree that you ask me to check the mathematical accuracy of your answer? And that I only do that and state publicly the result of the checking because you asked me to? If I misunderstood you, please say so and I will delete my comment right away. So... here we go. To summarize, the general line of your proof is correct but some details annoy me, most often because you make some unnecessary détours where a more direct path exists. .../...
    $endgroup$
    – Did
    Apr 2 '11 at 10:04












    $begingroup$
    .../... For example: (1) $b_n>0$ for every $nge0$ and not only for $nge3$. (2) The easy argument I can think of to bound $b_n$ is based on the inequality $b_n+2nge1$ for every $nge0$, it leads to $b_nle n+1$ and not to $b_n<2n$. Comment on (2): as a consequence, when I read that you will use $b_n<2n$ and that there is an easy argument to prove it, I am puzzled and worried that I missed something or that my argument leading to $b_nle n+1$ is wrong, so, ultimately, I am distracted. And this is bad. :-) .../...
    $endgroup$
    – Did
    Apr 2 '11 at 10:05




    $begingroup$
    .../... For example: (1) $b_n>0$ for every $nge0$ and not only for $nge3$. (2) The easy argument I can think of to bound $b_n$ is based on the inequality $b_n+2nge1$ for every $nge0$, it leads to $b_nle n+1$ and not to $b_n<2n$. Comment on (2): as a consequence, when I read that you will use $b_n<2n$ and that there is an easy argument to prove it, I am puzzled and worried that I missed something or that my argument leading to $b_nle n+1$ is wrong, so, ultimately, I am distracted. And this is bad. :-) .../...
    $endgroup$
    – Did
    Apr 2 '11 at 10:05












    $begingroup$
    .../... (3) The easy argument I can think of to bound $b_n$ by a $log$ is based on he inequality $b_n+2nge2n$ for every $nge1$ and leads to an upper bound of leading term $frac12log(n)$ and not $log(n)$. So the comment on (2) applies here as well, mutatis mutandis. (3') You should expand this step. (4) The bound $b_k<log(k)$ is not useful the first time you invoke it (but it is useful the second time). (5) I would postpone the introduction of $log(n)$ to as late a point as possible. If you define $c_n$ by $c_n=b_n-frac12H_n$, $(c_n)$ is nonincreasing and bounded below by .../...
    $endgroup$
    – Did
    Apr 2 '11 at 10:06




    $begingroup$
    .../... (3) The easy argument I can think of to bound $b_n$ by a $log$ is based on he inequality $b_n+2nge2n$ for every $nge1$ and leads to an upper bound of leading term $frac12log(n)$ and not $log(n)$. So the comment on (2) applies here as well, mutatis mutandis. (3') You should expand this step. (4) The bound $b_k<log(k)$ is not useful the first time you invoke it (but it is useful the second time). (5) I would postpone the introduction of $log(n)$ to as late a point as possible. If you define $c_n$ by $c_n=b_n-frac12H_n$, $(c_n)$ is nonincreasing and bounded below by .../...
    $endgroup$
    – Did
    Apr 2 '11 at 10:06











    4












    $begingroup$

    Let us consider the functional formulation. Given $y(0)=1$, $y' = frac1y$ yields $ y(x) = sqrt2x+1$.




    I am not saying $a(n)=y(n)$. Yet there is a link between the two approaches (finite difference).






    share|cite|improve this answer











    $endgroup$








    • 1




      $begingroup$
      What are you saying? That $a_n=y(n)$? Clearly not, since $a_n$ is always rational and $y(n)$ is typically irrational. There's no reason why replacing a difference by a derivative should work.
      $endgroup$
      – joriki
      Mar 29 '11 at 19:28






    • 2




      $begingroup$
      @joriki: Actually, it could be useful. If I recollect correctly, Donald J Newman recommends this as a rough method to guess the asymptotic behaviour of certain sequences, in one of his books.
      $endgroup$
      – Aryabhata
      Mar 29 '11 at 19:39











    • $begingroup$
      @joriki Indeed one can compare the solution $y$ of the ODE $y'=varphi(y)$ with the sequence $(a_n)$ defined by $a_n+1=a_n+varphi(a_n)$. For $varphi(y)=-2y$ the result is interesting.
      $endgroup$
      – Did
      Apr 4 '11 at 17:51










    • $begingroup$
      @Moron See comment above.
      $endgroup$
      – Did
      Apr 4 '11 at 17:52










    • $begingroup$
      @Didier: Thanks for the example :-)
      $endgroup$
      – Aryabhata
      Apr 4 '11 at 17:58















    4












    $begingroup$

    Let us consider the functional formulation. Given $y(0)=1$, $y' = frac1y$ yields $ y(x) = sqrt2x+1$.




    I am not saying $a(n)=y(n)$. Yet there is a link between the two approaches (finite difference).






    share|cite|improve this answer











    $endgroup$








    • 1




      $begingroup$
      What are you saying? That $a_n=y(n)$? Clearly not, since $a_n$ is always rational and $y(n)$ is typically irrational. There's no reason why replacing a difference by a derivative should work.
      $endgroup$
      – joriki
      Mar 29 '11 at 19:28






    • 2




      $begingroup$
      @joriki: Actually, it could be useful. If I recollect correctly, Donald J Newman recommends this as a rough method to guess the asymptotic behaviour of certain sequences, in one of his books.
      $endgroup$
      – Aryabhata
      Mar 29 '11 at 19:39











    • $begingroup$
      @joriki Indeed one can compare the solution $y$ of the ODE $y'=varphi(y)$ with the sequence $(a_n)$ defined by $a_n+1=a_n+varphi(a_n)$. For $varphi(y)=-2y$ the result is interesting.
      $endgroup$
      – Did
      Apr 4 '11 at 17:51










    • $begingroup$
      @Moron See comment above.
      $endgroup$
      – Did
      Apr 4 '11 at 17:52










    • $begingroup$
      @Didier: Thanks for the example :-)
      $endgroup$
      – Aryabhata
      Apr 4 '11 at 17:58













    4












    4








    4





    $begingroup$

    Let us consider the functional formulation. Given $y(0)=1$, $y' = frac1y$ yields $ y(x) = sqrt2x+1$.




    I am not saying $a(n)=y(n)$. Yet there is a link between the two approaches (finite difference).






    share|cite|improve this answer











    $endgroup$



    Let us consider the functional formulation. Given $y(0)=1$, $y' = frac1y$ yields $ y(x) = sqrt2x+1$.




    I am not saying $a(n)=y(n)$. Yet there is a link between the two approaches (finite difference).







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited Mar 29 '11 at 19:32

























    answered Mar 29 '11 at 19:23









    WokWok

    1,5781323




    1,5781323







    • 1




      $begingroup$
      What are you saying? That $a_n=y(n)$? Clearly not, since $a_n$ is always rational and $y(n)$ is typically irrational. There's no reason why replacing a difference by a derivative should work.
      $endgroup$
      – joriki
      Mar 29 '11 at 19:28






    • 2




      $begingroup$
      @joriki: Actually, it could be useful. If I recollect correctly, Donald J Newman recommends this as a rough method to guess the asymptotic behaviour of certain sequences, in one of his books.
      $endgroup$
      – Aryabhata
      Mar 29 '11 at 19:39











    • $begingroup$
      @joriki Indeed one can compare the solution $y$ of the ODE $y'=varphi(y)$ with the sequence $(a_n)$ defined by $a_n+1=a_n+varphi(a_n)$. For $varphi(y)=-2y$ the result is interesting.
      $endgroup$
      – Did
      Apr 4 '11 at 17:51










    • $begingroup$
      @Moron See comment above.
      $endgroup$
      – Did
      Apr 4 '11 at 17:52










    • $begingroup$
      @Didier: Thanks for the example :-)
      $endgroup$
      – Aryabhata
      Apr 4 '11 at 17:58












    • 1




      $begingroup$
      What are you saying? That $a_n=y(n)$? Clearly not, since $a_n$ is always rational and $y(n)$ is typically irrational. There's no reason why replacing a difference by a derivative should work.
      $endgroup$
      – joriki
      Mar 29 '11 at 19:28






    • 2




      $begingroup$
      @joriki: Actually, it could be useful. If I recollect correctly, Donald J Newman recommends this as a rough method to guess the asymptotic behaviour of certain sequences, in one of his books.
      $endgroup$
      – Aryabhata
      Mar 29 '11 at 19:39











    • $begingroup$
      @joriki Indeed one can compare the solution $y$ of the ODE $y'=varphi(y)$ with the sequence $(a_n)$ defined by $a_n+1=a_n+varphi(a_n)$. For $varphi(y)=-2y$ the result is interesting.
      $endgroup$
      – Did
      Apr 4 '11 at 17:51










    • $begingroup$
      @Moron See comment above.
      $endgroup$
      – Did
      Apr 4 '11 at 17:52










    • $begingroup$
      @Didier: Thanks for the example :-)
      $endgroup$
      – Aryabhata
      Apr 4 '11 at 17:58







    1




    1




    $begingroup$
    What are you saying? That $a_n=y(n)$? Clearly not, since $a_n$ is always rational and $y(n)$ is typically irrational. There's no reason why replacing a difference by a derivative should work.
    $endgroup$
    – joriki
    Mar 29 '11 at 19:28




    $begingroup$
    What are you saying? That $a_n=y(n)$? Clearly not, since $a_n$ is always rational and $y(n)$ is typically irrational. There's no reason why replacing a difference by a derivative should work.
    $endgroup$
    – joriki
    Mar 29 '11 at 19:28




    2




    2




    $begingroup$
    @joriki: Actually, it could be useful. If I recollect correctly, Donald J Newman recommends this as a rough method to guess the asymptotic behaviour of certain sequences, in one of his books.
    $endgroup$
    – Aryabhata
    Mar 29 '11 at 19:39





    $begingroup$
    @joriki: Actually, it could be useful. If I recollect correctly, Donald J Newman recommends this as a rough method to guess the asymptotic behaviour of certain sequences, in one of his books.
    $endgroup$
    – Aryabhata
    Mar 29 '11 at 19:39













    $begingroup$
    @joriki Indeed one can compare the solution $y$ of the ODE $y'=varphi(y)$ with the sequence $(a_n)$ defined by $a_n+1=a_n+varphi(a_n)$. For $varphi(y)=-2y$ the result is interesting.
    $endgroup$
    – Did
    Apr 4 '11 at 17:51




    $begingroup$
    @joriki Indeed one can compare the solution $y$ of the ODE $y'=varphi(y)$ with the sequence $(a_n)$ defined by $a_n+1=a_n+varphi(a_n)$. For $varphi(y)=-2y$ the result is interesting.
    $endgroup$
    – Did
    Apr 4 '11 at 17:51












    $begingroup$
    @Moron See comment above.
    $endgroup$
    – Did
    Apr 4 '11 at 17:52




    $begingroup$
    @Moron See comment above.
    $endgroup$
    – Did
    Apr 4 '11 at 17:52












    $begingroup$
    @Didier: Thanks for the example :-)
    $endgroup$
    – Aryabhata
    Apr 4 '11 at 17:58




    $begingroup$
    @Didier: Thanks for the example :-)
    $endgroup$
    – Aryabhata
    Apr 4 '11 at 17:58











    0












    $begingroup$

    Let $b_n=a_n^-1$, so that $b_n+1=(b_n+b_n^-1)^-1$ is the $n$th iterate of $$f(x)=(x+x^-1)^-1=x-x^3+x^5-x^7+cdots$$
    The correct asymptotics have been given elsewhere, but this answer is to point out that there is a general method applicable to any function $f$ analytic at 0 with a series expansion $x+a_kx^k+a_k+1x^k+1+cdots$ with $k>1$ and $a_k<0$: I learned about it in Chapter 8 of de Bruijn's Asymptotic Methods in Analysis, where it is shown that if the starting value is small enough, the $n$th iterate of $f$ is asymptotically equivalent to $((1-k)a_kn)^-1/(k-1)$. In our case, $k=3$ and $a_k=-1$ so $b_n sim (2n)^-1/2$ and $a_n sim (2n)^1/2$.



    A sketch of the proof in the case at hand is as follows. First, show by induction that if $u_n$ is any sequence tending to zero and such that
    $$u_n+1=u_n-u_n^2+O(u_n^3)$$
    then $u_n = n^-1 + O(n^-2log n)$. This is the tricky part of the proof.



    Next make a substitution $z_n= 2b_n^2$. We have
    $$ b_n+1=b_n(1-b_n^2+b_n^4-cdots)$$
    so
    $$z_n+1=z_nleft(1-frac12z_n + frac14z_n^2+ cdotsright)^2 = z_n-z_n^2 + frac34z_n^3 + cdots$$
    from which we get $z_n = n^-1+O(n^-2log n)$ and the asymptotics for $b_n$ follow.



    Incidentally, the sequence $b_n$ is what you get by using Newton's method to find a root of $xe^-x^-2/2$. But I couldn't find a way to make that shed any light on the asymptotics...






    share|cite|improve this answer











    $endgroup$

















      0












      $begingroup$

      Let $b_n=a_n^-1$, so that $b_n+1=(b_n+b_n^-1)^-1$ is the $n$th iterate of $$f(x)=(x+x^-1)^-1=x-x^3+x^5-x^7+cdots$$
      The correct asymptotics have been given elsewhere, but this answer is to point out that there is a general method applicable to any function $f$ analytic at 0 with a series expansion $x+a_kx^k+a_k+1x^k+1+cdots$ with $k>1$ and $a_k<0$: I learned about it in Chapter 8 of de Bruijn's Asymptotic Methods in Analysis, where it is shown that if the starting value is small enough, the $n$th iterate of $f$ is asymptotically equivalent to $((1-k)a_kn)^-1/(k-1)$. In our case, $k=3$ and $a_k=-1$ so $b_n sim (2n)^-1/2$ and $a_n sim (2n)^1/2$.



      A sketch of the proof in the case at hand is as follows. First, show by induction that if $u_n$ is any sequence tending to zero and such that
      $$u_n+1=u_n-u_n^2+O(u_n^3)$$
      then $u_n = n^-1 + O(n^-2log n)$. This is the tricky part of the proof.



      Next make a substitution $z_n= 2b_n^2$. We have
      $$ b_n+1=b_n(1-b_n^2+b_n^4-cdots)$$
      so
      $$z_n+1=z_nleft(1-frac12z_n + frac14z_n^2+ cdotsright)^2 = z_n-z_n^2 + frac34z_n^3 + cdots$$
      from which we get $z_n = n^-1+O(n^-2log n)$ and the asymptotics for $b_n$ follow.



      Incidentally, the sequence $b_n$ is what you get by using Newton's method to find a root of $xe^-x^-2/2$. But I couldn't find a way to make that shed any light on the asymptotics...






      share|cite|improve this answer











      $endgroup$















        0












        0








        0





        $begingroup$

        Let $b_n=a_n^-1$, so that $b_n+1=(b_n+b_n^-1)^-1$ is the $n$th iterate of $$f(x)=(x+x^-1)^-1=x-x^3+x^5-x^7+cdots$$
        The correct asymptotics have been given elsewhere, but this answer is to point out that there is a general method applicable to any function $f$ analytic at 0 with a series expansion $x+a_kx^k+a_k+1x^k+1+cdots$ with $k>1$ and $a_k<0$: I learned about it in Chapter 8 of de Bruijn's Asymptotic Methods in Analysis, where it is shown that if the starting value is small enough, the $n$th iterate of $f$ is asymptotically equivalent to $((1-k)a_kn)^-1/(k-1)$. In our case, $k=3$ and $a_k=-1$ so $b_n sim (2n)^-1/2$ and $a_n sim (2n)^1/2$.



        A sketch of the proof in the case at hand is as follows. First, show by induction that if $u_n$ is any sequence tending to zero and such that
        $$u_n+1=u_n-u_n^2+O(u_n^3)$$
        then $u_n = n^-1 + O(n^-2log n)$. This is the tricky part of the proof.



        Next make a substitution $z_n= 2b_n^2$. We have
        $$ b_n+1=b_n(1-b_n^2+b_n^4-cdots)$$
        so
        $$z_n+1=z_nleft(1-frac12z_n + frac14z_n^2+ cdotsright)^2 = z_n-z_n^2 + frac34z_n^3 + cdots$$
        from which we get $z_n = n^-1+O(n^-2log n)$ and the asymptotics for $b_n$ follow.



        Incidentally, the sequence $b_n$ is what you get by using Newton's method to find a root of $xe^-x^-2/2$. But I couldn't find a way to make that shed any light on the asymptotics...






        share|cite|improve this answer











        $endgroup$



        Let $b_n=a_n^-1$, so that $b_n+1=(b_n+b_n^-1)^-1$ is the $n$th iterate of $$f(x)=(x+x^-1)^-1=x-x^3+x^5-x^7+cdots$$
        The correct asymptotics have been given elsewhere, but this answer is to point out that there is a general method applicable to any function $f$ analytic at 0 with a series expansion $x+a_kx^k+a_k+1x^k+1+cdots$ with $k>1$ and $a_k<0$: I learned about it in Chapter 8 of de Bruijn's Asymptotic Methods in Analysis, where it is shown that if the starting value is small enough, the $n$th iterate of $f$ is asymptotically equivalent to $((1-k)a_kn)^-1/(k-1)$. In our case, $k=3$ and $a_k=-1$ so $b_n sim (2n)^-1/2$ and $a_n sim (2n)^1/2$.



        A sketch of the proof in the case at hand is as follows. First, show by induction that if $u_n$ is any sequence tending to zero and such that
        $$u_n+1=u_n-u_n^2+O(u_n^3)$$
        then $u_n = n^-1 + O(n^-2log n)$. This is the tricky part of the proof.



        Next make a substitution $z_n= 2b_n^2$. We have
        $$ b_n+1=b_n(1-b_n^2+b_n^4-cdots)$$
        so
        $$z_n+1=z_nleft(1-frac12z_n + frac14z_n^2+ cdotsright)^2 = z_n-z_n^2 + frac34z_n^3 + cdots$$
        from which we get $z_n = n^-1+O(n^-2log n)$ and the asymptotics for $b_n$ follow.



        Incidentally, the sequence $b_n$ is what you get by using Newton's method to find a root of $xe^-x^-2/2$. But I couldn't find a way to make that shed any light on the asymptotics...







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Apr 14 '18 at 17:06

























        answered Mar 28 '18 at 18:01









        Matthew TowersMatthew Towers

        7,51622446




        7,51622446



























            draft saved

            draft discarded
















































            Thanks for contributing an answer to Mathematics Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid


            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.

            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f29777%2fclosed-form-for-the-sequence-defined-by-a-0-1-and-a-n1-a-n-a-n-1%23new-answer', 'question_page');

            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            Lowndes Grove History Architecture References Navigation menu32°48′6″N 79°57′58″W / 32.80167°N 79.96611°W / 32.80167; -79.9661132°48′6″N 79°57′58″W / 32.80167°N 79.96611°W / 32.80167; -79.9661178002500"National Register Information System"Historic houses of South Carolina"Lowndes Grove""+32° 48' 6.00", −79° 57' 58.00""Lowndes Grove, Charleston County (260 St. Margaret St., Charleston)""Lowndes Grove"The Charleston ExpositionIt Happened in South Carolina"Lowndes Grove (House), Saint Margaret Street & Sixth Avenue, Charleston, Charleston County, SC(Photographs)"Plantations of the Carolina Low Countrye

            random experiment with two different functions on unit interval Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern)Random variable and probability space notionsRandom Walk with EdgesFinding functions where the increase over a random interval is Poisson distributedNumber of days until dayCan an observed event in fact be of zero probability?Unit random processmodels of coins and uniform distributionHow to get the number of successes given $n$ trials , probability $P$ and a random variable $X$Absorbing Markov chain in a computer. Is “almost every” turned into always convergence in computer executions?Stopped random walk is not uniformly integrable

            How should I support this large drywall patch? Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern) Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?How do I cover large gaps in drywall?How do I keep drywall around a patch from crumbling?Can I glue a second layer of drywall?How to patch long strip on drywall?Large drywall patch: how to avoid bulging seams?Drywall Mesh Patch vs. Bulge? To remove or not to remove?How to fix this drywall job?Prep drywall before backsplashWhat's the best way to fix this horrible drywall patch job?Drywall patching using 3M Patch Plus Primer