3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Mark Viola Apr 25 '15 at 2:12
  • 1
    $\begingroup$ @Dr. MV: Doesnt matter whether or not the asymptotic matches the initial condition. $\endgroup$ – themaker Apr 25 '15 at 2:17
  • $\begingroup$ @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. $\endgroup$ – Mark Viola Apr 25 '15 at 2:20
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Jack Apr 25 '15 at 14:47
  • $\begingroup$ @Jack Sorry for being too concise. I used to think that $\log{n}+1$ is almost the same, but actually it needs more estimates. $\endgroup$ – Golbez Apr 25 '15 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.