x + 1/x

perfect_radio

Let $a_0=1$ , $a_{k+1}=a_k+\frac{1}{a_k}$ , $\forall k \in \mathbb{N}_0$ .

a) Prove that $\lim_{k \to \infty} a_k=\infty$ . (there are at least three methods to prove this)

(the part in which i'm more interested) b) Find some good bounds for $a_k$ (actually two of the solutions i know use some weak lower / upper bound for $a_k$ - let's see if you can do better)

**Posted:** Fri Sep 16, 2005 11:24 am

_________________
"Germany has offered to send troops to the Lebanon border. I bet Israel's breathing a sigh of relief there. Nothing makes Jewish people feel safer and more secure than the German Army marching on their border."

Kent Merryfield

Here's the cheapest answer to part a): This sequence is clearly increasing, hence it either converges or tends to infinity. If it converges to a limit $x,$ then $x$ satisfies the equation $x+\frac1x=x.$ Since that has no real solution, convergence is not possible; thus $\lim_{k\to\infty}a_k=\infty.$

Not very satisfying, is it? In particular, this proof leaves us absolutely no insight for part b) - yes, the sequence goes to infinity, but we don't know how fast.

For a different intuitive approach, consider this:
$a_{k+1}-a_k=\frac1{a_k}$
is a difference equation that approximates (by the Euler method of approximation) the differential equation
$y'=\frac1y.$
This differential equation is readily solved by separation of variables; the solutions are $y=\sqrt{2x+C}.$ Hence we should look for estimates that say that for large $k,\,a_k$ behaves asymptotically like $\sqrt{2k}.$

That's not very rigorous, so far. I invite others to sharpen it.

**Posted:** Fri Sep 16, 2005 12:30 pm

Kent Merryfield

Here's another step in the process, albeit still a long ways from a complete answer.

Suppose $a_k=\sqrt{2k+b_k}.$

In other words, define $b_k=a_k^2-2k.$

Algebraic manipulation of the recursive formula gives us

$b_{k+1}=b_k+\frac1{a_k^2},$ or $b_{k+1}=b_k+\frac1{b_k+2k}.$

This is another strictly increasing sequence. Hence we have the following lower bound:

For $k>2,\,a_k>\sqrt{2k}.$

I believe that $b_k\to\infty,$ at a rate that is nearly logarithmic. Nailing that down would sharpen our estimates.

**Posted:** Fri Sep 16, 2005 1:11 pm

perfect_radio

**Posted:** Fri Sep 16, 2005 2:11 pm

_________________
"Germany has offered to send troops to the Lebanon border. I bet Israel's breathing a sigh of relief there. Nothing makes Jewish people feel safer and more secure than the German Army marching on their border."

Kent Merryfield

**Posted:** Fri Sep 16, 2005 2:42 pm

Ravi B

Yes, by using your previous recurrence, we can show that $b_k - \frac{1}{2} \ln k$ approaches a constant.

By the way, at the very beginning, it helps to square the original recurrence:
$a_{k+1}^2 = a_k^2 + \frac{1}{a_k^2} + 2 \, .$
If we let $s_k = a_k^2$ , we get the nice recurrence
$s_{k + 1} = s_k + 2 + \frac{1}{s_k} \, .$
That's a quick way to see that $s_k \sim 2k$ .

**Posted:** Fri Sep 16, 2005 4:43 pm

perfect_radio

**Posted:** Sat Sep 17, 2005 3:05 am

_________________
"Germany has offered to send troops to the Lebanon border. I bet Israel's breathing a sigh of relief there. Nothing makes Jewish people feel safer and more secure than the German Army marching on their border."

Ravi B

