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.

  • 1
    Maybe this is obvious, but people sometimes forget obvious methods: try writing out first few terms (10, say) and you might get an idea about how fast they grow. Then you bound the terms by some simple function. If the bound is tight enough to give you a limit (0 in this case) then you proceed to actually *prove* the bound (which may or may not be easy).2010-11-13
  • 0
    that's what I tried by showing $a_{n}\leq n$ but it wasn't tight enough.2010-11-13
  • 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
    I like this better, but unfortunately, I am out of votes for today.2010-11-12
  • 0
    I ended up using Stolz-Cesàro theorem. Because the number of fractions depends on $n$ I can't determine the limit directly, or did you mean something else?2010-11-14
  • 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
    actually the next question is to look at $(a_{n})^2 / n$ ;)2010-11-12
  • 0
    @daniel: That seems to be a harder problem :-) Does it ask to find the limit of $(a_n)^2/n$? Interesting course you are taking there :-)2010-11-12
  • 0
    yes, I was hoping that $a_{n}/n \to 1$ and then it's easy, but guess not :)2010-11-12
  • 0
    perhaps you have a hint for $\frac{(a_{n})^2}{n}$? the closest I got was to show that $\frac{1}{n}\leq \frac{(a_{n})^2}{n} \leq 3$ which implies that if $b_{n}=\frac{(a_{n})^2}{n}$ is monotonic then the limit exists. but still I haven't showed that it's monotonic and even if it is, how do I find its limit?2010-11-13
  • 0
    @daniel: Do you have any guess as to what the limit could be?2010-11-13
  • 0
    testing the first few elements gives me the impression that $\frac{(a_n)^2}{n}$ is increasing, so I'll guess and say 3.2010-11-13
  • 0
    @daniel: 3 is not right. Why don't you try computing a few more values? Did the problem give any hints you could use? What tools do you have available? I am curious though, which course is this? Perhaps a link to the course webpage.2010-11-13
  • 0
    I'm actually not from the US and I can't find a link in English but it's sort of Calculus part 2 with subjects like sequences, series, indefinite integral, Taylor and Maclaurin expansions etc. The question started off by showing $a_{n}\to \infty$, then asks to find $\frac{a_{n}}{n}$ and last $\frac{(a_{n})^2}{n}$2010-11-13
  • 0
    @daniel: I would strongly suggest you try guessing the limit first. Hint for that: read all the answers/comments in this thread again :-) btw, if your professor gives a solution which does not require guessing the solution at all, please let us know. I am curious.2010-11-13
  • 0
    @Moron: I believe I solved it without guessing. The limit I got is 2. Here's what I did: $(a_{n+1})^2=a_{n}^2+2+\frac{1}{a_{n}^2}=2(n-1)+\sum_{k=2}^{n}\frac{1}{a_{n}^2}+a_{1}=2(n-1)+a_{n}$, then we get $\frac{(a_{n+1})^2}{n+1}=\frac{2n-2}{n+1}+\frac{a_{n}}{n+1}\to 2+0=2$.2010-11-14
  • 0
    Also see my own answer for a shorter way2010-11-14
  • 0
    @daniel: How did you get rid if Sum (1/a_k_^2) ? btw 2 is correct :-)2010-11-14
  • 0
    you need a little more steps to get rid of Sum (1/a_k_^2)2010-11-14
  • 0
    hmm, forget that, for some reason I thought that $\sum_{k=1}^{n}\frac{1}{a_k^2}=a_{n+1}$ but the square gets in the way.2010-11-14
  • 0
    @daniel: No need to forget, it actually can be made to work!2010-11-14
  • 2
    @Moron: This is very impressive.2010-11-17
  • 0
    But for example a(n)=sqrt(2n+1.5) fits better at least for moderate n2010-11-17
  • 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}$.