Infinite sequence (recursive)

**hjortur** · September 20th 2009, 10:42 AM

Let $x_0$ and $k$ be positive real numbers.
$ x_n = \frac{k}{1+x_{n-1}} , \text{ for } n\geq1 $

Now prove that either of the sequences $x_1 , x_3, x_5 \dotsb$ or $x_2 , x_4 , x_6 , \dotsb$ is increasing and the other one is decreasing.

Then prove that $x_1 , x_2 , \dotsb x_n$ is convergant.

I have no idea how to work with recursive sequences, so if someone could tell me how do I start?

**bkarpuz** · September 20th 2009, 11:46 AM

Originally Posted by hjortur

Let $x_0$ and $k$ be positive real numbers.
$ x_n = \frac{k}{1+x_{n-1}} , \text{ for } n\geq0 $

Now prove that either of the sequences $x_1 , x_3, x_5 \dotsb$ or $x_2 , x_4 , x_6 , \dotsb$ is increasing and the other one is decreasing.

Then prove that $x_1 , x_2 , \dotsb x_n$ is convergant.

I have no idea how to work with recursive sequences, so if someone could tell me how do I start?

Do we know that $x_{-1}>0$ ?, otherwise there may occur some problems...

**hjortur** · September 20th 2009, 12:03 PM

I fixed typo in original post. Now it is no problem like you said.

**bkarpuz** · September 20th 2009, 02:03 PM

Originally Posted by hjortur

Let $x_0$ and $k$ be positive real numbers.
$ x_n = \frac{k}{1+x_{n-1}} , \text{ for } n\geq1 $

Now prove that either of the sequences $x_1 , x_3, x_5 \dotsb$ or $x_2 , x_4 , x_6 , \dotsb$ is increasing and the other one is decreasing.

Then prove that $x_1 , x_2 , \dotsb x_n$ is convergant.

I have no idea how to work with recursive sequences, so if someone could tell me how do I start?

I am not very sure, since I am also new to rational difference equations. But the clue must be hidden in defining $f(x):=\frac{(1+x)k}{1+k+x}>0$ for $x>0$ . Then, $f^{\prime}>0>f^{\prime\prime}$ . Moreover, we have $x(n)=f\big(x(n-2)\big)$ for $n\geq2$ . Also note that the equilibrium of the given equation is $x=\frac{1}{2}\big(-1+\sqrt{1+4k}\big)$ .

**hjortur** · September 20th 2009, 02:59 PM

Hmmm...

If you define
$ f(x):=\frac{(1+x)k}{1+k+x}>0 $

and then define:

$ g(x):=\frac{k}{1+f(x)}=\frac{k+kx+k^2}{1+2k+x+kx} $

then $g'(x)<0$

Then say something along the line that f(x) gives every other (e.g. even) numbers and g(x), the others. Now the derivative of g(x) is negative so that sequence is decreasing, and f(x) is positive so it is increasing?

I dont know, still doesnt help to prove that the whole sequence is convergant.

What does it mean when you say:

Also note that the equilibrium of the given equation is $x=\frac{1}{2}\big(-1+\sqrt{1+4k}\big)$ .

Lets assume the limit excists, call it L. Now:
$ x_n = \frac{k}{1+x_{n-1}} $
$ L = \frac{k}{1+L} $

So the limit is the positive solution to $L^2 +L =k$

**bkarpuz** · September 21st 2009, 03:57 AM

Originally Posted by hjortur

Let $x_0$ and $k$ be positive real numbers.
$ x_n = \frac{k}{1+x_{n-1}} , \text{ for } n\geq1 $

Now prove that either of the sequences $x_1 , x_3, x_5 \dotsb$ or $x_2 , x_4 , x_6 , \dotsb$ is increasing and the other one is decreasing.

Then prove that $x_1 , x_2 , \dotsb x_n$ is convergant.

I have no idea how to work with recursive sequences, so if someone could tell me how do I start?

