# Problem of finding the limit of reductive sequence

Let $\lbrace u_n \rbrace$ be a sequence defined by : $u_1=1$, $u_{n+1}=u_{n}+\dfrac{u_{n}^{2}}{a}$ for a be a positive real constant. Find : $\text{lim}_{n\rightarrow \infty}\left(\dfrac{u_1}{u_2}+...+\dfrac{u_n}{u_{n+1}}\right)$

If I denote $S_n$ by $\dfrac{u_1}{u_2}+...+\dfrac{u_n}{u_{n+1}}$ then $S_n$ is increasing sequence, but I could not prove that it is bounded above. May be $\text{lim}_{n\rightarrow \infty} S_n =\infty$ ?

-
Why would we want to do this? – Gerry Myerson Nov 6 '12 at 6:09
Numerical evidence strongly suggests that the limit is exactly $a$, which I cannot figure out currently. – Sangchul Lee Nov 6 '12 at 7:59

Shortly after finishing the proof, I realized that it is sufficient to observe the following identity

$$\sum_{k=1}^{n} \frac{u_k}{u_{k+1}} + \frac{a}{u_{n+1}} = a$$

and the fact that $u_{n} \to \infty$ as $n\to\infty$. Indeed,

$$\frac{a}{u_n} = \frac{u_n + a}{u_n + \frac{u_n^2}{a}} = \frac{u_n + a}{u_{n+1}} = \frac{u_n}{u_{n+1}} + \frac{a}{u_{n+1}}$$

and since $u_1 = 1$, the identity follows. Then by noting that

$$u_{n} \geq u_{n-1}^2 \geq \cdots \geq (u_2)^{2^{n-2}} \to \infty \quad \text{as} \quad n\to\infty,$$

the conclusion follows.

I leave my old and sophisticated proof, which served a motivation.

Finally I succeeded in proving my observation that

$$\sum_{n=1}^{\infty} \frac{u_n}{u_{n+1}} = a.$$

Step 0. Notation

By the substitution $u_n = \dfrac{a}{x_n}$, we have $$x_1 = a, \qquad x_{n+1} = \frac{x_n^2}{1+x_n}, \qquad \frac{u_n}{u_{n+1}} = \frac{x_{n+1}}{x_n}.$$ We denote $x_n = x_n(a)$ whenever the dependence of the sequence $(x_n)$ on the variable $a$ is required. Then we denote the limit as

$$s(a) := \sum_{n=1}^{\infty} \frac{u_n}{u_{n+1}} = \sum_{n=1}^{\infty} \frac{x_{n+1}(a)}{x_{n}(a)} \tag{1}$$

Since each summand is non-negative, it either converges absolutely or diverges to $+\infty$.

Step 1. Convergence and simple estimation of $s(a)$

Let $g(x)$ and $h(x)$ be functions defined on $x > 0$ by

$$g(x) = \frac{x^2}{1+x} \quad \text{and} \quad h(x) = \frac{g(x)}{x} = \frac{x}{1+x}.$$

One the one hand, since $0 < h(x) < 1$,

$$x_{n+1} = h(x_n) x_n < x_n$$

and $(x_n)$ decreases and converges to $0$ as $n \to \infty$. Then from the observation that $h(x)$ is an increasing function, we have

$$x_{n+1} = h(x_n) x_n \leq h(x_1) x_n.$$

Inductively applying this inequality we obtain

$$x_n \leq h(x_1)^{n-1} x_1 = \left(\frac{a}{1+a}\right)^{n-1} a.$$

On the other hand,

$$x_{n+1} \leq x_{n}^2 \leq \left(\frac{a}{1+a}\right)^{n-1} a x_n.$$

Therefore we have

$$s(a) \leq \sum_{n=1}^{\infty} \left(\frac{a}{1+a}\right)^{n-1} a = a + a^2.$$

In particular, the defining summation $(1)$ converges absolutely. Since

$$s(a) \geq \frac{x_2(a)}{x_1(a)} = \frac{a}{1+a} \geq a - a^2,$$

we obtain the following estimate:

$$\left| s(a) - a \right| \leq a^2. \tag{2}$$

Step 2. Further estimation