Inspired by Kent's recurrence for $b_k$ , let's define a simpler recurrence
$c_{k + 1} = c_k + \frac{1}{2k+1} \, ,$
with $c_0 = 1$ . That recurrence has solution
$c_k = 1 + \sum_{i = 0}^{k-1} \frac{1}{2i+1} \, .$
From results about the harmonic series, it is known that $c_k - \frac{1}{2} \ln k$ approaches a constant (involving Euler's constant).

By comparing the recurrences for $b_k$ and $c_k$ , we see that $b_k \le c_k$ . Let's examine the difference $d_k = c_k - b_k$ . By subtracting the recurrences for $b_k$ and $c_k$ , we get the recurrence
$\begin{eqnarray*} d_{k+1} & = & d_k + \frac{1}{2k+1} - \frac{1}{2k + b_k} \\ & = & d_k + \frac{b_k - 1}{...$
From that recurrence, we see that $d_k$ is an increasing sequence. By summing up, we get the equation
$d_k = \sum_{i = 0}^{k-1} \frac{b_i - 1}{(2i+1)(2i + b_i)} \, .$
Because $1 \le b_i \le c_i = O(\ln i)$ , we get
$d_k = \sum_{i = 0}^{k-1} \frac{O(\ln i)}{(2i+1)^2} = O(1) \, .$
In other words, $d_k$ is bounded. A bounded, increasing sequence must approach a limiting constant. That's what we wanted to show.

**Posted:** Sat Sep 17, 2005 1:09 pm

perfect_radio

**Posted:** Mon Sep 19, 2005 1:08 am

_________________
"Germany has offered to send troops to the Lebanon border. I bet Israel's breathing a sigh of relief there. Nothing makes Jewish people feel safer and more secure than the German Army marching on their border."

Ravi B

Define the usual harmonic series
$H_n = \sum_{i = 1}^n \frac{1}{i} \, .$
It is known that $H_n - \ln n$ approaches a constant, the Euler (or Euler-Mascheroni) constant. You can prove that result by comparing the harmonic series to the integral
$\int_1^n \frac{1}{x} \, dx = \ln n \, .$
I'm not going to give a proof here; it's a classical result.

Anyway, we can express the sum of odd reciprocals in terms of harmonic numbers:
$\sum_{i=0}^{k - 1} \frac{1}{2i+1} = H_{2k} - \frac{1}{2} H_k \, .$
So from the estimate on harmonic numbers, we get the estimate for our sum.

**Posted:** Mon Sep 19, 2005 3:55 am

perfect_radio

I am really dumb... I knew this result, $\ln (n+1) < H_{n}< 1+\ln n$ , and also how to prove it (considering some rectangles + integrals).

I have found that on the net that the existence of the constant can also be proven in the same way. (actually it gave the same hint as Ravi B + a nice drawing).

So, draw the graph of $x \mapsto \frac{1}{x}$ . Also draw the "big" and "small" rectangles coresponding to every pair $\{n,n+1\}$ . Let $D_{i}$ be the "difference" rectangles between the big and the small ones. Then we have $\sum_{i=1}^{n}\frac{1}{i(i+1)}= \sum_{i=1}^{n}\left( \frac{1}{i}-\frac{1}{i+1}\right) = 1-\frac{1}{n+1}$ , so $\textrm{Area of all }D_{i}\textrm{ rectangles}= \sum_{i=1}^{\infty}\frac{1}{i(i+1)}= 1$ .

Consider the sets $F_{i}$ formed by the $D_{i}$ rectangles and the graph of $x \mapsto \frac{1}{x}$ (the lower side). Thus, $\sum_{i=1}^{n}F_{i}= 1+\ln n-H_{n}$ . This sum increases at each step, and is bounded by $1$ , thus, it is convergent...

i know the presentation is not the most fortunate, but, did I got it right?

_________________
"Germany has offered to send troops to the Lebanon border. I bet Israel's breathing a sigh of relief there. Nothing makes Jewish people feel safer and more secure than the German Army marching on their border."

alon

**Posted:** Mon Sep 19, 2005 11:08 pm

Ravi B

**Posted:** Thu Sep 22, 2005 7:00 am