I will give a proof for the highlighted part, because I don't have any idea how to prove the first part yet, but I will write if I can find.
Using the recursion formula
$x(n)=\frac{k}{1+x(n-1)}$ ....for $n\geq1$ ,....(1)
where $x(0)>0$ and $k>0$ , we learn that
$x(n)<k$ ....for all $n\geq1$ , i.e., $\{x(n)\}_{n\in\mathbb{N}_{0}}$ is bounded.
Set
$\ell_{*}:=\liminf_{n\to\infty}x(n)$ ....and.... $\ell^{*}:=\limsup_{n\to\infty}x(n)$ .
Clearly,
$0\leq\ell_{*}\leq\ell^{*}\leq k$ .....(2)
Taking now inferior and superior limits on both sides of (1), we obtain
$\ell_{*}\geq\frac{k}{1+\ell^{*}}$ ....and.... $\ell^{*}\leq\frac{k}{1+\ell_{*}}$ (actually they are equal, but I prefer inequalities for a general proof),
which yields
$\ell_{*}(1+\ell^{*})\geq k\geq\ell^{*}(1+\ell_{*})$ ,
or equivalently
$\frac{\ell_{*}}{1+\ell_{*}}\geq\frac{\ell^{*}}{1+\ ell^{*}}$ .....(3)
Set $\nu(\lambda):=\lambda/(1+\lambda)$ for $\lambda>0$ , and note that $\nu$ is increasing on $[0,\infty)$ .
From (3), we have
$\nu(\ell_{*})\geq\nu(\ell^{*})$ ,
which yields
$\ell_{*}\geq\ell^{*}$ .....(4)
It follows from (2) and (4) that $\ell_{*}=\ell^{*}$ , i.e., $\{x(n)\}_{n\in\mathbb{N}_{0}}$ has a finite limit at infinity (more precisely this limit value lies in the interval $[0,k]$ ).
Let
$\ell:=\lim_{n\to\infty}x(n)$ .
Taking limit on both sides of (1), we obtain
$\ell=\frac{k}{1+\ell}$ ,....(5)
and solving this we obtain
$\ell:=\frac{1}{2}\big(-1+\sqrt{1+4k}\big)$ (note that we took the positive solution of (5) since the solutions we consider are positive),
which is called the equilibrium of the recursive equation (1).
Every solution of (1) with positive initial value and positive $k$ , tends to the equilibrium $\ell$ .

You should refer to the following books for rational difference equations:
[1] M. R. S. Kulenovic and G. Ladas, Dynamics of Second Order Rational Difference Equations with Open Problems and Conjectures, Champman & Hall, 2002.
[2] E. Camouzis and G. Ladas, Dynamics of Third-Order Rational Difference Equations with Open Problems and Conjectures, Champman & Hall, 2008.

Mathematica codes for plotting a graphic of the solution of the rational sequence

Code:

s=30; "Number of iterations";
x=Table[0,{i,1,s+1}];
k=1; "Coefficient";
x[[1]]=1; "Initial Value";
For[i=1,i<=s,i++,x[[i+1]]=k/(1+x[[i]])]
eq=l/.Solve[l==k/(1+l),{l}];
eq=If[eq[[1]]>0,eq[[1]],eq[[2]]];
xtab=Table[{i,x[[i+1]]},{i,0,s}];
Show[ListPlot[xtab,PlotStyle->{Red,PointSize[0.02],Opacity[1]},PlotRange->Full,AxesOrigin->{0,0}],ListPlot[xtab,PlotStyle->{Blue,Dashed,Thickness[0.001],Opacity[1]},Joined->True],Plot[eq,{i,0,s},PlotStyle->{Green,Thickness[0.001]}]]

**bkarpuz** · September 21st 2009, 07:36 AM

Originally Posted by hjortur

Let $x_0$ and $k$ be positive real numbers.
$ x_n = \frac{k}{1+x_{n-1}} , \text{ for } n\geq1 $

Now prove that either of the sequences $x_1 , x_3, x_5 \dotsb$ or $x_2 , x_4 , x_6 , \dotsb$ is increasing and the other one is decreasing.

Then prove that $x_1 , x_2 , \dotsb x_n$ is convergant.

I have no idea how to work with recursive sequences, so if someone could tell me how do I start?

I will show you the proof only for the case where either $\{x(2k+1)\}_{k\in\mathbb{N}}$ or $\{x(2k)\}_{\in\mathbb{N}}$ is decreasing by leaving some open problems.

