How to find $\lim a_n$ if $ a_{n+1}=a_n+\frac{a_n-1}{n^2-1} $ for every $n\ge2$

Question

$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?

Answer 1

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.

Answer 2

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$$

Answer 3

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.

Answer 4

To find $a_n$ for every $n\geqslant2$, one can use the following trick:

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$, $$ b_n=A_n\cdot b_2$$ where $$A_n=\prod_{k=2}^{n-1}\frac{k^2}{k^2-1}. $$ that is, $$a_n=1+A_n\cdot(a_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. $$

Answer 5

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.

Answer 6

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.