prove existence of the limit of a sequence
up vote
3
down vote
favorite
So I have the following problem:
$ x_0 = 1 , x_1 = 2 , $and $x_{n+1} = 2x_n + x_{n-1} $for $ n geq 1.$
Show that: $hspace{2mm} lim_{nto infty} frac{x_n}{x_{n+1}} $ exists.
Then show that the Limit is equal to $sqrt{2}-1$.
For this I thought i could use the fact that $x_n$ is bounded and I thought that it was monotonically falling, but that is not the case, so I ran out of ideas. And I don't know how to calculate the limit... Thank you very much for your help!
sequences-and-series limits
add a comment |
up vote
3
down vote
favorite
So I have the following problem:
$ x_0 = 1 , x_1 = 2 , $and $x_{n+1} = 2x_n + x_{n-1} $for $ n geq 1.$
Show that: $hspace{2mm} lim_{nto infty} frac{x_n}{x_{n+1}} $ exists.
Then show that the Limit is equal to $sqrt{2}-1$.
For this I thought i could use the fact that $x_n$ is bounded and I thought that it was monotonically falling, but that is not the case, so I ran out of ideas. And I don't know how to calculate the limit... Thank you very much for your help!
sequences-and-series limits
Don´t forget to mark an answer as accepted!!! Have a look at your other questions as well. Then your "$textrm{Thank you very much for your help!}$" is more credible.
– callculus
Nov 27 at 21:34
add a comment |
up vote
3
down vote
favorite
up vote
3
down vote
favorite
So I have the following problem:
$ x_0 = 1 , x_1 = 2 , $and $x_{n+1} = 2x_n + x_{n-1} $for $ n geq 1.$
Show that: $hspace{2mm} lim_{nto infty} frac{x_n}{x_{n+1}} $ exists.
Then show that the Limit is equal to $sqrt{2}-1$.
For this I thought i could use the fact that $x_n$ is bounded and I thought that it was monotonically falling, but that is not the case, so I ran out of ideas. And I don't know how to calculate the limit... Thank you very much for your help!
sequences-and-series limits
So I have the following problem:
$ x_0 = 1 , x_1 = 2 , $and $x_{n+1} = 2x_n + x_{n-1} $for $ n geq 1.$
Show that: $hspace{2mm} lim_{nto infty} frac{x_n}{x_{n+1}} $ exists.
Then show that the Limit is equal to $sqrt{2}-1$.
For this I thought i could use the fact that $x_n$ is bounded and I thought that it was monotonically falling, but that is not the case, so I ran out of ideas. And I don't know how to calculate the limit... Thank you very much for your help!
sequences-and-series limits
sequences-and-series limits
edited Nov 26 at 12:04
Tianlalu
2,9901936
2,9901936
asked Nov 26 at 12:03
M-S-R
505
505
Don´t forget to mark an answer as accepted!!! Have a look at your other questions as well. Then your "$textrm{Thank you very much for your help!}$" is more credible.
– callculus
Nov 27 at 21:34
add a comment |
Don´t forget to mark an answer as accepted!!! Have a look at your other questions as well. Then your "$textrm{Thank you very much for your help!}$" is more credible.
– callculus
Nov 27 at 21:34
Don´t forget to mark an answer as accepted!!! Have a look at your other questions as well. Then your "$textrm{Thank you very much for your help!}$" is more credible.
– callculus
Nov 27 at 21:34
Don´t forget to mark an answer as accepted!!! Have a look at your other questions as well. Then your "$textrm{Thank you very much for your help!}$" is more credible.
– callculus
Nov 27 at 21:34
add a comment |
8 Answers
8
active
oldest
votes
up vote
9
down vote
accepted
Without guessing the limit you may proceed as follows:
- Set $q_n = frac{x_n}{x_{n+1}}$
$$Rightarrow x_{n+1} = 2x_n + x_{n-1} Leftrightarrow frac{1}{q_n} = 2+q_{n-1}Leftrightarrow q_n = frac{1}{2+q_{n-1}}$$
Now, it follows
$$|q_{n+1} - q_n| = left|frac{1}{2+q_{n}} - frac{1}{2+q_{n-1}} right| = left|frac{q_{n-1} - q_n}{(color{blue}{2}+q_{n})(color{blue}{2}+q_{n-1})}right|$$ $$< frac{1}{color{blue}{2cdot 2}}left|q_{n-1} - q_{n} right| stackrel{mbox{see below}}{Rightarrow} boxed{(q_n) mbox{ is convergent}}$$
So, we get for the limit
$$L =frac{1}{2+L} Leftrightarrow (L+1)^2=2 stackrel{L>0}{Rightarrow}boxed{L = sqrt{2}-1}$$
Edit after comment:
Additional info concerning the convergence of the sequence:
- $q_{n+1} = q_1 + sum_{k=1}^n(q_{k+1} -q_k)$
- The sums converge (absolutely) as $|q_{k+1} -q_k| < left( frac{1}{4}right)^{k-1}|q_2 - q_1|$ since
- $left|sum_{k=1}^{infty}(q_{k+1} -q_k) right| leq sum_{k=1}^{infty}|q_{k+1} -q_k| < |q_2 - q_1|sum_{k=1}^{infty} left( frac{1}{4}right)^{k-1} < infty$
- As $s_n = sum_{k=1}^n(q_{k+1} -q_k)$ converges, it follows that $q_{n+1} =q_1 + s_n$ converges
I can't understand how you did get the $;<;$ inequality in your center line, and the conclusion that $;q_n;$ is convergent follows but not that immediate: some work there is still due (you can leave it that way but, perhaps, remark that still something must be done)
– DonAntonio
Nov 26 at 12:57
Nice. Now that inequality is clear...since $;q_n;$ is always positive. The deduction that $;q_n;$ is convergent can now be safely left to the OP (inductive argument). +1
– DonAntonio
Nov 26 at 13:14
The Edit is fine, yet something more must, imo, be added: there are sequences $;a_n;$ such that $;|a_{n+1}-a_n|to0;$ yet the limit of the sequence does not exist finitely (i.e., the sequence isn't Cauchy). If you leave the above as it is it could mean like you're doing this...
– DonAntonio
Nov 26 at 13:26
@DonAntonio : Now, the OP has (almost) no work left :-)
– trancelocation
Nov 26 at 13:38
Oh, he does...yet he asked for help, so at least to remind this. Perhaps something like "From this we can deduce the sequence is Cauchy and..."
– DonAntonio
Nov 26 at 13:44
add a comment |
up vote
4
down vote
We have the general term. With it, the existence and the value for the limit are proven.
For some values of $A$ and $B$ we have.
$$x_n=A(1-sqrt{2})^n+B(1+sqrt{2})^n$$
$$L=lim_{nto+infty}dfrac{x_n}{x_{n+1}}=lim_{nto+infty}dfrac{A(1-sqrt{2})^n+B(1+sqrt{2})^n}{A(1-sqrt{2})^{n+1}+B(1+sqrt{2})^{n+1}}$$
$$L=lim_{nto+infty}dfrac{dfrac{A(1-sqrt{2})^n}{(1+sqrt{2})^n}+dfrac{B(1+sqrt{2})^n}{(1+sqrt{2})^n}}{dfrac{A(1-sqrt{2})^{n+1}}{(1+sqrt{2})^n}+dfrac{B(1+sqrt{2})^{n+1}}{(1+sqrt{2})^n}}$$
$$L=dfrac{0+B}{0+B(1+sqrt{2})}=sqrt{2}-1$$
(the $0$'s come from the exponentials with base less that $1$, as they go to zero as the exponent goes to infinity)
No mind what values for $A$ and $B$ we have, so is, the limit is that, irrespective of the values for $x_1$ and $x_2$.
Added
Suppose the sequence has this form $x_n=A·r^n$ and check if it is possible for $r$ and $A$ to meet the conditions the recurrence law imposes:
$A·r^{n+1}=2A·r^n+A·r^{n-1}$ or $A·r^2r^{n-1}=A2·r·r^{n-1}+Ar^{n-1}$
But obviously $Aneq0$ and $rneq0$, so we can simplify and $r$ must satisfy:
$r^2-2r-1=0$ with roots $1-sqrt{2}$ and $1+sqrt{2}$
But the equation is linear, thus a linear combination of solutions is too a solution:
$x_n=A(1-sqrt{2})^n+B(1+sqrt{2})^n$
1
How do you know that $A$ and $B$ (not depending on $n$) exist?
– Kavi Rama Murthy
Nov 26 at 12:27
The linear recurrence laws are always combination of exponentials with the bases the roots of the equation formed with the terms: $r^2-2r-1=0$ in this case.
– Rafa Budría
Nov 26 at 12:31
5
@RafaBudría Kavi, you, and I know that . But it may not be obvious to the question author.
– Martin R
Nov 26 at 12:32
@MartinR I was thinking of that, but my son, in first course in university is said that property. I supposed it known. Anyway, I can suplement my answer.
– Rafa Budría
Nov 26 at 12:34
1
@YadatiKiran. We get $dfrac{1}{1+sqrt{2}}$, but $dfrac{1}{1+sqrt{2}}=dfrac{sqrt{2}-1}{(1+sqrt{2})(sqrt{2}-1)}=dfrac{sqrt{2}-1}{2-1}=sqrt{2}-1$
– Rafa Budría
Nov 26 at 12:55
|
show 1 more comment
up vote
2
down vote
We have $x_n$ to be monotonically increasing and since $dfrac{x_{n+1}}{x_n}=2+dfrac{x_{n-1}}{x_n}$, we can say $dfrac{x_{n+1}}{x_n}<3$ as $dfrac{x_{n-1}}{x_n}<1$ (monotoniclly increasing)$,:forall:ngeq1$. So $x_n$ is convergent.
Let $x_n=Acdot a^n,:aneq0$. The recurrence relation becomes $$ Acdot a^{n+1}=2Acdot a^n+Acdot a^{n-1}implies Acdot a^{n-1}(a^2-2a-1)=0underset{substack{Aneq0\aneq0}}{implies} a^2-2a-1=0$$
By quadratic formula, $a=dfrac{2pmsqrt{4+4}}{2}=1pmsqrt{2}$. Since $x_n$'s are non negative, we have $a=displaystyle lim_{ntoinfty}x_n=1+sqrt{2}$
$rule{17cm}{0.5pt}$
$x_n=A(1+sqrt{2})^n+B(1-sqrt{2})^n$ where $A,B$ are independent of $n$ by linear recurrence.
So if $L=displaystylelim_{ntoinfty}dfrac{x_n}{x_{n+1}}=lim_{ntoinfty}dfrac{A(1+sqrt{2})^n+B(1-sqrt{2})^n}{A(1+sqrt{2})^{n+1}+B(1-sqrt{2})^{n+1}}=lim_{ntoinfty}dfrac{A+dfrac{B(1-sqrt{2})^n}{B(1+sqrt{2})^n}}{dfrac{A(1+sqrt{2})^{n+1}}{(1-sqrt{2})^n}+dfrac{B(1-sqrt{2})^{n+1}}{B(1+sqrt{2})^n}}=dfrac{A}{A(1+sqrt{2})}=sqrt{2}-1$.
$left(text{Since}: |1-sqrt{2}|<1implies displaystylelim_{ntoinfty}(1-sqrt{2})^nto0right)$.
To show that the limit $displaystylelim_{ntoinfty}dfrac{x_n}{x_{n+1}}$ exists we see that it is bounded since $$0<dfrac{x_n}{x_{n+1}}=dfrac{x_n}{2x_{n}+x_{n-1}}leqdfrac{x_n}{2x_{n}}=dfrac12 $$
and $x_{n+1}geq2x_nimplies x_{n+1}geq x_n$ which gives $dfrac{x_n}{x_{n+1}}=dfrac{2x_{n-1}+x_{n-2}}{2x_{n}+x_{n-1}}leqdfrac{2x_{n-1}+x_{n-2}}{2x_{n}}$ i.e.$dfrac{x_n}{x_{n+1}}-dfrac{x_{n-1}}{x_{n}}leqdfrac{x_{n-2}}{2x_{n}}$ which shows monotonicity.Hence the limit exists.
Wrong. The sequence of ratios is not monotonic. $x_1=1$, $x_2=2$, $x_3=5$, $x_4=12$, $x_5=29$ et cetera. Check for yourself that $x_3/x_2$ is larger than $x_4/x_3$ but also $x_5/x_4$ is larger than $x_4/x_3$. Those ratios jump around the limit approaching it from both sides.
– Jyrki Lahtonen
Nov 27 at 4:05
@JyrkiLahtonen: I was talking of the sequence ${x_n}$ not the sequence of ratios. I have tried to show the limit of the sequence ${x_n}$ and then tried to estimate the limit of the sequence of ratios.
– Yadati Kiran
Nov 27 at 4:19
Ok. But $(x_n)$ being monotonic does not imply that $(x_{n-1}/x_n)$ converges. Neither does $(x_n)$, so exactly what are you trying to say in the first paragraph?
– Jyrki Lahtonen
Nov 27 at 4:21
I never said that. I have assumed that the limit exists but yes I agree I have to show it does. The answer is incomplete.
– Yadati Kiran
Nov 27 at 4:25
Ok. I do approve of your solution of actually solving the recurrence. That does provide the rigor (if you show that $Aneq0$). Adding my upvote. IMHO your answer would be better without that first paragraph :-)
– Jyrki Lahtonen
Nov 27 at 4:30
|
show 3 more comments
up vote
1
down vote
One trick is to use the given limit to derive the existence of it.
Write $y_n=frac{x_n}{x_{n+1}}$.
Claim: There exists $rin (0,1)$ such that
$$(sqrt 2-1)-y_nle rbig(y_{n-1}-(sqrt2-1)big).$$
Proof: Rearranging the terms,
begin{align*}
underbrace{frac{x_{n+1}}{x_n}}_{=1/ {y_n}}-1&=underbrace{frac{x_{n-1}}{x_n}}_{=y_{n-1}}+1\
frac 1{y_n}-(sqrt2+1)&=y_{n-1}-(sqrt2-1)\
frac 1{y_n}-frac1{sqrt2-1}&=y_{n-1}-(sqrt2-1)\
(sqrt 2-1)-y_n&=underbrace{y_n(sqrt2-1)}_{in(0,1)}big(y_{n-1}-(sqrt2-1)big).
end{align*}
so the claim is true. $square$
Therefore,
begin{align*}
|y_n-(sqrt2-1)|&le r |y_{n-1}-(sqrt2-1)|le r^2 |y_{n-2}-(sqrt2-1)|lecdots\
&le r^{n}|y_0-(sqrt2-1)|to0,
end{align*}
implies the limit exists, and $limlimits_{ntoinfty}y_n=sqrt2-1$.
add a comment |
up vote
0
down vote
Look at $x_n/x_{n+1} - x_{n-1}/x_n$ which is $(x_n^2 - x_{n-1}x_{n+1})/x_n x_{n-1}$.
We can prove by induction that the numerator is $(-1)^n$.
$$x_{n+1}^2 - x_n x_{n+2}
= x_{n+1}^2 - x_n(2x_{n+1} + x_n)
= x_{n+1}(x_{n+1} - 2x_n) - x_n^2
= -(x_n^2 - x_{n-1}x_{n+1})$$
with $x_1^2 - x_0x_2 = -1$. Hence $x_n/x_{n+1}$ tends to a limit by the alternating series test.
You may want to use frac{}{} to write fractions more clearly.
– DonAntonio
Nov 26 at 12:58
add a comment |
up vote
0
down vote
Since $x_n$ is increasing, all the terms become non-zero. By defining $a_n={x_nover x_{n+1}}$ we have $${x_nover x_{n+1}}={x_nover 2x_n+x_{n-1}}={1over 2+{x_{n-1}over {x_n}}}$$therefore $$a_n={1over 2+{ a_{n-1}}}$$Now by defining $b_n=a_n-(sqrt 2-1)$ we have $$b_n+sqrt 2-1={1over b_{n-1}+sqrt 2+1}$$therefore $$b_n=-sqrt 2+1+{1over b_{n-1}+sqrt 2+1}={(1-sqrt 2)b_{n-1}over a_n+2}$$since $x_n>0$ we have $a_n>0$ therefore$$|b_n|=|{(1-sqrt 2)b_{n-1}over a_n+2}|le {sqrt 2-1over 2}|b_{n-1}|$$which means that $b_n to 0$ or $a_n={x_nover x_{n+1}}to sqrt 2-1 quadblacksquare$
add a comment |
up vote
-1
down vote
We have that
$$frac{x_{n+1}}{x_n} = 2 + frac{x_{n-1}}{x_n}$$
then by
$$y_n=frac{x_{n}}{x_{n-1}} implies y_{n+1}=2+frac1{y_n }quad y_0=2$$
which converges to $L=sqrt 2+1$ and then
$$lim_{nto infty} frac{x_n}{x_{n+1}}=lim_{nto infty} frac{1}{y_{n+1}}=frac1L=sqrt 2 -1$$
1
It seems $y_n$ is 'alternating', i.e. increasing/decreasing when $n$ even and decreasing/increasing when $n$ odd.
– Tianlalu
Nov 26 at 13:08
2
Why $;y_n;$ is increasing and bounded?
– DonAntonio
Nov 26 at 13:10
@DonAntonio Yes I need to clarify that point better! Thanks
– gimusi
Nov 26 at 13:17
add a comment |
up vote
-1
down vote
Let
$$lim_{nto infty} frac{x_n}{x_{n+1}} = lim_{nto infty} frac{x_{n-1}}{x_{n1}} = k$$
Now
$$lim_{nto infty} frac{x_n}{x_{n+1}} = k$$
$$lim_{nto infty} frac{x_n}{2x_{n} + x_{n-1}} = k$$
Take $x_n$ out from numerator and denominator
$$lim_{nto infty} frac{1}{2 + frac{x_{n-1}}{x_n}} = k$$
Using the first equation
$$ frac{1}{2 + k} = k$$
$$k^2+2k-1=0$$
This gives two solutions $k=sqrt{2}-1$ and $k=-sqrt{2}-1$. Since none of the terms can be negative, we reject . the second solution thereby giving us
$$lim_{nto infty} frac{x_n}{x_{n+1}} = k = sqrt2 - 1$$
EDIT - As suggested by the commenter we need to prove that it is a finite limit before we start with the proof. Initially it's a $frac{infty}{infty}$ form as both $x_n$ and $x_{n+1}$ approach $infty$ as $n$ approaches $infty$. I'll use a finite upper bound to show that the limit is finite which means it exists.
For any $n$
$$frac{x_n}{x_{n+1}} =frac{x_n}{2x_n + x_{n-1}}$$
As $x_{n-1}$ is always a positive quantity
$$frac{x_n}{x_{n+1}} leq frac{x_n}{2x_n}$$
$$frac{x_n}{x_{n+1}} leq frac{1}{2}$$
For any $n$, you can take the last statement to prove the monotonicity as
$$x_{n+1}geq x_n$$
And since both $x_n$ and $x_{n+1}$ are positive values, the lower bound is $0$. The upper bound along with lower bound and the monotonicity proves that the limit is finite.
3
This seems to be the less hard part of the question. The hardest part is to prove the limit exists...
– DonAntonio
Nov 26 at 12:22
1
Is there any way to independently do that ?
– Sauhard Sharma
Nov 26 at 12:35
Why can you write the first line? why is the limit of $frac{x_n}{x_{n+1}} = frac{x_{n-1}}{x_n}$ ?
– M-S-R
Nov 26 at 12:54
@SauhardSharma It better is, otherwise your whole answer is invalid as you can use arithmetic of limits only if you know that the limit exists finitely, otherwise you can't. You can try induction, for example, to prove monotonicity or something like that
– DonAntonio
Nov 26 at 13:02
@DonAntonio Thanks for pointing out my mistake. I think the edited proof should suffice
– Sauhard Sharma
Nov 26 at 13:18
|
show 3 more comments
8 Answers
8
active
oldest
votes
8 Answers
8
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
9
down vote
accepted
Without guessing the limit you may proceed as follows:
- Set $q_n = frac{x_n}{x_{n+1}}$
$$Rightarrow x_{n+1} = 2x_n + x_{n-1} Leftrightarrow frac{1}{q_n} = 2+q_{n-1}Leftrightarrow q_n = frac{1}{2+q_{n-1}}$$
Now, it follows
$$|q_{n+1} - q_n| = left|frac{1}{2+q_{n}} - frac{1}{2+q_{n-1}} right| = left|frac{q_{n-1} - q_n}{(color{blue}{2}+q_{n})(color{blue}{2}+q_{n-1})}right|$$ $$< frac{1}{color{blue}{2cdot 2}}left|q_{n-1} - q_{n} right| stackrel{mbox{see below}}{Rightarrow} boxed{(q_n) mbox{ is convergent}}$$
So, we get for the limit
$$L =frac{1}{2+L} Leftrightarrow (L+1)^2=2 stackrel{L>0}{Rightarrow}boxed{L = sqrt{2}-1}$$
Edit after comment:
Additional info concerning the convergence of the sequence:
- $q_{n+1} = q_1 + sum_{k=1}^n(q_{k+1} -q_k)$
- The sums converge (absolutely) as $|q_{k+1} -q_k| < left( frac{1}{4}right)^{k-1}|q_2 - q_1|$ since
- $left|sum_{k=1}^{infty}(q_{k+1} -q_k) right| leq sum_{k=1}^{infty}|q_{k+1} -q_k| < |q_2 - q_1|sum_{k=1}^{infty} left( frac{1}{4}right)^{k-1} < infty$
- As $s_n = sum_{k=1}^n(q_{k+1} -q_k)$ converges, it follows that $q_{n+1} =q_1 + s_n$ converges
I can't understand how you did get the $;<;$ inequality in your center line, and the conclusion that $;q_n;$ is convergent follows but not that immediate: some work there is still due (you can leave it that way but, perhaps, remark that still something must be done)
– DonAntonio
Nov 26 at 12:57
Nice. Now that inequality is clear...since $;q_n;$ is always positive. The deduction that $;q_n;$ is convergent can now be safely left to the OP (inductive argument). +1
– DonAntonio
Nov 26 at 13:14
The Edit is fine, yet something more must, imo, be added: there are sequences $;a_n;$ such that $;|a_{n+1}-a_n|to0;$ yet the limit of the sequence does not exist finitely (i.e., the sequence isn't Cauchy). If you leave the above as it is it could mean like you're doing this...
– DonAntonio
Nov 26 at 13:26
@DonAntonio : Now, the OP has (almost) no work left :-)
– trancelocation
Nov 26 at 13:38
Oh, he does...yet he asked for help, so at least to remind this. Perhaps something like "From this we can deduce the sequence is Cauchy and..."
– DonAntonio
Nov 26 at 13:44
add a comment |
up vote
9
down vote
accepted
Without guessing the limit you may proceed as follows:
- Set $q_n = frac{x_n}{x_{n+1}}$
$$Rightarrow x_{n+1} = 2x_n + x_{n-1} Leftrightarrow frac{1}{q_n} = 2+q_{n-1}Leftrightarrow q_n = frac{1}{2+q_{n-1}}$$
Now, it follows
$$|q_{n+1} - q_n| = left|frac{1}{2+q_{n}} - frac{1}{2+q_{n-1}} right| = left|frac{q_{n-1} - q_n}{(color{blue}{2}+q_{n})(color{blue}{2}+q_{n-1})}right|$$ $$< frac{1}{color{blue}{2cdot 2}}left|q_{n-1} - q_{n} right| stackrel{mbox{see below}}{Rightarrow} boxed{(q_n) mbox{ is convergent}}$$
So, we get for the limit
$$L =frac{1}{2+L} Leftrightarrow (L+1)^2=2 stackrel{L>0}{Rightarrow}boxed{L = sqrt{2}-1}$$
Edit after comment:
Additional info concerning the convergence of the sequence:
- $q_{n+1} = q_1 + sum_{k=1}^n(q_{k+1} -q_k)$
- The sums converge (absolutely) as $|q_{k+1} -q_k| < left( frac{1}{4}right)^{k-1}|q_2 - q_1|$ since
- $left|sum_{k=1}^{infty}(q_{k+1} -q_k) right| leq sum_{k=1}^{infty}|q_{k+1} -q_k| < |q_2 - q_1|sum_{k=1}^{infty} left( frac{1}{4}right)^{k-1} < infty$
- As $s_n = sum_{k=1}^n(q_{k+1} -q_k)$ converges, it follows that $q_{n+1} =q_1 + s_n$ converges
I can't understand how you did get the $;<;$ inequality in your center line, and the conclusion that $;q_n;$ is convergent follows but not that immediate: some work there is still due (you can leave it that way but, perhaps, remark that still something must be done)
– DonAntonio
Nov 26 at 12:57
Nice. Now that inequality is clear...since $;q_n;$ is always positive. The deduction that $;q_n;$ is convergent can now be safely left to the OP (inductive argument). +1
– DonAntonio
Nov 26 at 13:14
The Edit is fine, yet something more must, imo, be added: there are sequences $;a_n;$ such that $;|a_{n+1}-a_n|to0;$ yet the limit of the sequence does not exist finitely (i.e., the sequence isn't Cauchy). If you leave the above as it is it could mean like you're doing this...
– DonAntonio
Nov 26 at 13:26
@DonAntonio : Now, the OP has (almost) no work left :-)
– trancelocation
Nov 26 at 13:38
Oh, he does...yet he asked for help, so at least to remind this. Perhaps something like "From this we can deduce the sequence is Cauchy and..."
– DonAntonio
Nov 26 at 13:44
add a comment |
up vote
9
down vote
accepted
up vote
9
down vote
accepted
Without guessing the limit you may proceed as follows:
- Set $q_n = frac{x_n}{x_{n+1}}$
$$Rightarrow x_{n+1} = 2x_n + x_{n-1} Leftrightarrow frac{1}{q_n} = 2+q_{n-1}Leftrightarrow q_n = frac{1}{2+q_{n-1}}$$
Now, it follows
$$|q_{n+1} - q_n| = left|frac{1}{2+q_{n}} - frac{1}{2+q_{n-1}} right| = left|frac{q_{n-1} - q_n}{(color{blue}{2}+q_{n})(color{blue}{2}+q_{n-1})}right|$$ $$< frac{1}{color{blue}{2cdot 2}}left|q_{n-1} - q_{n} right| stackrel{mbox{see below}}{Rightarrow} boxed{(q_n) mbox{ is convergent}}$$
So, we get for the limit
$$L =frac{1}{2+L} Leftrightarrow (L+1)^2=2 stackrel{L>0}{Rightarrow}boxed{L = sqrt{2}-1}$$
Edit after comment:
Additional info concerning the convergence of the sequence:
- $q_{n+1} = q_1 + sum_{k=1}^n(q_{k+1} -q_k)$
- The sums converge (absolutely) as $|q_{k+1} -q_k| < left( frac{1}{4}right)^{k-1}|q_2 - q_1|$ since
- $left|sum_{k=1}^{infty}(q_{k+1} -q_k) right| leq sum_{k=1}^{infty}|q_{k+1} -q_k| < |q_2 - q_1|sum_{k=1}^{infty} left( frac{1}{4}right)^{k-1} < infty$
- As $s_n = sum_{k=1}^n(q_{k+1} -q_k)$ converges, it follows that $q_{n+1} =q_1 + s_n$ converges
Without guessing the limit you may proceed as follows:
- Set $q_n = frac{x_n}{x_{n+1}}$
$$Rightarrow x_{n+1} = 2x_n + x_{n-1} Leftrightarrow frac{1}{q_n} = 2+q_{n-1}Leftrightarrow q_n = frac{1}{2+q_{n-1}}$$
Now, it follows
$$|q_{n+1} - q_n| = left|frac{1}{2+q_{n}} - frac{1}{2+q_{n-1}} right| = left|frac{q_{n-1} - q_n}{(color{blue}{2}+q_{n})(color{blue}{2}+q_{n-1})}right|$$ $$< frac{1}{color{blue}{2cdot 2}}left|q_{n-1} - q_{n} right| stackrel{mbox{see below}}{Rightarrow} boxed{(q_n) mbox{ is convergent}}$$
So, we get for the limit
$$L =frac{1}{2+L} Leftrightarrow (L+1)^2=2 stackrel{L>0}{Rightarrow}boxed{L = sqrt{2}-1}$$
Edit after comment:
Additional info concerning the convergence of the sequence:
- $q_{n+1} = q_1 + sum_{k=1}^n(q_{k+1} -q_k)$
- The sums converge (absolutely) as $|q_{k+1} -q_k| < left( frac{1}{4}right)^{k-1}|q_2 - q_1|$ since
- $left|sum_{k=1}^{infty}(q_{k+1} -q_k) right| leq sum_{k=1}^{infty}|q_{k+1} -q_k| < |q_2 - q_1|sum_{k=1}^{infty} left( frac{1}{4}right)^{k-1} < infty$
- As $s_n = sum_{k=1}^n(q_{k+1} -q_k)$ converges, it follows that $q_{n+1} =q_1 + s_n$ converges
edited Nov 26 at 13:36
answered Nov 26 at 12:44
trancelocation
8,7571521
8,7571521
I can't understand how you did get the $;<;$ inequality in your center line, and the conclusion that $;q_n;$ is convergent follows but not that immediate: some work there is still due (you can leave it that way but, perhaps, remark that still something must be done)
– DonAntonio
Nov 26 at 12:57
Nice. Now that inequality is clear...since $;q_n;$ is always positive. The deduction that $;q_n;$ is convergent can now be safely left to the OP (inductive argument). +1
– DonAntonio
Nov 26 at 13:14
The Edit is fine, yet something more must, imo, be added: there are sequences $;a_n;$ such that $;|a_{n+1}-a_n|to0;$ yet the limit of the sequence does not exist finitely (i.e., the sequence isn't Cauchy). If you leave the above as it is it could mean like you're doing this...
– DonAntonio
Nov 26 at 13:26
@DonAntonio : Now, the OP has (almost) no work left :-)
– trancelocation
Nov 26 at 13:38
Oh, he does...yet he asked for help, so at least to remind this. Perhaps something like "From this we can deduce the sequence is Cauchy and..."
– DonAntonio
Nov 26 at 13:44
add a comment |
I can't understand how you did get the $;<;$ inequality in your center line, and the conclusion that $;q_n;$ is convergent follows but not that immediate: some work there is still due (you can leave it that way but, perhaps, remark that still something must be done)
– DonAntonio
Nov 26 at 12:57
Nice. Now that inequality is clear...since $;q_n;$ is always positive. The deduction that $;q_n;$ is convergent can now be safely left to the OP (inductive argument). +1
– DonAntonio
Nov 26 at 13:14
The Edit is fine, yet something more must, imo, be added: there are sequences $;a_n;$ such that $;|a_{n+1}-a_n|to0;$ yet the limit of the sequence does not exist finitely (i.e., the sequence isn't Cauchy). If you leave the above as it is it could mean like you're doing this...
– DonAntonio
Nov 26 at 13:26
@DonAntonio : Now, the OP has (almost) no work left :-)
– trancelocation
Nov 26 at 13:38
Oh, he does...yet he asked for help, so at least to remind this. Perhaps something like "From this we can deduce the sequence is Cauchy and..."
– DonAntonio
Nov 26 at 13:44
I can't understand how you did get the $;<;$ inequality in your center line, and the conclusion that $;q_n;$ is convergent follows but not that immediate: some work there is still due (you can leave it that way but, perhaps, remark that still something must be done)
– DonAntonio
Nov 26 at 12:57
I can't understand how you did get the $;<;$ inequality in your center line, and the conclusion that $;q_n;$ is convergent follows but not that immediate: some work there is still due (you can leave it that way but, perhaps, remark that still something must be done)
– DonAntonio
Nov 26 at 12:57
Nice. Now that inequality is clear...since $;q_n;$ is always positive. The deduction that $;q_n;$ is convergent can now be safely left to the OP (inductive argument). +1
– DonAntonio
Nov 26 at 13:14
Nice. Now that inequality is clear...since $;q_n;$ is always positive. The deduction that $;q_n;$ is convergent can now be safely left to the OP (inductive argument). +1
– DonAntonio
Nov 26 at 13:14
The Edit is fine, yet something more must, imo, be added: there are sequences $;a_n;$ such that $;|a_{n+1}-a_n|to0;$ yet the limit of the sequence does not exist finitely (i.e., the sequence isn't Cauchy). If you leave the above as it is it could mean like you're doing this...
– DonAntonio
Nov 26 at 13:26
The Edit is fine, yet something more must, imo, be added: there are sequences $;a_n;$ such that $;|a_{n+1}-a_n|to0;$ yet the limit of the sequence does not exist finitely (i.e., the sequence isn't Cauchy). If you leave the above as it is it could mean like you're doing this...
– DonAntonio
Nov 26 at 13:26
@DonAntonio : Now, the OP has (almost) no work left :-)
– trancelocation
Nov 26 at 13:38
@DonAntonio : Now, the OP has (almost) no work left :-)
– trancelocation
Nov 26 at 13:38
Oh, he does...yet he asked for help, so at least to remind this. Perhaps something like "From this we can deduce the sequence is Cauchy and..."
– DonAntonio
Nov 26 at 13:44
Oh, he does...yet he asked for help, so at least to remind this. Perhaps something like "From this we can deduce the sequence is Cauchy and..."
– DonAntonio
Nov 26 at 13:44
add a comment |
up vote
4
down vote
We have the general term. With it, the existence and the value for the limit are proven.
For some values of $A$ and $B$ we have.
$$x_n=A(1-sqrt{2})^n+B(1+sqrt{2})^n$$
$$L=lim_{nto+infty}dfrac{x_n}{x_{n+1}}=lim_{nto+infty}dfrac{A(1-sqrt{2})^n+B(1+sqrt{2})^n}{A(1-sqrt{2})^{n+1}+B(1+sqrt{2})^{n+1}}$$
$$L=lim_{nto+infty}dfrac{dfrac{A(1-sqrt{2})^n}{(1+sqrt{2})^n}+dfrac{B(1+sqrt{2})^n}{(1+sqrt{2})^n}}{dfrac{A(1-sqrt{2})^{n+1}}{(1+sqrt{2})^n}+dfrac{B(1+sqrt{2})^{n+1}}{(1+sqrt{2})^n}}$$
$$L=dfrac{0+B}{0+B(1+sqrt{2})}=sqrt{2}-1$$
(the $0$'s come from the exponentials with base less that $1$, as they go to zero as the exponent goes to infinity)
No mind what values for $A$ and $B$ we have, so is, the limit is that, irrespective of the values for $x_1$ and $x_2$.
Added
Suppose the sequence has this form $x_n=A·r^n$ and check if it is possible for $r$ and $A$ to meet the conditions the recurrence law imposes:
$A·r^{n+1}=2A·r^n+A·r^{n-1}$ or $A·r^2r^{n-1}=A2·r·r^{n-1}+Ar^{n-1}$
But obviously $Aneq0$ and $rneq0$, so we can simplify and $r$ must satisfy:
$r^2-2r-1=0$ with roots $1-sqrt{2}$ and $1+sqrt{2}$
But the equation is linear, thus a linear combination of solutions is too a solution:
$x_n=A(1-sqrt{2})^n+B(1+sqrt{2})^n$
1
How do you know that $A$ and $B$ (not depending on $n$) exist?
– Kavi Rama Murthy
Nov 26 at 12:27
The linear recurrence laws are always combination of exponentials with the bases the roots of the equation formed with the terms: $r^2-2r-1=0$ in this case.
– Rafa Budría
Nov 26 at 12:31
5
@RafaBudría Kavi, you, and I know that . But it may not be obvious to the question author.
– Martin R
Nov 26 at 12:32
@MartinR I was thinking of that, but my son, in first course in university is said that property. I supposed it known. Anyway, I can suplement my answer.
– Rafa Budría
Nov 26 at 12:34
1
@YadatiKiran. We get $dfrac{1}{1+sqrt{2}}$, but $dfrac{1}{1+sqrt{2}}=dfrac{sqrt{2}-1}{(1+sqrt{2})(sqrt{2}-1)}=dfrac{sqrt{2}-1}{2-1}=sqrt{2}-1$
– Rafa Budría
Nov 26 at 12:55
|
show 1 more comment
up vote
4
down vote
We have the general term. With it, the existence and the value for the limit are proven.
For some values of $A$ and $B$ we have.
$$x_n=A(1-sqrt{2})^n+B(1+sqrt{2})^n$$
$$L=lim_{nto+infty}dfrac{x_n}{x_{n+1}}=lim_{nto+infty}dfrac{A(1-sqrt{2})^n+B(1+sqrt{2})^n}{A(1-sqrt{2})^{n+1}+B(1+sqrt{2})^{n+1}}$$
$$L=lim_{nto+infty}dfrac{dfrac{A(1-sqrt{2})^n}{(1+sqrt{2})^n}+dfrac{B(1+sqrt{2})^n}{(1+sqrt{2})^n}}{dfrac{A(1-sqrt{2})^{n+1}}{(1+sqrt{2})^n}+dfrac{B(1+sqrt{2})^{n+1}}{(1+sqrt{2})^n}}$$
$$L=dfrac{0+B}{0+B(1+sqrt{2})}=sqrt{2}-1$$
(the $0$'s come from the exponentials with base less that $1$, as they go to zero as the exponent goes to infinity)
No mind what values for $A$ and $B$ we have, so is, the limit is that, irrespective of the values for $x_1$ and $x_2$.
Added
Suppose the sequence has this form $x_n=A·r^n$ and check if it is possible for $r$ and $A$ to meet the conditions the recurrence law imposes:
$A·r^{n+1}=2A·r^n+A·r^{n-1}$ or $A·r^2r^{n-1}=A2·r·r^{n-1}+Ar^{n-1}$
But obviously $Aneq0$ and $rneq0$, so we can simplify and $r$ must satisfy:
$r^2-2r-1=0$ with roots $1-sqrt{2}$ and $1+sqrt{2}$
But the equation is linear, thus a linear combination of solutions is too a solution:
$x_n=A(1-sqrt{2})^n+B(1+sqrt{2})^n$
1
How do you know that $A$ and $B$ (not depending on $n$) exist?
– Kavi Rama Murthy
Nov 26 at 12:27
The linear recurrence laws are always combination of exponentials with the bases the roots of the equation formed with the terms: $r^2-2r-1=0$ in this case.
– Rafa Budría
Nov 26 at 12:31
5
@RafaBudría Kavi, you, and I know that . But it may not be obvious to the question author.
– Martin R
Nov 26 at 12:32
@MartinR I was thinking of that, but my son, in first course in university is said that property. I supposed it known. Anyway, I can suplement my answer.
– Rafa Budría
Nov 26 at 12:34
1
@YadatiKiran. We get $dfrac{1}{1+sqrt{2}}$, but $dfrac{1}{1+sqrt{2}}=dfrac{sqrt{2}-1}{(1+sqrt{2})(sqrt{2}-1)}=dfrac{sqrt{2}-1}{2-1}=sqrt{2}-1$
– Rafa Budría
Nov 26 at 12:55
|
show 1 more comment
up vote
4
down vote
up vote
4
down vote
We have the general term. With it, the existence and the value for the limit are proven.
For some values of $A$ and $B$ we have.
$$x_n=A(1-sqrt{2})^n+B(1+sqrt{2})^n$$
$$L=lim_{nto+infty}dfrac{x_n}{x_{n+1}}=lim_{nto+infty}dfrac{A(1-sqrt{2})^n+B(1+sqrt{2})^n}{A(1-sqrt{2})^{n+1}+B(1+sqrt{2})^{n+1}}$$
$$L=lim_{nto+infty}dfrac{dfrac{A(1-sqrt{2})^n}{(1+sqrt{2})^n}+dfrac{B(1+sqrt{2})^n}{(1+sqrt{2})^n}}{dfrac{A(1-sqrt{2})^{n+1}}{(1+sqrt{2})^n}+dfrac{B(1+sqrt{2})^{n+1}}{(1+sqrt{2})^n}}$$
$$L=dfrac{0+B}{0+B(1+sqrt{2})}=sqrt{2}-1$$
(the $0$'s come from the exponentials with base less that $1$, as they go to zero as the exponent goes to infinity)
No mind what values for $A$ and $B$ we have, so is, the limit is that, irrespective of the values for $x_1$ and $x_2$.
Added
Suppose the sequence has this form $x_n=A·r^n$ and check if it is possible for $r$ and $A$ to meet the conditions the recurrence law imposes:
$A·r^{n+1}=2A·r^n+A·r^{n-1}$ or $A·r^2r^{n-1}=A2·r·r^{n-1}+Ar^{n-1}$
But obviously $Aneq0$ and $rneq0$, so we can simplify and $r$ must satisfy:
$r^2-2r-1=0$ with roots $1-sqrt{2}$ and $1+sqrt{2}$
But the equation is linear, thus a linear combination of solutions is too a solution:
$x_n=A(1-sqrt{2})^n+B(1+sqrt{2})^n$
We have the general term. With it, the existence and the value for the limit are proven.
For some values of $A$ and $B$ we have.
$$x_n=A(1-sqrt{2})^n+B(1+sqrt{2})^n$$
$$L=lim_{nto+infty}dfrac{x_n}{x_{n+1}}=lim_{nto+infty}dfrac{A(1-sqrt{2})^n+B(1+sqrt{2})^n}{A(1-sqrt{2})^{n+1}+B(1+sqrt{2})^{n+1}}$$
$$L=lim_{nto+infty}dfrac{dfrac{A(1-sqrt{2})^n}{(1+sqrt{2})^n}+dfrac{B(1+sqrt{2})^n}{(1+sqrt{2})^n}}{dfrac{A(1-sqrt{2})^{n+1}}{(1+sqrt{2})^n}+dfrac{B(1+sqrt{2})^{n+1}}{(1+sqrt{2})^n}}$$
$$L=dfrac{0+B}{0+B(1+sqrt{2})}=sqrt{2}-1$$
(the $0$'s come from the exponentials with base less that $1$, as they go to zero as the exponent goes to infinity)
No mind what values for $A$ and $B$ we have, so is, the limit is that, irrespective of the values for $x_1$ and $x_2$.
Added
Suppose the sequence has this form $x_n=A·r^n$ and check if it is possible for $r$ and $A$ to meet the conditions the recurrence law imposes:
$A·r^{n+1}=2A·r^n+A·r^{n-1}$ or $A·r^2r^{n-1}=A2·r·r^{n-1}+Ar^{n-1}$
But obviously $Aneq0$ and $rneq0$, so we can simplify and $r$ must satisfy:
$r^2-2r-1=0$ with roots $1-sqrt{2}$ and $1+sqrt{2}$
But the equation is linear, thus a linear combination of solutions is too a solution:
$x_n=A(1-sqrt{2})^n+B(1+sqrt{2})^n$
edited Nov 26 at 12:47
answered Nov 26 at 12:24
Rafa Budría
5,4151825
5,4151825
1
How do you know that $A$ and $B$ (not depending on $n$) exist?
– Kavi Rama Murthy
Nov 26 at 12:27
The linear recurrence laws are always combination of exponentials with the bases the roots of the equation formed with the terms: $r^2-2r-1=0$ in this case.
– Rafa Budría
Nov 26 at 12:31
5
@RafaBudría Kavi, you, and I know that . But it may not be obvious to the question author.
– Martin R
Nov 26 at 12:32
@MartinR I was thinking of that, but my son, in first course in university is said that property. I supposed it known. Anyway, I can suplement my answer.
– Rafa Budría
Nov 26 at 12:34
1
@YadatiKiran. We get $dfrac{1}{1+sqrt{2}}$, but $dfrac{1}{1+sqrt{2}}=dfrac{sqrt{2}-1}{(1+sqrt{2})(sqrt{2}-1)}=dfrac{sqrt{2}-1}{2-1}=sqrt{2}-1$
– Rafa Budría
Nov 26 at 12:55
|
show 1 more comment
1
How do you know that $A$ and $B$ (not depending on $n$) exist?
– Kavi Rama Murthy
Nov 26 at 12:27
The linear recurrence laws are always combination of exponentials with the bases the roots of the equation formed with the terms: $r^2-2r-1=0$ in this case.
– Rafa Budría
Nov 26 at 12:31
5
@RafaBudría Kavi, you, and I know that . But it may not be obvious to the question author.
– Martin R
Nov 26 at 12:32
@MartinR I was thinking of that, but my son, in first course in university is said that property. I supposed it known. Anyway, I can suplement my answer.
– Rafa Budría
Nov 26 at 12:34
1
@YadatiKiran. We get $dfrac{1}{1+sqrt{2}}$, but $dfrac{1}{1+sqrt{2}}=dfrac{sqrt{2}-1}{(1+sqrt{2})(sqrt{2}-1)}=dfrac{sqrt{2}-1}{2-1}=sqrt{2}-1$
– Rafa Budría
Nov 26 at 12:55
1
1
How do you know that $A$ and $B$ (not depending on $n$) exist?
– Kavi Rama Murthy
Nov 26 at 12:27
How do you know that $A$ and $B$ (not depending on $n$) exist?
– Kavi Rama Murthy
Nov 26 at 12:27
The linear recurrence laws are always combination of exponentials with the bases the roots of the equation formed with the terms: $r^2-2r-1=0$ in this case.
– Rafa Budría
Nov 26 at 12:31
The linear recurrence laws are always combination of exponentials with the bases the roots of the equation formed with the terms: $r^2-2r-1=0$ in this case.
– Rafa Budría
Nov 26 at 12:31
5
5
@RafaBudría Kavi, you, and I know that . But it may not be obvious to the question author.
– Martin R
Nov 26 at 12:32
@RafaBudría Kavi, you, and I know that . But it may not be obvious to the question author.
– Martin R
Nov 26 at 12:32
@MartinR I was thinking of that, but my son, in first course in university is said that property. I supposed it known. Anyway, I can suplement my answer.
– Rafa Budría
Nov 26 at 12:34
@MartinR I was thinking of that, but my son, in first course in university is said that property. I supposed it known. Anyway, I can suplement my answer.
– Rafa Budría
Nov 26 at 12:34
1
1
@YadatiKiran. We get $dfrac{1}{1+sqrt{2}}$, but $dfrac{1}{1+sqrt{2}}=dfrac{sqrt{2}-1}{(1+sqrt{2})(sqrt{2}-1)}=dfrac{sqrt{2}-1}{2-1}=sqrt{2}-1$
– Rafa Budría
Nov 26 at 12:55
@YadatiKiran. We get $dfrac{1}{1+sqrt{2}}$, but $dfrac{1}{1+sqrt{2}}=dfrac{sqrt{2}-1}{(1+sqrt{2})(sqrt{2}-1)}=dfrac{sqrt{2}-1}{2-1}=sqrt{2}-1$
– Rafa Budría
Nov 26 at 12:55
|
show 1 more comment
up vote
2
down vote
We have $x_n$ to be monotonically increasing and since $dfrac{x_{n+1}}{x_n}=2+dfrac{x_{n-1}}{x_n}$, we can say $dfrac{x_{n+1}}{x_n}<3$ as $dfrac{x_{n-1}}{x_n}<1$ (monotoniclly increasing)$,:forall:ngeq1$. So $x_n$ is convergent.
Let $x_n=Acdot a^n,:aneq0$. The recurrence relation becomes $$ Acdot a^{n+1}=2Acdot a^n+Acdot a^{n-1}implies Acdot a^{n-1}(a^2-2a-1)=0underset{substack{Aneq0\aneq0}}{implies} a^2-2a-1=0$$
By quadratic formula, $a=dfrac{2pmsqrt{4+4}}{2}=1pmsqrt{2}$. Since $x_n$'s are non negative, we have $a=displaystyle lim_{ntoinfty}x_n=1+sqrt{2}$
$rule{17cm}{0.5pt}$
$x_n=A(1+sqrt{2})^n+B(1-sqrt{2})^n$ where $A,B$ are independent of $n$ by linear recurrence.
So if $L=displaystylelim_{ntoinfty}dfrac{x_n}{x_{n+1}}=lim_{ntoinfty}dfrac{A(1+sqrt{2})^n+B(1-sqrt{2})^n}{A(1+sqrt{2})^{n+1}+B(1-sqrt{2})^{n+1}}=lim_{ntoinfty}dfrac{A+dfrac{B(1-sqrt{2})^n}{B(1+sqrt{2})^n}}{dfrac{A(1+sqrt{2})^{n+1}}{(1-sqrt{2})^n}+dfrac{B(1-sqrt{2})^{n+1}}{B(1+sqrt{2})^n}}=dfrac{A}{A(1+sqrt{2})}=sqrt{2}-1$.
$left(text{Since}: |1-sqrt{2}|<1implies displaystylelim_{ntoinfty}(1-sqrt{2})^nto0right)$.
To show that the limit $displaystylelim_{ntoinfty}dfrac{x_n}{x_{n+1}}$ exists we see that it is bounded since $$0<dfrac{x_n}{x_{n+1}}=dfrac{x_n}{2x_{n}+x_{n-1}}leqdfrac{x_n}{2x_{n}}=dfrac12 $$
and $x_{n+1}geq2x_nimplies x_{n+1}geq x_n$ which gives $dfrac{x_n}{x_{n+1}}=dfrac{2x_{n-1}+x_{n-2}}{2x_{n}+x_{n-1}}leqdfrac{2x_{n-1}+x_{n-2}}{2x_{n}}$ i.e.$dfrac{x_n}{x_{n+1}}-dfrac{x_{n-1}}{x_{n}}leqdfrac{x_{n-2}}{2x_{n}}$ which shows monotonicity.Hence the limit exists.
Wrong. The sequence of ratios is not monotonic. $x_1=1$, $x_2=2$, $x_3=5$, $x_4=12$, $x_5=29$ et cetera. Check for yourself that $x_3/x_2$ is larger than $x_4/x_3$ but also $x_5/x_4$ is larger than $x_4/x_3$. Those ratios jump around the limit approaching it from both sides.
– Jyrki Lahtonen
Nov 27 at 4:05
@JyrkiLahtonen: I was talking of the sequence ${x_n}$ not the sequence of ratios. I have tried to show the limit of the sequence ${x_n}$ and then tried to estimate the limit of the sequence of ratios.
– Yadati Kiran
Nov 27 at 4:19
Ok. But $(x_n)$ being monotonic does not imply that $(x_{n-1}/x_n)$ converges. Neither does $(x_n)$, so exactly what are you trying to say in the first paragraph?
– Jyrki Lahtonen
Nov 27 at 4:21
I never said that. I have assumed that the limit exists but yes I agree I have to show it does. The answer is incomplete.
– Yadati Kiran
Nov 27 at 4:25
Ok. I do approve of your solution of actually solving the recurrence. That does provide the rigor (if you show that $Aneq0$). Adding my upvote. IMHO your answer would be better without that first paragraph :-)
– Jyrki Lahtonen
Nov 27 at 4:30
|
show 3 more comments
up vote
2
down vote
We have $x_n$ to be monotonically increasing and since $dfrac{x_{n+1}}{x_n}=2+dfrac{x_{n-1}}{x_n}$, we can say $dfrac{x_{n+1}}{x_n}<3$ as $dfrac{x_{n-1}}{x_n}<1$ (monotoniclly increasing)$,:forall:ngeq1$. So $x_n$ is convergent.
Let $x_n=Acdot a^n,:aneq0$. The recurrence relation becomes $$ Acdot a^{n+1}=2Acdot a^n+Acdot a^{n-1}implies Acdot a^{n-1}(a^2-2a-1)=0underset{substack{Aneq0\aneq0}}{implies} a^2-2a-1=0$$
By quadratic formula, $a=dfrac{2pmsqrt{4+4}}{2}=1pmsqrt{2}$. Since $x_n$'s are non negative, we have $a=displaystyle lim_{ntoinfty}x_n=1+sqrt{2}$
$rule{17cm}{0.5pt}$
$x_n=A(1+sqrt{2})^n+B(1-sqrt{2})^n$ where $A,B$ are independent of $n$ by linear recurrence.
So if $L=displaystylelim_{ntoinfty}dfrac{x_n}{x_{n+1}}=lim_{ntoinfty}dfrac{A(1+sqrt{2})^n+B(1-sqrt{2})^n}{A(1+sqrt{2})^{n+1}+B(1-sqrt{2})^{n+1}}=lim_{ntoinfty}dfrac{A+dfrac{B(1-sqrt{2})^n}{B(1+sqrt{2})^n}}{dfrac{A(1+sqrt{2})^{n+1}}{(1-sqrt{2})^n}+dfrac{B(1-sqrt{2})^{n+1}}{B(1+sqrt{2})^n}}=dfrac{A}{A(1+sqrt{2})}=sqrt{2}-1$.
$left(text{Since}: |1-sqrt{2}|<1implies displaystylelim_{ntoinfty}(1-sqrt{2})^nto0right)$.
To show that the limit $displaystylelim_{ntoinfty}dfrac{x_n}{x_{n+1}}$ exists we see that it is bounded since $$0<dfrac{x_n}{x_{n+1}}=dfrac{x_n}{2x_{n}+x_{n-1}}leqdfrac{x_n}{2x_{n}}=dfrac12 $$
and $x_{n+1}geq2x_nimplies x_{n+1}geq x_n$ which gives $dfrac{x_n}{x_{n+1}}=dfrac{2x_{n-1}+x_{n-2}}{2x_{n}+x_{n-1}}leqdfrac{2x_{n-1}+x_{n-2}}{2x_{n}}$ i.e.$dfrac{x_n}{x_{n+1}}-dfrac{x_{n-1}}{x_{n}}leqdfrac{x_{n-2}}{2x_{n}}$ which shows monotonicity.Hence the limit exists.
Wrong. The sequence of ratios is not monotonic. $x_1=1$, $x_2=2$, $x_3=5$, $x_4=12$, $x_5=29$ et cetera. Check for yourself that $x_3/x_2$ is larger than $x_4/x_3$ but also $x_5/x_4$ is larger than $x_4/x_3$. Those ratios jump around the limit approaching it from both sides.
– Jyrki Lahtonen
Nov 27 at 4:05
@JyrkiLahtonen: I was talking of the sequence ${x_n}$ not the sequence of ratios. I have tried to show the limit of the sequence ${x_n}$ and then tried to estimate the limit of the sequence of ratios.
– Yadati Kiran
Nov 27 at 4:19
Ok. But $(x_n)$ being monotonic does not imply that $(x_{n-1}/x_n)$ converges. Neither does $(x_n)$, so exactly what are you trying to say in the first paragraph?
– Jyrki Lahtonen
Nov 27 at 4:21
I never said that. I have assumed that the limit exists but yes I agree I have to show it does. The answer is incomplete.
– Yadati Kiran
Nov 27 at 4:25
Ok. I do approve of your solution of actually solving the recurrence. That does provide the rigor (if you show that $Aneq0$). Adding my upvote. IMHO your answer would be better without that first paragraph :-)
– Jyrki Lahtonen
Nov 27 at 4:30
|
show 3 more comments
up vote
2
down vote
up vote
2
down vote
We have $x_n$ to be monotonically increasing and since $dfrac{x_{n+1}}{x_n}=2+dfrac{x_{n-1}}{x_n}$, we can say $dfrac{x_{n+1}}{x_n}<3$ as $dfrac{x_{n-1}}{x_n}<1$ (monotoniclly increasing)$,:forall:ngeq1$. So $x_n$ is convergent.
Let $x_n=Acdot a^n,:aneq0$. The recurrence relation becomes $$ Acdot a^{n+1}=2Acdot a^n+Acdot a^{n-1}implies Acdot a^{n-1}(a^2-2a-1)=0underset{substack{Aneq0\aneq0}}{implies} a^2-2a-1=0$$
By quadratic formula, $a=dfrac{2pmsqrt{4+4}}{2}=1pmsqrt{2}$. Since $x_n$'s are non negative, we have $a=displaystyle lim_{ntoinfty}x_n=1+sqrt{2}$
$rule{17cm}{0.5pt}$
$x_n=A(1+sqrt{2})^n+B(1-sqrt{2})^n$ where $A,B$ are independent of $n$ by linear recurrence.
So if $L=displaystylelim_{ntoinfty}dfrac{x_n}{x_{n+1}}=lim_{ntoinfty}dfrac{A(1+sqrt{2})^n+B(1-sqrt{2})^n}{A(1+sqrt{2})^{n+1}+B(1-sqrt{2})^{n+1}}=lim_{ntoinfty}dfrac{A+dfrac{B(1-sqrt{2})^n}{B(1+sqrt{2})^n}}{dfrac{A(1+sqrt{2})^{n+1}}{(1-sqrt{2})^n}+dfrac{B(1-sqrt{2})^{n+1}}{B(1+sqrt{2})^n}}=dfrac{A}{A(1+sqrt{2})}=sqrt{2}-1$.
$left(text{Since}: |1-sqrt{2}|<1implies displaystylelim_{ntoinfty}(1-sqrt{2})^nto0right)$.
To show that the limit $displaystylelim_{ntoinfty}dfrac{x_n}{x_{n+1}}$ exists we see that it is bounded since $$0<dfrac{x_n}{x_{n+1}}=dfrac{x_n}{2x_{n}+x_{n-1}}leqdfrac{x_n}{2x_{n}}=dfrac12 $$
and $x_{n+1}geq2x_nimplies x_{n+1}geq x_n$ which gives $dfrac{x_n}{x_{n+1}}=dfrac{2x_{n-1}+x_{n-2}}{2x_{n}+x_{n-1}}leqdfrac{2x_{n-1}+x_{n-2}}{2x_{n}}$ i.e.$dfrac{x_n}{x_{n+1}}-dfrac{x_{n-1}}{x_{n}}leqdfrac{x_{n-2}}{2x_{n}}$ which shows monotonicity.Hence the limit exists.
We have $x_n$ to be monotonically increasing and since $dfrac{x_{n+1}}{x_n}=2+dfrac{x_{n-1}}{x_n}$, we can say $dfrac{x_{n+1}}{x_n}<3$ as $dfrac{x_{n-1}}{x_n}<1$ (monotoniclly increasing)$,:forall:ngeq1$. So $x_n$ is convergent.
Let $x_n=Acdot a^n,:aneq0$. The recurrence relation becomes $$ Acdot a^{n+1}=2Acdot a^n+Acdot a^{n-1}implies Acdot a^{n-1}(a^2-2a-1)=0underset{substack{Aneq0\aneq0}}{implies} a^2-2a-1=0$$
By quadratic formula, $a=dfrac{2pmsqrt{4+4}}{2}=1pmsqrt{2}$. Since $x_n$'s are non negative, we have $a=displaystyle lim_{ntoinfty}x_n=1+sqrt{2}$
$rule{17cm}{0.5pt}$
$x_n=A(1+sqrt{2})^n+B(1-sqrt{2})^n$ where $A,B$ are independent of $n$ by linear recurrence.
So if $L=displaystylelim_{ntoinfty}dfrac{x_n}{x_{n+1}}=lim_{ntoinfty}dfrac{A(1+sqrt{2})^n+B(1-sqrt{2})^n}{A(1+sqrt{2})^{n+1}+B(1-sqrt{2})^{n+1}}=lim_{ntoinfty}dfrac{A+dfrac{B(1-sqrt{2})^n}{B(1+sqrt{2})^n}}{dfrac{A(1+sqrt{2})^{n+1}}{(1-sqrt{2})^n}+dfrac{B(1-sqrt{2})^{n+1}}{B(1+sqrt{2})^n}}=dfrac{A}{A(1+sqrt{2})}=sqrt{2}-1$.
$left(text{Since}: |1-sqrt{2}|<1implies displaystylelim_{ntoinfty}(1-sqrt{2})^nto0right)$.
To show that the limit $displaystylelim_{ntoinfty}dfrac{x_n}{x_{n+1}}$ exists we see that it is bounded since $$0<dfrac{x_n}{x_{n+1}}=dfrac{x_n}{2x_{n}+x_{n-1}}leqdfrac{x_n}{2x_{n}}=dfrac12 $$
and $x_{n+1}geq2x_nimplies x_{n+1}geq x_n$ which gives $dfrac{x_n}{x_{n+1}}=dfrac{2x_{n-1}+x_{n-2}}{2x_{n}+x_{n-1}}leqdfrac{2x_{n-1}+x_{n-2}}{2x_{n}}$ i.e.$dfrac{x_n}{x_{n+1}}-dfrac{x_{n-1}}{x_{n}}leqdfrac{x_{n-2}}{2x_{n}}$ which shows monotonicity.Hence the limit exists.
edited Nov 27 at 5:11
answered Nov 26 at 12:43
Yadati Kiran
1,259417
1,259417
Wrong. The sequence of ratios is not monotonic. $x_1=1$, $x_2=2$, $x_3=5$, $x_4=12$, $x_5=29$ et cetera. Check for yourself that $x_3/x_2$ is larger than $x_4/x_3$ but also $x_5/x_4$ is larger than $x_4/x_3$. Those ratios jump around the limit approaching it from both sides.
– Jyrki Lahtonen
Nov 27 at 4:05
@JyrkiLahtonen: I was talking of the sequence ${x_n}$ not the sequence of ratios. I have tried to show the limit of the sequence ${x_n}$ and then tried to estimate the limit of the sequence of ratios.
– Yadati Kiran
Nov 27 at 4:19
Ok. But $(x_n)$ being monotonic does not imply that $(x_{n-1}/x_n)$ converges. Neither does $(x_n)$, so exactly what are you trying to say in the first paragraph?
– Jyrki Lahtonen
Nov 27 at 4:21
I never said that. I have assumed that the limit exists but yes I agree I have to show it does. The answer is incomplete.
– Yadati Kiran
Nov 27 at 4:25
Ok. I do approve of your solution of actually solving the recurrence. That does provide the rigor (if you show that $Aneq0$). Adding my upvote. IMHO your answer would be better without that first paragraph :-)
– Jyrki Lahtonen
Nov 27 at 4:30
|
show 3 more comments
Wrong. The sequence of ratios is not monotonic. $x_1=1$, $x_2=2$, $x_3=5$, $x_4=12$, $x_5=29$ et cetera. Check for yourself that $x_3/x_2$ is larger than $x_4/x_3$ but also $x_5/x_4$ is larger than $x_4/x_3$. Those ratios jump around the limit approaching it from both sides.
– Jyrki Lahtonen
Nov 27 at 4:05
@JyrkiLahtonen: I was talking of the sequence ${x_n}$ not the sequence of ratios. I have tried to show the limit of the sequence ${x_n}$ and then tried to estimate the limit of the sequence of ratios.
– Yadati Kiran
Nov 27 at 4:19
Ok. But $(x_n)$ being monotonic does not imply that $(x_{n-1}/x_n)$ converges. Neither does $(x_n)$, so exactly what are you trying to say in the first paragraph?
– Jyrki Lahtonen
Nov 27 at 4:21
I never said that. I have assumed that the limit exists but yes I agree I have to show it does. The answer is incomplete.
– Yadati Kiran
Nov 27 at 4:25
Ok. I do approve of your solution of actually solving the recurrence. That does provide the rigor (if you show that $Aneq0$). Adding my upvote. IMHO your answer would be better without that first paragraph :-)
– Jyrki Lahtonen
Nov 27 at 4:30
Wrong. The sequence of ratios is not monotonic. $x_1=1$, $x_2=2$, $x_3=5$, $x_4=12$, $x_5=29$ et cetera. Check for yourself that $x_3/x_2$ is larger than $x_4/x_3$ but also $x_5/x_4$ is larger than $x_4/x_3$. Those ratios jump around the limit approaching it from both sides.
– Jyrki Lahtonen
Nov 27 at 4:05
Wrong. The sequence of ratios is not monotonic. $x_1=1$, $x_2=2$, $x_3=5$, $x_4=12$, $x_5=29$ et cetera. Check for yourself that $x_3/x_2$ is larger than $x_4/x_3$ but also $x_5/x_4$ is larger than $x_4/x_3$. Those ratios jump around the limit approaching it from both sides.
– Jyrki Lahtonen
Nov 27 at 4:05
@JyrkiLahtonen: I was talking of the sequence ${x_n}$ not the sequence of ratios. I have tried to show the limit of the sequence ${x_n}$ and then tried to estimate the limit of the sequence of ratios.
– Yadati Kiran
Nov 27 at 4:19
@JyrkiLahtonen: I was talking of the sequence ${x_n}$ not the sequence of ratios. I have tried to show the limit of the sequence ${x_n}$ and then tried to estimate the limit of the sequence of ratios.
– Yadati Kiran
Nov 27 at 4:19
Ok. But $(x_n)$ being monotonic does not imply that $(x_{n-1}/x_n)$ converges. Neither does $(x_n)$, so exactly what are you trying to say in the first paragraph?
– Jyrki Lahtonen
Nov 27 at 4:21
Ok. But $(x_n)$ being monotonic does not imply that $(x_{n-1}/x_n)$ converges. Neither does $(x_n)$, so exactly what are you trying to say in the first paragraph?
– Jyrki Lahtonen
Nov 27 at 4:21
I never said that. I have assumed that the limit exists but yes I agree I have to show it does. The answer is incomplete.
– Yadati Kiran
Nov 27 at 4:25
I never said that. I have assumed that the limit exists but yes I agree I have to show it does. The answer is incomplete.
– Yadati Kiran
Nov 27 at 4:25
Ok. I do approve of your solution of actually solving the recurrence. That does provide the rigor (if you show that $Aneq0$). Adding my upvote. IMHO your answer would be better without that first paragraph :-)
– Jyrki Lahtonen
Nov 27 at 4:30
Ok. I do approve of your solution of actually solving the recurrence. That does provide the rigor (if you show that $Aneq0$). Adding my upvote. IMHO your answer would be better without that first paragraph :-)
– Jyrki Lahtonen
Nov 27 at 4:30
|
show 3 more comments
up vote
1
down vote
One trick is to use the given limit to derive the existence of it.
Write $y_n=frac{x_n}{x_{n+1}}$.
Claim: There exists $rin (0,1)$ such that
$$(sqrt 2-1)-y_nle rbig(y_{n-1}-(sqrt2-1)big).$$
Proof: Rearranging the terms,
begin{align*}
underbrace{frac{x_{n+1}}{x_n}}_{=1/ {y_n}}-1&=underbrace{frac{x_{n-1}}{x_n}}_{=y_{n-1}}+1\
frac 1{y_n}-(sqrt2+1)&=y_{n-1}-(sqrt2-1)\
frac 1{y_n}-frac1{sqrt2-1}&=y_{n-1}-(sqrt2-1)\
(sqrt 2-1)-y_n&=underbrace{y_n(sqrt2-1)}_{in(0,1)}big(y_{n-1}-(sqrt2-1)big).
end{align*}
so the claim is true. $square$
Therefore,
begin{align*}
|y_n-(sqrt2-1)|&le r |y_{n-1}-(sqrt2-1)|le r^2 |y_{n-2}-(sqrt2-1)|lecdots\
&le r^{n}|y_0-(sqrt2-1)|to0,
end{align*}
implies the limit exists, and $limlimits_{ntoinfty}y_n=sqrt2-1$.
add a comment |
up vote
1
down vote
One trick is to use the given limit to derive the existence of it.
Write $y_n=frac{x_n}{x_{n+1}}$.
Claim: There exists $rin (0,1)$ such that
$$(sqrt 2-1)-y_nle rbig(y_{n-1}-(sqrt2-1)big).$$
Proof: Rearranging the terms,
begin{align*}
underbrace{frac{x_{n+1}}{x_n}}_{=1/ {y_n}}-1&=underbrace{frac{x_{n-1}}{x_n}}_{=y_{n-1}}+1\
frac 1{y_n}-(sqrt2+1)&=y_{n-1}-(sqrt2-1)\
frac 1{y_n}-frac1{sqrt2-1}&=y_{n-1}-(sqrt2-1)\
(sqrt 2-1)-y_n&=underbrace{y_n(sqrt2-1)}_{in(0,1)}big(y_{n-1}-(sqrt2-1)big).
end{align*}
so the claim is true. $square$
Therefore,
begin{align*}
|y_n-(sqrt2-1)|&le r |y_{n-1}-(sqrt2-1)|le r^2 |y_{n-2}-(sqrt2-1)|lecdots\
&le r^{n}|y_0-(sqrt2-1)|to0,
end{align*}
implies the limit exists, and $limlimits_{ntoinfty}y_n=sqrt2-1$.
add a comment |
up vote
1
down vote
up vote
1
down vote
One trick is to use the given limit to derive the existence of it.
Write $y_n=frac{x_n}{x_{n+1}}$.
Claim: There exists $rin (0,1)$ such that
$$(sqrt 2-1)-y_nle rbig(y_{n-1}-(sqrt2-1)big).$$
Proof: Rearranging the terms,
begin{align*}
underbrace{frac{x_{n+1}}{x_n}}_{=1/ {y_n}}-1&=underbrace{frac{x_{n-1}}{x_n}}_{=y_{n-1}}+1\
frac 1{y_n}-(sqrt2+1)&=y_{n-1}-(sqrt2-1)\
frac 1{y_n}-frac1{sqrt2-1}&=y_{n-1}-(sqrt2-1)\
(sqrt 2-1)-y_n&=underbrace{y_n(sqrt2-1)}_{in(0,1)}big(y_{n-1}-(sqrt2-1)big).
end{align*}
so the claim is true. $square$
Therefore,
begin{align*}
|y_n-(sqrt2-1)|&le r |y_{n-1}-(sqrt2-1)|le r^2 |y_{n-2}-(sqrt2-1)|lecdots\
&le r^{n}|y_0-(sqrt2-1)|to0,
end{align*}
implies the limit exists, and $limlimits_{ntoinfty}y_n=sqrt2-1$.
One trick is to use the given limit to derive the existence of it.
Write $y_n=frac{x_n}{x_{n+1}}$.
Claim: There exists $rin (0,1)$ such that
$$(sqrt 2-1)-y_nle rbig(y_{n-1}-(sqrt2-1)big).$$
Proof: Rearranging the terms,
begin{align*}
underbrace{frac{x_{n+1}}{x_n}}_{=1/ {y_n}}-1&=underbrace{frac{x_{n-1}}{x_n}}_{=y_{n-1}}+1\
frac 1{y_n}-(sqrt2+1)&=y_{n-1}-(sqrt2-1)\
frac 1{y_n}-frac1{sqrt2-1}&=y_{n-1}-(sqrt2-1)\
(sqrt 2-1)-y_n&=underbrace{y_n(sqrt2-1)}_{in(0,1)}big(y_{n-1}-(sqrt2-1)big).
end{align*}
so the claim is true. $square$
Therefore,
begin{align*}
|y_n-(sqrt2-1)|&le r |y_{n-1}-(sqrt2-1)|le r^2 |y_{n-2}-(sqrt2-1)|lecdots\
&le r^{n}|y_0-(sqrt2-1)|to0,
end{align*}
implies the limit exists, and $limlimits_{ntoinfty}y_n=sqrt2-1$.
edited Nov 26 at 12:55
answered Nov 26 at 12:30
Tianlalu
2,9901936
2,9901936
add a comment |
add a comment |
up vote
0
down vote
Look at $x_n/x_{n+1} - x_{n-1}/x_n$ which is $(x_n^2 - x_{n-1}x_{n+1})/x_n x_{n-1}$.
We can prove by induction that the numerator is $(-1)^n$.
$$x_{n+1}^2 - x_n x_{n+2}
= x_{n+1}^2 - x_n(2x_{n+1} + x_n)
= x_{n+1}(x_{n+1} - 2x_n) - x_n^2
= -(x_n^2 - x_{n-1}x_{n+1})$$
with $x_1^2 - x_0x_2 = -1$. Hence $x_n/x_{n+1}$ tends to a limit by the alternating series test.
You may want to use frac{}{} to write fractions more clearly.
– DonAntonio
Nov 26 at 12:58
add a comment |
up vote
0
down vote
Look at $x_n/x_{n+1} - x_{n-1}/x_n$ which is $(x_n^2 - x_{n-1}x_{n+1})/x_n x_{n-1}$.
We can prove by induction that the numerator is $(-1)^n$.
$$x_{n+1}^2 - x_n x_{n+2}
= x_{n+1}^2 - x_n(2x_{n+1} + x_n)
= x_{n+1}(x_{n+1} - 2x_n) - x_n^2
= -(x_n^2 - x_{n-1}x_{n+1})$$
with $x_1^2 - x_0x_2 = -1$. Hence $x_n/x_{n+1}$ tends to a limit by the alternating series test.
You may want to use frac{}{} to write fractions more clearly.
– DonAntonio
Nov 26 at 12:58
add a comment |
up vote
0
down vote
up vote
0
down vote
Look at $x_n/x_{n+1} - x_{n-1}/x_n$ which is $(x_n^2 - x_{n-1}x_{n+1})/x_n x_{n-1}$.
We can prove by induction that the numerator is $(-1)^n$.
$$x_{n+1}^2 - x_n x_{n+2}
= x_{n+1}^2 - x_n(2x_{n+1} + x_n)
= x_{n+1}(x_{n+1} - 2x_n) - x_n^2
= -(x_n^2 - x_{n-1}x_{n+1})$$
with $x_1^2 - x_0x_2 = -1$. Hence $x_n/x_{n+1}$ tends to a limit by the alternating series test.
Look at $x_n/x_{n+1} - x_{n-1}/x_n$ which is $(x_n^2 - x_{n-1}x_{n+1})/x_n x_{n-1}$.
We can prove by induction that the numerator is $(-1)^n$.
$$x_{n+1}^2 - x_n x_{n+2}
= x_{n+1}^2 - x_n(2x_{n+1} + x_n)
= x_{n+1}(x_{n+1} - 2x_n) - x_n^2
= -(x_n^2 - x_{n-1}x_{n+1})$$
with $x_1^2 - x_0x_2 = -1$. Hence $x_n/x_{n+1}$ tends to a limit by the alternating series test.
answered Nov 26 at 12:57
Michael Behrend
1,04746
1,04746
You may want to use frac{}{} to write fractions more clearly.
– DonAntonio
Nov 26 at 12:58
add a comment |
You may want to use frac{}{} to write fractions more clearly.
– DonAntonio
Nov 26 at 12:58
You may want to use frac{}{} to write fractions more clearly.
– DonAntonio
Nov 26 at 12:58
You may want to use frac{}{} to write fractions more clearly.
– DonAntonio
Nov 26 at 12:58
add a comment |
up vote
0
down vote
Since $x_n$ is increasing, all the terms become non-zero. By defining $a_n={x_nover x_{n+1}}$ we have $${x_nover x_{n+1}}={x_nover 2x_n+x_{n-1}}={1over 2+{x_{n-1}over {x_n}}}$$therefore $$a_n={1over 2+{ a_{n-1}}}$$Now by defining $b_n=a_n-(sqrt 2-1)$ we have $$b_n+sqrt 2-1={1over b_{n-1}+sqrt 2+1}$$therefore $$b_n=-sqrt 2+1+{1over b_{n-1}+sqrt 2+1}={(1-sqrt 2)b_{n-1}over a_n+2}$$since $x_n>0$ we have $a_n>0$ therefore$$|b_n|=|{(1-sqrt 2)b_{n-1}over a_n+2}|le {sqrt 2-1over 2}|b_{n-1}|$$which means that $b_n to 0$ or $a_n={x_nover x_{n+1}}to sqrt 2-1 quadblacksquare$
add a comment |
up vote
0
down vote
Since $x_n$ is increasing, all the terms become non-zero. By defining $a_n={x_nover x_{n+1}}$ we have $${x_nover x_{n+1}}={x_nover 2x_n+x_{n-1}}={1over 2+{x_{n-1}over {x_n}}}$$therefore $$a_n={1over 2+{ a_{n-1}}}$$Now by defining $b_n=a_n-(sqrt 2-1)$ we have $$b_n+sqrt 2-1={1over b_{n-1}+sqrt 2+1}$$therefore $$b_n=-sqrt 2+1+{1over b_{n-1}+sqrt 2+1}={(1-sqrt 2)b_{n-1}over a_n+2}$$since $x_n>0$ we have $a_n>0$ therefore$$|b_n|=|{(1-sqrt 2)b_{n-1}over a_n+2}|le {sqrt 2-1over 2}|b_{n-1}|$$which means that $b_n to 0$ or $a_n={x_nover x_{n+1}}to sqrt 2-1 quadblacksquare$
add a comment |
up vote
0
down vote
up vote
0
down vote
Since $x_n$ is increasing, all the terms become non-zero. By defining $a_n={x_nover x_{n+1}}$ we have $${x_nover x_{n+1}}={x_nover 2x_n+x_{n-1}}={1over 2+{x_{n-1}over {x_n}}}$$therefore $$a_n={1over 2+{ a_{n-1}}}$$Now by defining $b_n=a_n-(sqrt 2-1)$ we have $$b_n+sqrt 2-1={1over b_{n-1}+sqrt 2+1}$$therefore $$b_n=-sqrt 2+1+{1over b_{n-1}+sqrt 2+1}={(1-sqrt 2)b_{n-1}over a_n+2}$$since $x_n>0$ we have $a_n>0$ therefore$$|b_n|=|{(1-sqrt 2)b_{n-1}over a_n+2}|le {sqrt 2-1over 2}|b_{n-1}|$$which means that $b_n to 0$ or $a_n={x_nover x_{n+1}}to sqrt 2-1 quadblacksquare$
Since $x_n$ is increasing, all the terms become non-zero. By defining $a_n={x_nover x_{n+1}}$ we have $${x_nover x_{n+1}}={x_nover 2x_n+x_{n-1}}={1over 2+{x_{n-1}over {x_n}}}$$therefore $$a_n={1over 2+{ a_{n-1}}}$$Now by defining $b_n=a_n-(sqrt 2-1)$ we have $$b_n+sqrt 2-1={1over b_{n-1}+sqrt 2+1}$$therefore $$b_n=-sqrt 2+1+{1over b_{n-1}+sqrt 2+1}={(1-sqrt 2)b_{n-1}over a_n+2}$$since $x_n>0$ we have $a_n>0$ therefore$$|b_n|=|{(1-sqrt 2)b_{n-1}over a_n+2}|le {sqrt 2-1over 2}|b_{n-1}|$$which means that $b_n to 0$ or $a_n={x_nover x_{n+1}}to sqrt 2-1 quadblacksquare$
answered Nov 28 at 0:25
Mostafa Ayaz
13.4k3836
13.4k3836
add a comment |
add a comment |
up vote
-1
down vote
We have that
$$frac{x_{n+1}}{x_n} = 2 + frac{x_{n-1}}{x_n}$$
then by
$$y_n=frac{x_{n}}{x_{n-1}} implies y_{n+1}=2+frac1{y_n }quad y_0=2$$
which converges to $L=sqrt 2+1$ and then
$$lim_{nto infty} frac{x_n}{x_{n+1}}=lim_{nto infty} frac{1}{y_{n+1}}=frac1L=sqrt 2 -1$$
1
It seems $y_n$ is 'alternating', i.e. increasing/decreasing when $n$ even and decreasing/increasing when $n$ odd.
– Tianlalu
Nov 26 at 13:08
2
Why $;y_n;$ is increasing and bounded?
– DonAntonio
Nov 26 at 13:10
@DonAntonio Yes I need to clarify that point better! Thanks
– gimusi
Nov 26 at 13:17
add a comment |
up vote
-1
down vote
We have that
$$frac{x_{n+1}}{x_n} = 2 + frac{x_{n-1}}{x_n}$$
then by
$$y_n=frac{x_{n}}{x_{n-1}} implies y_{n+1}=2+frac1{y_n }quad y_0=2$$
which converges to $L=sqrt 2+1$ and then
$$lim_{nto infty} frac{x_n}{x_{n+1}}=lim_{nto infty} frac{1}{y_{n+1}}=frac1L=sqrt 2 -1$$
1
It seems $y_n$ is 'alternating', i.e. increasing/decreasing when $n$ even and decreasing/increasing when $n$ odd.
– Tianlalu
Nov 26 at 13:08
2
Why $;y_n;$ is increasing and bounded?
– DonAntonio
Nov 26 at 13:10
@DonAntonio Yes I need to clarify that point better! Thanks
– gimusi
Nov 26 at 13:17
add a comment |
up vote
-1
down vote
up vote
-1
down vote
We have that
$$frac{x_{n+1}}{x_n} = 2 + frac{x_{n-1}}{x_n}$$
then by
$$y_n=frac{x_{n}}{x_{n-1}} implies y_{n+1}=2+frac1{y_n }quad y_0=2$$
which converges to $L=sqrt 2+1$ and then
$$lim_{nto infty} frac{x_n}{x_{n+1}}=lim_{nto infty} frac{1}{y_{n+1}}=frac1L=sqrt 2 -1$$
We have that
$$frac{x_{n+1}}{x_n} = 2 + frac{x_{n-1}}{x_n}$$
then by
$$y_n=frac{x_{n}}{x_{n-1}} implies y_{n+1}=2+frac1{y_n }quad y_0=2$$
which converges to $L=sqrt 2+1$ and then
$$lim_{nto infty} frac{x_n}{x_{n+1}}=lim_{nto infty} frac{1}{y_{n+1}}=frac1L=sqrt 2 -1$$
edited Nov 26 at 13:21
answered Nov 26 at 13:04
gimusi
91.2k74495
91.2k74495
1
It seems $y_n$ is 'alternating', i.e. increasing/decreasing when $n$ even and decreasing/increasing when $n$ odd.
– Tianlalu
Nov 26 at 13:08
2
Why $;y_n;$ is increasing and bounded?
– DonAntonio
Nov 26 at 13:10
@DonAntonio Yes I need to clarify that point better! Thanks
– gimusi
Nov 26 at 13:17
add a comment |
1
It seems $y_n$ is 'alternating', i.e. increasing/decreasing when $n$ even and decreasing/increasing when $n$ odd.
– Tianlalu
Nov 26 at 13:08
2
Why $;y_n;$ is increasing and bounded?
– DonAntonio
Nov 26 at 13:10
@DonAntonio Yes I need to clarify that point better! Thanks
– gimusi
Nov 26 at 13:17
1
1
It seems $y_n$ is 'alternating', i.e. increasing/decreasing when $n$ even and decreasing/increasing when $n$ odd.
– Tianlalu
Nov 26 at 13:08
It seems $y_n$ is 'alternating', i.e. increasing/decreasing when $n$ even and decreasing/increasing when $n$ odd.
– Tianlalu
Nov 26 at 13:08
2
2
Why $;y_n;$ is increasing and bounded?
– DonAntonio
Nov 26 at 13:10
Why $;y_n;$ is increasing and bounded?
– DonAntonio
Nov 26 at 13:10
@DonAntonio Yes I need to clarify that point better! Thanks
– gimusi
Nov 26 at 13:17
@DonAntonio Yes I need to clarify that point better! Thanks
– gimusi
Nov 26 at 13:17
add a comment |
up vote
-1
down vote
Let
$$lim_{nto infty} frac{x_n}{x_{n+1}} = lim_{nto infty} frac{x_{n-1}}{x_{n1}} = k$$
Now
$$lim_{nto infty} frac{x_n}{x_{n+1}} = k$$
$$lim_{nto infty} frac{x_n}{2x_{n} + x_{n-1}} = k$$
Take $x_n$ out from numerator and denominator
$$lim_{nto infty} frac{1}{2 + frac{x_{n-1}}{x_n}} = k$$
Using the first equation
$$ frac{1}{2 + k} = k$$
$$k^2+2k-1=0$$
This gives two solutions $k=sqrt{2}-1$ and $k=-sqrt{2}-1$. Since none of the terms can be negative, we reject . the second solution thereby giving us
$$lim_{nto infty} frac{x_n}{x_{n+1}} = k = sqrt2 - 1$$
EDIT - As suggested by the commenter we need to prove that it is a finite limit before we start with the proof. Initially it's a $frac{infty}{infty}$ form as both $x_n$ and $x_{n+1}$ approach $infty$ as $n$ approaches $infty$. I'll use a finite upper bound to show that the limit is finite which means it exists.
For any $n$
$$frac{x_n}{x_{n+1}} =frac{x_n}{2x_n + x_{n-1}}$$
As $x_{n-1}$ is always a positive quantity
$$frac{x_n}{x_{n+1}} leq frac{x_n}{2x_n}$$
$$frac{x_n}{x_{n+1}} leq frac{1}{2}$$
For any $n$, you can take the last statement to prove the monotonicity as
$$x_{n+1}geq x_n$$
And since both $x_n$ and $x_{n+1}$ are positive values, the lower bound is $0$. The upper bound along with lower bound and the monotonicity proves that the limit is finite.
3
This seems to be the less hard part of the question. The hardest part is to prove the limit exists...
– DonAntonio
Nov 26 at 12:22
1
Is there any way to independently do that ?
– Sauhard Sharma
Nov 26 at 12:35
Why can you write the first line? why is the limit of $frac{x_n}{x_{n+1}} = frac{x_{n-1}}{x_n}$ ?
– M-S-R
Nov 26 at 12:54
@SauhardSharma It better is, otherwise your whole answer is invalid as you can use arithmetic of limits only if you know that the limit exists finitely, otherwise you can't. You can try induction, for example, to prove monotonicity or something like that
– DonAntonio
Nov 26 at 13:02
@DonAntonio Thanks for pointing out my mistake. I think the edited proof should suffice
– Sauhard Sharma
Nov 26 at 13:18
|
show 3 more comments
up vote
-1
down vote
Let
$$lim_{nto infty} frac{x_n}{x_{n+1}} = lim_{nto infty} frac{x_{n-1}}{x_{n1}} = k$$
Now
$$lim_{nto infty} frac{x_n}{x_{n+1}} = k$$
$$lim_{nto infty} frac{x_n}{2x_{n} + x_{n-1}} = k$$
Take $x_n$ out from numerator and denominator
$$lim_{nto infty} frac{1}{2 + frac{x_{n-1}}{x_n}} = k$$
Using the first equation
$$ frac{1}{2 + k} = k$$
$$k^2+2k-1=0$$
This gives two solutions $k=sqrt{2}-1$ and $k=-sqrt{2}-1$. Since none of the terms can be negative, we reject . the second solution thereby giving us
$$lim_{nto infty} frac{x_n}{x_{n+1}} = k = sqrt2 - 1$$
EDIT - As suggested by the commenter we need to prove that it is a finite limit before we start with the proof. Initially it's a $frac{infty}{infty}$ form as both $x_n$ and $x_{n+1}$ approach $infty$ as $n$ approaches $infty$. I'll use a finite upper bound to show that the limit is finite which means it exists.
For any $n$
$$frac{x_n}{x_{n+1}} =frac{x_n}{2x_n + x_{n-1}}$$
As $x_{n-1}$ is always a positive quantity
$$frac{x_n}{x_{n+1}} leq frac{x_n}{2x_n}$$
$$frac{x_n}{x_{n+1}} leq frac{1}{2}$$
For any $n$, you can take the last statement to prove the monotonicity as
$$x_{n+1}geq x_n$$
And since both $x_n$ and $x_{n+1}$ are positive values, the lower bound is $0$. The upper bound along with lower bound and the monotonicity proves that the limit is finite.
3
This seems to be the less hard part of the question. The hardest part is to prove the limit exists...
– DonAntonio
Nov 26 at 12:22
1
Is there any way to independently do that ?
– Sauhard Sharma
Nov 26 at 12:35
Why can you write the first line? why is the limit of $frac{x_n}{x_{n+1}} = frac{x_{n-1}}{x_n}$ ?
– M-S-R
Nov 26 at 12:54
@SauhardSharma It better is, otherwise your whole answer is invalid as you can use arithmetic of limits only if you know that the limit exists finitely, otherwise you can't. You can try induction, for example, to prove monotonicity or something like that
– DonAntonio
Nov 26 at 13:02
@DonAntonio Thanks for pointing out my mistake. I think the edited proof should suffice
– Sauhard Sharma
Nov 26 at 13:18
|
show 3 more comments
up vote
-1
down vote
up vote
-1
down vote
Let
$$lim_{nto infty} frac{x_n}{x_{n+1}} = lim_{nto infty} frac{x_{n-1}}{x_{n1}} = k$$
Now
$$lim_{nto infty} frac{x_n}{x_{n+1}} = k$$
$$lim_{nto infty} frac{x_n}{2x_{n} + x_{n-1}} = k$$
Take $x_n$ out from numerator and denominator
$$lim_{nto infty} frac{1}{2 + frac{x_{n-1}}{x_n}} = k$$
Using the first equation
$$ frac{1}{2 + k} = k$$
$$k^2+2k-1=0$$
This gives two solutions $k=sqrt{2}-1$ and $k=-sqrt{2}-1$. Since none of the terms can be negative, we reject . the second solution thereby giving us
$$lim_{nto infty} frac{x_n}{x_{n+1}} = k = sqrt2 - 1$$
EDIT - As suggested by the commenter we need to prove that it is a finite limit before we start with the proof. Initially it's a $frac{infty}{infty}$ form as both $x_n$ and $x_{n+1}$ approach $infty$ as $n$ approaches $infty$. I'll use a finite upper bound to show that the limit is finite which means it exists.
For any $n$
$$frac{x_n}{x_{n+1}} =frac{x_n}{2x_n + x_{n-1}}$$
As $x_{n-1}$ is always a positive quantity
$$frac{x_n}{x_{n+1}} leq frac{x_n}{2x_n}$$
$$frac{x_n}{x_{n+1}} leq frac{1}{2}$$
For any $n$, you can take the last statement to prove the monotonicity as
$$x_{n+1}geq x_n$$
And since both $x_n$ and $x_{n+1}$ are positive values, the lower bound is $0$. The upper bound along with lower bound and the monotonicity proves that the limit is finite.
Let
$$lim_{nto infty} frac{x_n}{x_{n+1}} = lim_{nto infty} frac{x_{n-1}}{x_{n1}} = k$$
Now
$$lim_{nto infty} frac{x_n}{x_{n+1}} = k$$
$$lim_{nto infty} frac{x_n}{2x_{n} + x_{n-1}} = k$$
Take $x_n$ out from numerator and denominator
$$lim_{nto infty} frac{1}{2 + frac{x_{n-1}}{x_n}} = k$$
Using the first equation
$$ frac{1}{2 + k} = k$$
$$k^2+2k-1=0$$
This gives two solutions $k=sqrt{2}-1$ and $k=-sqrt{2}-1$. Since none of the terms can be negative, we reject . the second solution thereby giving us
$$lim_{nto infty} frac{x_n}{x_{n+1}} = k = sqrt2 - 1$$
EDIT - As suggested by the commenter we need to prove that it is a finite limit before we start with the proof. Initially it's a $frac{infty}{infty}$ form as both $x_n$ and $x_{n+1}$ approach $infty$ as $n$ approaches $infty$. I'll use a finite upper bound to show that the limit is finite which means it exists.
For any $n$
$$frac{x_n}{x_{n+1}} =frac{x_n}{2x_n + x_{n-1}}$$
As $x_{n-1}$ is always a positive quantity
$$frac{x_n}{x_{n+1}} leq frac{x_n}{2x_n}$$
$$frac{x_n}{x_{n+1}} leq frac{1}{2}$$
For any $n$, you can take the last statement to prove the monotonicity as
$$x_{n+1}geq x_n$$
And since both $x_n$ and $x_{n+1}$ are positive values, the lower bound is $0$. The upper bound along with lower bound and the monotonicity proves that the limit is finite.
edited Nov 26 at 13:48
answered Nov 26 at 12:18
Sauhard Sharma
3538
3538
3
This seems to be the less hard part of the question. The hardest part is to prove the limit exists...
– DonAntonio
Nov 26 at 12:22
1
Is there any way to independently do that ?
– Sauhard Sharma
Nov 26 at 12:35
Why can you write the first line? why is the limit of $frac{x_n}{x_{n+1}} = frac{x_{n-1}}{x_n}$ ?
– M-S-R
Nov 26 at 12:54
@SauhardSharma It better is, otherwise your whole answer is invalid as you can use arithmetic of limits only if you know that the limit exists finitely, otherwise you can't. You can try induction, for example, to prove monotonicity or something like that
– DonAntonio
Nov 26 at 13:02
@DonAntonio Thanks for pointing out my mistake. I think the edited proof should suffice
– Sauhard Sharma
Nov 26 at 13:18
|
show 3 more comments
3
This seems to be the less hard part of the question. The hardest part is to prove the limit exists...
– DonAntonio
Nov 26 at 12:22
1
Is there any way to independently do that ?
– Sauhard Sharma
Nov 26 at 12:35
Why can you write the first line? why is the limit of $frac{x_n}{x_{n+1}} = frac{x_{n-1}}{x_n}$ ?
– M-S-R
Nov 26 at 12:54
@SauhardSharma It better is, otherwise your whole answer is invalid as you can use arithmetic of limits only if you know that the limit exists finitely, otherwise you can't. You can try induction, for example, to prove monotonicity or something like that
– DonAntonio
Nov 26 at 13:02
@DonAntonio Thanks for pointing out my mistake. I think the edited proof should suffice
– Sauhard Sharma
Nov 26 at 13:18
3
3
This seems to be the less hard part of the question. The hardest part is to prove the limit exists...
– DonAntonio
Nov 26 at 12:22
This seems to be the less hard part of the question. The hardest part is to prove the limit exists...
– DonAntonio
Nov 26 at 12:22
1
1
Is there any way to independently do that ?
– Sauhard Sharma
Nov 26 at 12:35
Is there any way to independently do that ?
– Sauhard Sharma
Nov 26 at 12:35
Why can you write the first line? why is the limit of $frac{x_n}{x_{n+1}} = frac{x_{n-1}}{x_n}$ ?
– M-S-R
Nov 26 at 12:54
Why can you write the first line? why is the limit of $frac{x_n}{x_{n+1}} = frac{x_{n-1}}{x_n}$ ?
– M-S-R
Nov 26 at 12:54
@SauhardSharma It better is, otherwise your whole answer is invalid as you can use arithmetic of limits only if you know that the limit exists finitely, otherwise you can't. You can try induction, for example, to prove monotonicity or something like that
– DonAntonio
Nov 26 at 13:02
@SauhardSharma It better is, otherwise your whole answer is invalid as you can use arithmetic of limits only if you know that the limit exists finitely, otherwise you can't. You can try induction, for example, to prove monotonicity or something like that
– DonAntonio
Nov 26 at 13:02
@DonAntonio Thanks for pointing out my mistake. I think the edited proof should suffice
– Sauhard Sharma
Nov 26 at 13:18
@DonAntonio Thanks for pointing out my mistake. I think the edited proof should suffice
– Sauhard Sharma
Nov 26 at 13:18
|
show 3 more comments
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3014227%2fprove-existence-of-the-limit-of-a-sequence%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
Don´t forget to mark an answer as accepted!!! Have a look at your other questions as well. Then your "$textrm{Thank you very much for your help!}$" is more credible.
– callculus
Nov 27 at 21:34