From the second part of the proof, we now know that every solution of the rational difference equation
$x(n)=\frac{k}{1+x(n-1)}$ ....for $n\in\mathbb{N}$ ....(1)
converges to the equilibrium point of the equation $\ell:=\big(-1\sqrt{1+4k}\big)/2$ .
Now define $g(u):=k/(1+u)$ and $f(u):=(g\circ g)(u)=k(1+u)/(1+k+u)$ for $u\geq0$ .
It is clear that $g>0>g^{\prime}$ on $[0,\infty)$ and $\ell$ is the only positive fixed point of $g$ the equation, i.e., $u=\ell$ is the only solution of $g(u)=u$ for $u\geq0$ .
Moreover,
$f,f^{\prime}>0>f^{\prime\prime}$ on $[0,\infty)$ ....(2)
and $\ell$ is the only positive fixed point of $f$ too.
From (2), we see that
$f(u)\geq f(\ell)=\ell$ for all $u\geq\ell$ .....(3)

Open Problem 1. Prove that $f(u)\leq u$ for all $u\in[\ell,\infty)$ .
Note. For this open problem, Mathematica 7.0 returns empty set when trying to find some $u\geq\ell$ such that $f(u)>u$ .
Below you will find the code, but you have to prove it yourself.

Code:

f[u_,k_]=(k(1+u))/(1+k+u);
l[k_]=l/.Solve[l ==k/(1+l),{l}][[2]];
FindInstance[f[u,k]>u&&k>0&&u>l[k],{u,k}]

I assume that the proof for the open problem is given and continue the proof for the original problem.
Hence, (3) can be rewritten as
$u\geq f(u)\geq f(\ell)=\ell$ for all $u\geq\ell$ ,....(4)
Rewrite now (1) as
$x(n)=f\big(x(n-2)\big)$ ....for $n\geq2$ .....(5)
If $x(n)\geq\ell$ for some $n\in\mathbb{N}$ , then from (4) and (5), we have
$x(n)\geq f\big(x(n)\big)=x(n+2)\geq f(\ell)=\ell$ .....(6)
This proves that if a term is above the equilibrium then succeeding second term is not greater than this term and not less than the equilibrium point.
By mathematical induction, we can say that if $x(0)>\ell$ , then $\{x(2n)\}_{n\in\mathbb{N}_{0}}$ decreases to $\ell$ , and if $x(1)>\ell$ , then $\{x(2n+1)\}_{n\in\mathbb{N}_{0}}$ decreases to $\ell$ also.

You can show by using very similar arguments that the subsequences increase to the equilibrium provided that their initial values are not greater than the equilibrium.
In this case you need to prove the following problem.

Open Problem 2. Prove that $f(u)\geq u$ for all $u\in[0,\ell]$ .
Again see the solution by Mathematica 7.0.

Code:

f[u_,k_]=(k(1+u))/(1+k+u);
l[k_]=l/.Solve[l ==k/(1+l),{l}][[2]];
FindInstance[f[u,k]<u&&k>0&&u<l[k]&&u>0,{u,k}]

Please let me know when you have proofs for the open problems.

**hjortur** · September 21st 2009, 11:40 AM

Wow, thank you bkarpuz. But I am pretty sure your solution is much to complicated. Most of what you are talking about, I have never even heard of. This was supposed to be an easy excercise at the end of the chapter on sequences.

But thank you very much, for taking your time to answer my question.

**bkarpuz** · September 21st 2009, 11:48 AM

Originally Posted by hjortur

Wow, thank you bkarpuz. But I am pretty sure your solution is much to complicated. Most of what you are talking about, I have never even heard of. This was supposed to be an easy excercise at the end of the chapter on sequences.

But thank you very much, for taking your time to answer my question.

I don't believe

Please let me know which book is it!

Also please let me know if you find a simple solution.

**hjortur** · September 21st 2009, 12:59 PM

It is an Icelandic textbook written by my teacher, so you will probably never find it.
Because we have a different system here in Iceland, it is hard to say what course my course corresponds to.
But I think it is somewhere along the lines of Calculus I and Mathematical analysis I. (First year, BSc (in mathematics) student).

But I will tell you when I find a simple solution.

Thread: Infinite sequence (recursive)

LinkBack

Thread Tools

Display

Infinite sequence (recursive)

Proof of the second part

Proof for the first part

Similar Math Help Forum Discussions

Recursive Sequence Convergence

Recursive sequence (Fibonacci Sequence) & Limits

recursive sequence

recursive sequence

recursive sequence

Search Tags