1

$f(n+1) = f(n) + f(n)^{a}$ where $a \in (0,1)$ and $n \ge 1$ with $f(1) = m$.

If $a=0$, we see $f(n) = m + n - 1$ and if $a=1$, we see $f(n) = 2^{n-1}m$. So the recursion seems to interpolate between linear and exponential forms.

Is there a closed form or tight approximation or tight asymptotics for $f(n)$ in terms of $n$, $a$ and $m$?

Update after leshik's answer

Can the same asymptotics hold if $a \ge 1$? What is the asymptotics/tight approximation/exact expression if $a \ge 1$?

Turbo
  • 6,221
  • the asymptotic is $(1-a)^{1/1-a}n^{\frac{1}{1-a}}$ unless I made a stupid mistake. – leshik May 23 '13 at 11:29
  • The answer to the updated question is - no. The dominant term will be $f^a(n)$ so $f(n)$ will grow exponentially. – leshik May 23 '13 at 16:31
  • @leshik Is there a way to express the exponential series as well? – Turbo May 23 '13 at 16:32
  • It has to be something of the form $e^{\alpha a^n}.$ You can use the same arguments as I described in my answer to your original question. – leshik May 23 '13 at 16:47

1 Answers1

2

We "guess" the asymptotic by making use of Stolz-Cesaro theorem. The idea is to show that the sequence behaves like $n^{\alpha}$ for an appropriate choice of $\alpha.$ By Stolz- Cesaro, $$A=\lim_{n\to\infty}\frac{x_{n+1}}{(n+1)^{\alpha}}=\lim_{n\to\infty}\frac{x_{n+1}-x_n}{(n+1)^{\alpha}-n^{\alpha}}=\lim_{n\to\infty}\frac{x_n^a}{\alpha n^{\alpha-1}}=\frac{1}{\alpha}\lim_{n\to\infty}\left(\frac{x_n}{ n^{{\alpha-1}/a}}\right)^a.$$
Now, we want to have $\frac{\alpha-1}{a}=\alpha$ or $\alpha=\frac{1}{1-a}.$ The equation for our limit can be rewritten as $A=\frac{1}{\alpha}A^a$ which gives $A=(1-a)^{\frac{1}{1-a}}.$

leshik
  • 4,850