Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Is it $$a_n-1\text{ or }a_{n-1}?$$ –  lab bhattacharjee Feb 21 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 at 15:44
    
To "lab bhattacharjee": It is correct the way it is. It is: $a_n-1$ –  FiBO Feb 21 at 15:47
    
To "Squirtle": The limit is 199, not 99. I confirmed this. –  FiBO Feb 21 at 15:48
2  
I think what's confusing is that you have a first-order diff eq'n yet have two initial values. –  Ron Gordon Feb 21 at 16:02
show 10 more comments

6 Answers 6

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.

share|improve this answer
    
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 at 16:37
2  
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 at 16:43
add comment

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

share|improve this answer
    
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 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 at 16:55
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
    
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 at 16:21
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.