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.
$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?
sequences-and-series recurrence-relations closed-form
$endgroup$
|
show 1 more comment
$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?
sequences-and-series recurrence-relations closed-form
$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
|
show 1 more comment
$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?
sequences-and-series recurrence-relations closed-form
$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
sequences-and-series recurrence-relations closed-form
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
|
show 1 more comment
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
|
show 1 more comment
6 Answers
6
active
oldest
votes
$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$
$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
|
show 1 more comment
$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.)
$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
add a comment |
$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...
$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
add a comment |
$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.
$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
|
show 9 more comments
$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).
$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
|
show 1 more comment
$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...
$endgroup$
add a comment |
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
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
$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$
$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
|
show 1 more comment
$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$
$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
|
show 1 more comment
$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$
$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$
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
|
show 1 more comment
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
|
show 1 more comment
$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.)
$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
add a comment |
$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.)
$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
add a comment |
$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.)
$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.)
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
add a comment |
$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
add a comment |
$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...
$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
add a comment |
$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...
$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
add a comment |
$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...
$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...
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
add a comment |
$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
add a comment |
$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.
$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
|
show 9 more comments
$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.
$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
|
show 9 more comments
$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.
$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.
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
|
show 9 more comments
$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
|
show 9 more comments
$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).
$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
|
show 1 more comment
$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).
$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
|
show 1 more comment
$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).
$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).
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
|
show 1 more comment
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
|
show 1 more comment
$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...
$endgroup$
add a comment |
$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...
$endgroup$
add a comment |
$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...
$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...
edited Apr 14 '18 at 17:06
answered Mar 28 '18 at 18:01
Matthew TowersMatthew Towers
7,51622446
7,51622446
add a comment |
add a comment |
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.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
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