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!
 A: (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.
A: It will not converge.  If it converged to a limit $L$, it would solve $$L=L+2^{-L}$$
which has no solution.
A: $$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)
