Intereting Posts

Is every compact space compactly generated?
Does $i^i$ and $i^{1\over e}$ have more than one root in $$
Categorical Pasting Lemma
Convert from a field extension to an elementary field extension
For every infinite $S$, $|S|=|S\times S|$ implies the Axiom of choice
Find the number of irreducible polynomials in any given degree
Given A Real Vector Space, Any two choices of Basis Gives A Same Topology
Fractional Derivative Implications/Meaning?
Find a minimum of $x^2+y^2$ under the condition $x^3+3xy+y^3=1$
Finding the order of $\mathrm{GL}_n(\mathbb{F}_p)$
Is this division theorem already a proven idea?
If a unit cylinder is dropped on floor, is there equal chances to be horizontal or vertical?
What is the cross product in spherical coordinates?
differential inverse matrix
question about typical proof of Krull Intersection Theorem

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

- How does one solve this recurrence relation?
- Recurrence $a_n = \sum_{k=1}^{n-1}a^2_{k}, a_1=1$
- The $\gcd$ operator commutes with functions defined by linear recurrence relations
- converting a recursive formula into a non-recursive formula.
- An Identity for Pell-numbers
- Solve the reccurence $a_n= 4a_{n−1} − 2 a_{n−2}$

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

- What's the value of this Viète-style product involving the golden ratio?
- How to derive an explicit formula for $\sum \frac{e^{i n \theta}}{n}?$
- Yet another $\sum = \pi$. Need to prove.
- Numbers $p-\sqrt{q}$ having regular egyptian fraction expansions?
- Frobenius method differ by integer
- Explicit formula for Bernoulli numbers by using only the recurrence relation
- Combination of quadratic and cubic series
- Infinite series $\sum _{n=2}^{\infty } \frac{1}{n \log (n)}$
- If $ \lim_{n \to \infty} (2 x_{n + 1} - x_{n}) = x $, then is it true that $ \lim_{n \to \infty} x_{n} = x $?
- explicit formula for recurrence relation $a_{n+1}=2a_n+\frac{1}{a_n}$

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.

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.

$$

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.

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.

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

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.

- $f$ continuous, $f^N$ analytic on a domain D implies $f$ analytic on D
- Convergence of the sequence $\sqrt{1+2\sqrt{1}},\sqrt{1+2\sqrt{1+3\sqrt{1}}},\sqrt{1+2\sqrt{1+3\sqrt{1+4\sqrt{1}}}},\cdots$
- Isometric Embedding of a separable Banach Space into $\ell^{\infty}$
- Euler Totient Issues
- a square root of an irrational number
- Proving that $\mathbb R^3$ cannot be made into a real division algebra (and that extending complex multiplication would not work)
- If a measure is semifinite, then there are sets of arbitrarily large but finite measure
- Prove that $\cos(x)$ doesn't have a limit as $x$ approaches infinity.
- Factoring polynomials of the form $1+x+\cdots +x^{p-1}$ in finite field
- For any integer n greater than 1, $4^n+n^4$ is never a prime number.
- Let $A$ and $B$ be $n \times n$ real matrices such that $AB=BA=0$ and $A+B$ is invertible
- Complex numbers equation: $z^4 = -16$
- How to compute $\lim_{n\rightarrow\infty}e^{-n}\left(1+n+\frac{n^2}{2!}\cdots+\frac{n^n}{n!}\right)$
- Problem on circles, tangents and triangles
- Functions $f$ satisfying $ f\circ f(x)=2f(x)-x,\forall x\in\mathbb{R}$.