# How to find the limit of this recurrence relation?

$a_n$ is a sequence where $a_1=0$ and $a_2=100$, and for $n \geq 2$: $$a_{n+1}=a_n+\frac{a_n-1}{(n)^2-1}$$

I have a basic understanding of sequences. I wasn't sure how to deal with this recurrence relation since there is $n$ in the equation.

By using an excel sheet, I know the limit is 199. And I confirmed this with Wolfram Alpha, which showed that the "Recurrence equation solution" is: $f(x)=199-\frac{198}{x}$

My question: Is it possible to find the limit of this sequence or even the "recurrence equation solution" without using an excel sheet or Wolfram Alpha? If so, can you clearly explain how this is done?

-
Is it $$a_n-1\text{ or }a_{n-1}?$$ – lab bhattacharjee Feb 21 '14 at 15:41
You only need to know with $a_1$ or $a_{100}$ to find the limit since it is a recurrence relation that only depends on the last element. So hopefully there is no contradiction between $a_1$ and $a_{100}$. That being said, I would doubt the limit is 99 because $a_{101} = 100 + \frac{99}{9,999} > 99$ and this is an increasing sequence. – Squirtle Feb 21 '14 at 15:44
To "lab bhattacharjee": It is correct the way it is. It is: $a_n-1$ – FiBO Feb 21 '14 at 15:47
To "Squirtle": The limit is 199, not 99. I confirmed this. – FiBO Feb 21 '14 at 15:48
I think what's confusing is that you have a first-order diff eq'n yet have two initial values. – Ron Gordon Feb 21 '14 at 16:02

Once you have the clue that $a_n = b + c/n$ for some constants $b$ and $c$, it's easy to plug this in to the equation and see that this works if $b+c=1$. Then take $n=2$ to match the value there.

EDIT: So, how could you guess the form $a_n = b + c/n$? Well, if you look for solutions to $f(z+1) = f(z) + \dfrac{f(z) - 1}{n^2 - 1}$ where $a_n = f(n)$ is a rational function of $n$, if $f(z)$ has a pole of order $k$ at $z=p$ then $f(z+1)$ has a pole of the same order at $z=p-1$. This rapidly leads to the conclusion that the only possible pole of $f(z)$ is at $z=0$ (and that of order at most $2$). For example, if there was a pole at $z = \infty$, i.e. $f(z) = a z^d + O(z^{d-1})$ with $d \ge 1$ and $a \ne 0$, then $$f(z+1) - f(z) - \dfrac{f(z)-1}{z^2 - 1} = a d z^{d-1} + O(z^{d-2}) \ne 0$$

-

The recurrence relation can be rewritten as

$${n+1\over n}a_{n+1}=\left({1\over n}-{1\over n-1}\right)+{n\over n-1}a_n$$

Now let

$$b_k={k\over k-1}a_k$$

to obtain

\begin{align} b_{n+1}&=\left({1\over n}-{1\over n-1}\right)+b_n\\ &=\left({1\over n}-{1\over n-1}\right)+\left({1\over n-1}-{1\over n-2}\right)+b_{n-1}\\ &\vdots\\ &=\left({1\over n}-{1\over3-2}\right)+b_{3-1}\\ &=\left({1\over n}-1\right)+2a_2\\ &={1\over n}+199 \end{align}

It follows that $\lim_{n\to\infty}a_n=\lim_{n\to\infty}{n-1\over n}b_n=199$.

Having written all this up, I see it's essentially the same answer as Jack D'Aurizio's, just organized in a somewhat different fashion.

-

The recurrence

$$a_{n+1}=a_n+\frac{a_n-1}{n^2-1}$$

is a discretization of the differential equation

$$\frac{dy}{dx} = \frac{y-1}{x^2-1}.$$

This equation is separable and has solution

$$y(x) = 1 + C \sqrt{1 - \frac{2}{x+2}}.$$

Now, for large $x$ we have

$$y(x) \approx 1 + C \left(1 - \frac{1}{x+2}\right) \approx 1 + C \left(1 - \frac{1}{x}\right) = 1+C - \frac{C}{x},$$

by the binomial theorem, which suggests checking for a solution of the form $a_n = 1+C - \frac{C}{n}$ in the recurrence relation.

-

To find $a_n$ for every $n\geqslant2$, one can use the trick of centering a recursion around its fixed point.

