3

I want to study the asymptotic behavior of the following recurrence relation:

$y_1=1$;

$y_{n+1}=y_n+\left(1+\frac{y_n}{n}\right)^{-n}$ for $n\ge 1$.

I made an initial attempt and guessed that $y_n∼Log(n)$. Any referrence or hint about this might be helpful. Any help will be greatly appreciated.

Jack
  • 33
  • What was included in your initial attempt? Note that $y_1=1$, but $\log(1)=0$. Can you think of a related function that matches the initial condition? – Mark Viola Apr 25 '15 at 02:12
  • 1
    @Dr. MV: Doesnt matter whether or not the asymptotic matches the initial condition. – themaker Apr 25 '15 at 02:17
  • @themaker Yes, that is correct ... $\log(n)$ and $\log(n+1)$ are asymptotically (large $n$) the same. With $\log(n+1)-\log(n) =O(n^{-1})$. I am only prompting thinking here. – Mark Viola Apr 25 '15 at 02:20

1 Answers1

0

Let $a_n=\frac{y_n}{\log{n}}$ when $n\ge 2$. Now we will show by induction that $a_n> 1$. This is because $a_2=3/(2\log{2})>1.$ Suppose $a_n>1$, we will show that $a_{n+1}>1$. This is because the function $$f_n(x)=\frac{1}{\log{(n+1)}}\left\{x\log{n}+\left(1+\frac{\log{n}}{n}x\right)^{-n}\right\}$$ is increasing when $x>0$(by computing its derivative.) Now $$a_{n+1}=f_n(a_n)>f_n(1)=\frac{1}{\log{(n+1)}}\left\{\log{n}+\left(1+\frac{\log{n}}{n}\right)^{-n}\right\}.$$ To show $a_{n+1}>1$ it suffices to show $$\left(1+\frac{\log{n}}{n}\right)^{-n}>\log\left(1+\frac{1}{n}\right).$$ Note when $x>0$ the inequality holds: $$\log(1+x)<x.$$ Thus $$\left(1+\frac{\log{n}}{n}\right)^{-n}=\exp\left(-n\log\left(1+\frac{\log{n}}{n}\right)\right)>\exp\left(-n\frac{\log{n}}{n}\right)=\frac{1}{n}>\log\left(1+\frac{1}{n}\right).$$ Once again, we may use similar technique to show that $b_n=\frac{y_n}{\log(n)+1}<1$.

Addendum Let $g_n(x)=\frac{1}{\log(n+1)+1}\left\{x(\log n+1)+\left(1+\frac{\log{n}+1}{n}x\right)^{-n}\right\}.$ Also, we see that $$b_{n+1}=g_n(b_n)<g_n(1)=\frac{1}{\log(n+1)+1}\left\{(\log n+1)+\left(1+\frac{\log{n}+1}{n}x\right)^{-n}\right\}.$$ It suffices to prove that $$\left(1+\frac{\log{n}+1}{n}x\right)^{-n}=\exp\left(-n\log\left(1+\frac{\log{n}+1}{n}\right)\right)< \log\left(1+\frac{1}{n}\right).$$ Consider the inequality $\log(1+x)>x-x^2/2$. We see that $$\exp\left(-n\log\left(1+\frac{\log{n}+1}{n}\right)\right)<\exp\left(-n\left(\frac{\log{n}+1}{n}-\frac{(\log{n}+1)^2}{2n^2}\right)\right)=\frac{1}{en}\exp\left(\frac{(\log{n}+1)^2}{2n}\right)<\frac{1}{n}-\frac{1}{2n^2}$$ The last inequality is because by taking derivative, and note that $n$ is integer $$\frac{(\log{n}+1)^2}{2n}\le \frac{(\log 3+1)^2}{6}.$$ Also, this implies $$\exp \frac{(\log{n}+1)^2}{2n} \le \exp \frac{(\log 3+1)^2}{6}<2.1 $$ Thus, we only need to prove $$\frac{2.1}{en}<\frac{1}{n}-\frac{1}{2n^2}$$ which holds when $n\ge 3$. But we can check that $b_1,b_2,b_3$ all less than $1$. Thus we are done.

Golbez
  • 4,276
  • Thanks. When proving $b_n<1$, what inequality would be applied to obtain that $\left(1+\frac{1+Log(n)}{n}\right)^{n}>n+1$? – Jack Apr 25 '15 at 14:47
  • @Jack Sorry for being too concise. I used to think that $\log{n}+1$ is almost the same, but actually it needs more estimates. – Golbez Apr 25 '15 at 15:44