Since $x_{n+1} = g(x_n)$, we have $x_{n+1}(a) = x_{n}(g(a))$. This gives the following identity:

$$s(a) = \frac{x_{2}(a)}{x_{1}(a)} + \sum_{n=1}^{\infty} \frac{x_{n+1}(g(a))}{x_{n}(g(a))} = \frac{a}{1+a} + s\left(\frac{a^2}{1+a}\right). \tag{3}$$

Now we claim the following estimation:

$$\left| s(a) - a \right| \leq a^{2^n} \quad \text{for all} \quad a > 0 \text{ and } n \geq 1. \tag{4}$$

The case $n = 1$ reduces to $(2)$, hence is true for the initial case $n = 1$. Thus assume that $(4)$ holds for $n$. By $(3)$,

$$\left| s(a) - a \right| = \left| \frac{a}{1+a} + s\left(\frac{a^2}{1+a}\right) - a \right| = \left| s\left(\frac{a^2}{1+a}\right) - \frac{a^2}{1+a} \right| \leq \left(\frac{a^2}{1+a}\right)^{2^n} \leq a^{2^{n+1}}.$$

Therefore $(4)$ holds for $n+1$, and consequently for all $n$ by mathematical induction.

Step 3. Proof of the main claim

Now we claim that $s(a) = a$ for all $a > 0$. Let us first consider the case $a \in (0, 1)$. Then taking $n \to \infty$ to the estimation $(4)$, we have $s(a) = a$.

Now we consider the case $a \geq 1$. Then note that $(3)$ can be written as

$$s(a) = \frac{x_2(a)}{x_1(a)} + s(x_2(a)).$$

Thus inductively applying this identity, we obtain

$$s(a) = \sum_{k=1}^{m-1} \frac{x_{k+1}(a)}{x_k(a)} + s(x_m(a)).$$

But we know that $x_m(a) < 1$ for large $m$. Thus with such $m$, the previous result implies

$$s(a) = \sum_{k=1}^{m-1} \frac{x_{k+1}(a)}{x_k(a)} + x_m(a).$$

But since

$$\frac{x_{k+1}}{x_k} + x_{k+1} = h(x_k) + g(x_k) = x_k,$$

the above sum reduces to $s(a) = a$ as desired, completing the proof. ////

-
:I'm having trouble following some of your calculations. I can see that $h(x)$ is an increasing function. You state, in your answer, that: $x_{n+1}=h(x_n)x_n \le h(x_1)x_n$. Shouldn't this be $x_{n+1}=h(x_n)x_n \ge h(x_1)x_n$? What am I missing? Could you please help? I really think your proof is pretty amazing, and I'd like to try to understand all of it... – Matt Groff Nov 6 '12 at 21:06
@MattGroff, we observed that $(x_n)$ is decreasing. Thus $x_n \leq x_1$ and $h(x_n) \leq h(x_1)$. – Sangchul Lee Nov 6 '12 at 23:08
Thank you very much. – Matt Groff Nov 7 '12 at 5:46

Note the relation $u_{n+1} = u_n(1+ \frac{u_n}{a})$

So, $\frac{u_n}{u_{n+1}}=\frac{a}{a+u_n}$

The first observation is that $u_n$ is a very rapidly growing series, at least as fast as an exponential. An exponential multiplies its previous term by a constant, while $u_n$ is more than squaring its predecessor(which will be > 1).

Consider another series, $v_n = 2^n-a$. As $u_n$ grows faster than $v_n$, there will be some value of $n$, say $n_0$, satisfying $u_n >v_n \forall n>n_0$.This is a fundamental concept from asymptotic analysis of algorithms.

Putting all the pieces together: $\forall n>n_0, \frac{a}{a+u_n}<\frac{a}{a+v_n}=\frac{a}{2^n}$

So, $\sum_{n=n_0}^{\infty}\frac{u_n}{u_{n+1}}<\sum_{n=n_0}^{\infty}\frac{a}{2^n} = \frac{a}{2^{n_0-1}}$

So, your series is bounded, and it converges. Calculating the exact bound will require finding the value of $n_0$, which can be done easily by a computer, but is complicated analytically.

For such a rapidly growing series, the convergence will be extremely fast, so expect a low $n_0$ unless a is really big.

-