2
$\begingroup$

I'm trying to solve the general formula for nth term: $a_n = a_{n-1} + 2^{-a_{n-1}}, a_0 = 0$. And want to if there exists $f(n)$, s.t. $lim_{n\rightarrow \infty}a_n = f(n)$.


First, I've tried to see what do first terms look like:

$a_0 = 0$
$a_1 = 1$
$a_2 = 1.50000000000000$
$a_3 = 1.85355339059327$
$a_4 = 2.13026337562636$
$a_5 = 2.35867953516332$

But I can't find any clue.


Then I tried to directly write down the general formula

$a_1 = 2^{-a_0}$
$a_2 = 2^{-a_0} + (2)^{2^{-a_0}}$
$a_3 = 2^{-a_0} + (2)^{2^{-a_0}} + (2)^{(2)^{2^{-a_0}}}$

In this way, I can definitely write down the general formula in a very silly way. However, I can't see what $f(n)$ would $a_n$ goes to as $n\rightarrow \infty$.


Apparently, it's not arithmetic or geometric sequence. And I don't think the method of characteristic functions would help.

Any hint or detailed steps would be appreciated!

$\endgroup$
  • $\begingroup$ It doesn't change much, but it should be $a_3 = 2^{-a_0} + (2)^{-2^{-a_0}} + (2)^{-(2^{-a_0} + (2)^{-2^{-a_0}})}$ $\endgroup$ – Ross Millikan Apr 30 at 23:17
2
$\begingroup$

(I think I recently answered a similar question. Oh well, here I go again.)

If $a_n = a_{n-1} + c^{-a_{n-1}}, a_0 = 0 $ where $c > 1$, my conjecture is that $a_n \sim \dfrac{\ln(u)}{u}+\dfrac{\ln(n)}{u} $ where $u = \ln(c) $.

I will first show that the $a_n$ are unbounded.

If the $a_n$ are bounded, say $a_n < M$, then $a_n = a_{n-1} + 2^{-a_{n-1}} \gt a_{n-1} + 2^{-M} $ or $a_n - a_{n-1} \gt 2^{-M} $. Summing this, $a_m-a_0 =\sum_{n=1}^m(a_n - a_{n-1}) \gt m2^{-M} $ which is a contradiction for large enough $m$.

If $a_n \sim f(n)$, then $f'(n) \sim c^{-f(n)} = u^{-uf(n)} $ where $u = \ln c$.

Then $f''(n) =(-uf'(n))e^{-uf(n)} =(-uf'(n))f'(n) =-uf'^2(n) $.

Letting $g = f'$, then $g' = -ug^2$ so $\dfrac{-g'}{g^2} =u $ or $(1/g)' = u $ or $1/g = dn+r$ or $g = \dfrac1{dn+r}$.

Therefore $f'(n) = \dfrac1{un+r}$ so

$\begin{array}\\ f(n) &= \int \dfrac{dn}{un+r}\\ &=\frac1{u}\ln(un+r)\\ &=\frac1{u}(\ln(u)+\ln(n+r/u))\\ &=\frac{\ln(u)}{u}+\frac1{u}\ln(n+r/u)\\ \end{array} $

For simplicity's sake I will assume that $r = 0$. Then

$\begin{array}\\ f(n) &=\frac{\ln(u)}{u}+\frac1{u}\ln(n)\\ \text{so}\\ f(n+1) &=\frac{\ln(u)}{u}+\frac1{u}\ln(n+1)\\ &=\frac{\ln(u)}{u}+\frac1{u}(\ln(n)+\ln(1+1/n))\\ &\sim\frac{\ln(u)}{u}+\frac1{u}(\ln(n)+\frac1{n}+O(\frac1{n^2}))\\ &=f(n)+\frac1{u}(\frac1{n}+O(\frac1{n^2}))\\ &=f(n)+\frac1{un}+O(\frac1{n^2})\\ \end{array} $

So we want

$\begin{array}\\ \frac1{un} &\sim c^{-(\ln(u)/u+\ln(n)/u)}\\ &\sim e^{\ln(c)(-\ln(u)/u-\ln(n)/u)}\\ &\sim e^{u(-\ln(u)/u-\ln(n)/u)}\\ &\sim e^{-\ln(u)-\ln(n))}\\ &\sim e^{-\ln(un)}\\ &=\frac1{un}\\ \end{array} $

So it works.

$\endgroup$
  • $\begingroup$ It works very well ! $\endgroup$ – Claude Leibovici May 1 at 6:10
  • 1
    $\begingroup$ I think there is a typo on 6th line. Should be $f'(n) \sim c^{-f(n)} = e^{-uf(n)}$ $\endgroup$ – Donny May 1 at 23:58
  • $\begingroup$ Thanks! This perfectly solved my problem! $\endgroup$ – Donny May 2 at 0:10
  • $\begingroup$ Fortunately, that typo didn't affect anything following. $\endgroup$ – marty cohen May 2 at 11:10
1
$\begingroup$

It will not converge. If it converged to a limit $L$, it would solve $$L=L+2^{-L}$$ which has no solution.

$\endgroup$
  • $\begingroup$ Thanks! I see why it's not convergent. However, I still want to see how big is $a_n$, i.e. to find it's upper bound or lower bound if they exist. It seems $log_2(n)$ is an upper bound. Do you have any advice on finding a good upper/lower bound? $\endgroup$ – Donny May 1 at 0:04
  • $\begingroup$ It is monotonically increasing, so there can't be an upper bound. If there were it would converge. It goes off to infinity $\endgroup$ – Ross Millikan May 1 at 0:11
0
$\begingroup$

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

Note that the difference between $a_n$ and $a_{n-1}$ is given in terms of $a_{n-1}$...

$$a_n-a_{n-1}=\frac{1}{2^{a_{n-1}}}$$

Shift the indices by $1$, and you have a difference equation...

$$\Delta a(n)=\frac{1}{2^{a(n)}}$$

...with initial condition $a(0)=0$.

I know nothing about solving difference equations, but from what you have written and the result I got when I put this into Wolfram Alpha, it has no closed-form solution. (If it does have a closed form solution, it will probably be in terms of the natural logarithm, but again, this is not my area of expertise)

$\endgroup$

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.