10
$\begingroup$

I started by showing that $1\leq a_{n} \leq n$ (by induction) and then $\frac{1}{n}\leq \frac{a_{n}}{n} \leq 1$ which doesn't really get me anywhere.

On a different path I showed that $a_{n} \to \infty$ but can't see how that helps me.

  • 0
    for sequence (1, 2, 2.5, 2.9, 3.2, 3.6, 3.8, ...) your bound is obviously pretty crude and in particular it doesn't help you at all. You should try to get a crudest bound that will help you (to make proving easier), but no cruder :-) In this case a_n ~ sqrt(2n), so that for any epsilon in [1/2, 1) Kn^{epsilon} is good enough.2010-11-13

6 Answers 6

20

Use $a_{n+1} = \frac{1}{a_n} + \frac{1}{a_{n-1}} + \cdots + 1$ and $a_n \longrightarrow \infty$.

  • 0
    For every \epsilon > 0, from some point on, all summands $1/a_n$ are smaller than $\epsilon$, so the sum is at most $\epsilon n + C_\epsilon$.2010-11-14
12

I completely forgot about the Stolz-Cesàro theorem, from which we get:

$\lim_{n\to \infty} \frac{a_n}{n}=\lim_{n\to\infty} \frac{a_{n+1}-a_{n}}{(n+1)-n}=\lim_{n\to \infty}\frac{\frac{1}{a_{n}}}{1}=\lim_{n\to \infty}\frac{1}{a_{n}}=0. $ The same technique works for $\displaystyle \frac{a_{n}^2}{n}.$

  • 0
    Very interesting. Well done :-)2010-11-14
9

Now that the homework is solved, here is some more investigation into this interesting sequence.

I think we can show that $\displaystyle a_{n}^2 \sim 2n + \dfrac{\log n}{2} - C$ for some constant $\displaystyle C \gt 0$

By $\displaystyle x_n \sim y_n$ I mean $\displaystyle \lim_{n \to \infty} (x_n - y_n) = 0$

Consider $b_n = a_{n}^2 - 2n$

Then we have that $\displaystyle b_{n+1} = b_n + \dfrac{1}{b_n + 2n}$

Notice that $b_3 \gt 0$ and thus for sufficiently large $\displaystyle n$, $\displaystyle b_n \gt 0$.

It is also easy to show that $\displaystyle b_n \lt 2n$. In fact, we can easily show that $b_n \lt \log n$

Now we have that, for sufficiently large $\displaystyle m,n$

$\displaystyle b_{m+1} - b_n = \sum_{k=n}^{m} \dfrac{1}{b_k + 2k}$

Since $\displaystyle 0 \lt b_k \lt \log k$

we have that

$\displaystyle \sum_{k=n}^{m} \dfrac{1}{2k} \gt b_{m+1} - b_n \gt \sum_{k=n}^{m} \dfrac{1}{2k}(1- \dfrac{b_k}{2k})$

(Here we used $\displaystyle \dfrac{1}{1+x} \gt \ \ 1-x, 1 \gt x \gt 0$)

Now Since $b_k \lt \log k$, we have that

$\displaystyle \sum_{k=n}^{m} \dfrac{1}{2k} \gt b_{m+1} - b_n \gt \sum_{k=n}^{m} \dfrac{1}{2k} - \sum_{k=n}^{m} \dfrac{\log k}{4k^2}$

Using the fact that $\displaystyle H_m - H_n = \log(\dfrac{m+1}{n}) + O(\dfrac{1}{n} - \dfrac{1}{m})$, where $\displaystyle H_n = \sum_{k=1}^{n} \dfrac{1}{k}$ is the $\displaystyle n^{th}$ harmonic number.

We see that,

if $c_n = b_n - \dfrac{\log n}{2}$, then

$\displaystyle O(\dfrac{1}{n} -\dfrac{1}{m}) \gt c_{m+1} - c_n \gt O(\dfrac{1}{n} -\dfrac{1}{m}) -\sum_{k=n}^{m} \dfrac{\log k}{4k^2}$

Now $\displaystyle \sum_{k=1}^{\infty} \dfrac{\log k}{k^2}$ is convergent and so by the Cauchy convergence criteria, we have that $\displaystyle c_n$ is convergent.

Thus the sequence $\displaystyle a_{n}^2 - 2n - \dfrac{\log n}{2}$ converges and hence, for some $\displaystyle C$ we have that

$\displaystyle a_{n}^2 \sim 2n + \dfrac{\log n}{2} - C$

or in other words

$\displaystyle a_{n} \sim \sqrt{2n + \dfrac{\log n}{2} - C}$

A quick (possibly incorrect) computer simulation seems to show a very slow convergence to $\displaystyle C = 1.47812676429749\dots$


The previous answer:

Hint: Consider $(a_n)^2$ and try to apply similar reasoning as you did for $a_n$.

  • 0
    @Martin: Thanks! Yeah, the convergence is very slow. We could likely give a better formula which is more accurate even for small n.2010-11-17
5

As $a_{n+1}^2 = a_n^2 + 2 + \frac{1}{a_n^2}$, we know that

$ a_{n+1}^2 \leq a_n^2 + 3 $

If $a_n^2 \leq 3n$, then $a_{n+1}^2 \leq 3(n+1) $, and since $a_1^2 = 1 \leq 3$, by the induction hypothesis $a_n^2 \leq 3n$

Thus, $\frac{a_n^2}{n^2} \leq 3/n$ for all $n$, and hence

$\lim_{n \rightarrow \infty} \frac{a_n^2}{n^2} = 0$

from this it follows though that

$\lim_{n \rightarrow \infty} \frac{a_n}{n} = 0$.

4

Lets rewrite:

$\frac{a_{n+1}-a_n}{n+1-n}=\frac{1}{a_n}$

Now, as n goes to infinity lets denote $a_n=f$ .Then approximately:

$\frac{d f}{dn}=\frac{1}{f}$

After integrating:

$\frac{f^2}{2}=n+c=>\frac{f^2}{n^2}=\frac{2}{n}+\frac{c}{n^2}$

  • 1
    +1: Even though this seems like nonsensical math, Donald J Newman actually suggests using this as a quick method to get an idea of the rough asymptotic behaviour of a series.2010-11-13
3

Hint: prove by induction that $a_n \leq 2\sqrt{n}$.