# How to calculate the general formula for nth term of this recursion?

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!

• 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}})}$ – Ross Millikan Apr 30 at 23:17

(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.

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

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

• 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? – Donny May 1 at 0:04
• It is monotonically increasing, so there can't be an upper bound. If there were it would converge. It goes off to infinity – Ross Millikan May 1 at 0:11

$$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)