Here $a_n=1$ would imply $a_{n+1}=1$, hence one can consider the sequence $b_n=a_n-1$, and, see what happens! one gets $$b_{n+1}=\frac{n^2}{n^2-1}b_n.$$ Thus, for every $n\geqslant2$, $$a_n=1+A_n\cdot(a_2-1),\qquad A_n=\prod_{k=2}^{n-1}\frac{k^2}{k^2-1}.$$ Now, $k^2-1=(k+1)(k-1)$ hence $$A_n=\frac{2\cdot3\cdots(n-1)}{1\cdot2\cdots(n-2)}\cdot\frac{2\cdot3\cdots(n-1)}{3\cdot4\cdots n}=\frac{2(n-1)}n=2-\frac2n.$$ Finally, $$a_n=2a_2-1-(a_2-1)\frac2n.$$ This confirms the formula you indicate in your post when $a_2=100$ and shows that, in the general case, $$\lim\limits_{n\to\infty}a_n=2a_2-1.$$

-
I didn't understand what you meant with "centering a recursion around its fixed point" and why did you a product of the sequence? – FiBO Feb 21 '14 at 16:50
"Centering around $1$" is, as explained one line below, to consider $b_n=a_n-1$. And if $b_{n+1}=c_{n+1}b_n$ for every $n\geqslant2$, then $b_n=c_nc_{n-1}\cdots c_3b_2$, that is, $a_n-1=c_nc_{n-1}\cdots c_3(a_2-1)$, that is, $a_n=1+c_nc_{n-1}\cdots c_3(a_2-1)$. – Did Feb 21 '14 at 16:55

You have: $$(n^2-1)\,a_{n+1} = n^2 a_n - 1,$$ that by putting $b_n = n a_n$ becomes: $$(n-1) b_{n+1} = n b_n - 1,$$ or: $$\frac{b_{n+1}}{n}-\frac{b_n}{n-1}=-\frac{1}{n(n-1)}=\frac{1}{n}-\frac{1}{n-1},$$ so if we set $c_n=\frac{b_n}{n-1}=\frac{n}{n-1}a_n$, we end with: $$c_{n+1}-c_{n} = \frac{1}{n}-\frac{1}{n-1}.\tag{1}$$ If $c_2=2a_2=200$ (notice that only one starting value is needed), by summing both sides of $(1)$ with $n$ going from $2$ to $N-1$ you get: $$c_{N}-c_2 = \sum_{n=2}^{N-1}\left(\frac{1}{n}-\frac{1}{n-1}\right)=\frac{1}{N-1}-1,$$ then: $$c_{N} = \frac{1}{N-1}+199$$ and: $$a_{N} = \frac{1}{N}+199\cdot\frac{N-1}{N} = 199 - \frac{198}{N}$$ as claimed by Wolfram Alpha.

-
I like your solution, but you can add more explanation to how you reached this solution exactly? I kind of got lost with c and summation. – FiBO Feb 21 '14 at 16:37
This kind of technique is the discrete analogue of integration through a change of variable: we define ausiliary sequences in order to have a recursion like $d_{n+1}-d_{n}=f(n)$. Doing so, $d_n$ is the $n$-th partial sum of $f(n)$. If $\sum f(n)$ is a telescoping sum, we get a "closed"-expression for $d_n$, then for our starting sequence. – Jack D'Aurizio Feb 21 '14 at 16:43

Hint: clearly, your sequence is increasing. To prove it converges, an idea would be to find an upper bound on $a_n$ and prove it holds via a recurrence relation.

Cheating by looking at the limit computed by Mathematica (which, to generalize a bit, is $2\alpha -1$ when $a_2=\alpha$), you can try to prove $$a_n < 2\alpha - 1 - \frac{C}{n}\qquad \forall n\geq 2$$ for some "convenient" constant $C$ (I tried quickly, unless I made a mistake $C\stackrel{\rm{}def}{=}6(\alpha-1)$ should work). You will then, by monotone convergence, have $a_n\xrightarrow[n\to\infty]{}\ell \leq 2\alpha-1$.

To show the limit is actually $2\alpha-1$, I suppose (this is very hazy) that a similar approach, but with a convenient lower bound this time, should work.

-
But the solutions of Did and Jack D'Aurizio above are definitely better (that is, "clean" and elegant -- this is not.) – Clement C. Feb 21 '14 at 16:21