Conjecture on the growth of $q_1 = 1, q_{n+1}=q_n + f(q_n) $

37 Views Asked by At

This is a generalization of my answer to Calculate the limit of the following recurrent series in the form suggested by Will Jagy.

$q_1 = 1, q_{n+1}=q_n + f(q_n) $ where $f(x) > 0$ and $f'(x) < 0$.

I show that $q_n$ is unbounded and derive a conjecture for the growth of $q_n$ as a function of $f(x)$.

To make my question explicit (since some people seem to want that):

Is my conjecture on the growth of $q_n$ true?

My conjecture for $f(x) = \dfrac{a}{x^b} $ is $q_n \approx (a(b+1)n)^{1/(b+1)} $ and for $f(x) = \dfrac{a}{b^x} $ is $q_n \approx \dfrac{\ln(a\ln(b)n)}{\ln(b)}$.

First, a proof that $q_n$ is unbounded.

$q_n > 1$ for $n > 1$ and $q_n$ is increasing.

If $q_n$ is bounded, there is an $L$ such that $q_n \le L$ for all $n$ so that, since $f'(x) < 0$, $f(q_n) \ge f(L)$.

Writing $q_{n+1}=q_n + f(q_n) $ as $q_{n+1}-q_n = f(q_n) $ and summing

$\begin{array}\\ q_{n+1}-q_1 &=\sum_{k=1}^n (q_{k+1}-q_k)\\ &=\sum_{k=1}^n f(q_k)\\ &\ge\sum_{k=1}^n f(L)\\ &= nf(L)\\ \end{array} $

which is unbounded, a contradiction.

Now to get an estimate for $q_n$ in terms of $f(x)$.

Suppose $q_n = g(n)$ where $g$ is a reasonably smooth function (i.e., has at least a first derivative). Then

$\begin{array}\\ q_{n+1}-q_n &=g(n+1)-g(n)\\ &=g'(n+c) \qquad\text{where } 0 \le c \le 1\\ &\approx g'(n) \qquad\text{this is the big assumption}\\ \end{array} $

Therefore $g'(n) \approx f(q_n) =f(g(n)) $.

This is the functional equation that $g$ has to satisfy.

For example, if $f(x) = \frac{2}{x}$ as in the original problem, the equation is $g'(n) =\frac{2}{g(n)} $ so $2 = g(n)g'(n) =\frac12(g^2(n))' $. Integrating, $4n+c =g^2(n)$ so $g(n) = 2\sqrt{n+c_1} $. This agrees with my conjecture in my answer to the original question.

More generally, if $f(x) = ax^{-b}$ where $a, b > 0$, the equation is $g'(n) =a(g(n))^{-b} $ or $a = g'g^b =\frac1{b+1}(g^{b+1})' $.

Integrating, $a(b+1)n+c =g^{b+1}(n) $ so $g(n) =(a(b+1)n+c)^{1/(b+1)} $.

As a check, simplifying with $c=0$, $g(n) = (a(b+1)n)^{1/(b+1)}$ so

$\begin{array}\\ g(n+1)-g(n) &=(a(b+1)(n+1)^{1/(b+1)}-(a(b+1)n)^{1/(b+1)}\\ &=(a(b+1)n)^{1/(b+1)}((1+1/n)^{1/(b+1)}-1)\\ &=(a(b+1)n)^{1/(b+1)}(\frac1{(b+1)n}+O(\frac1{n^2}))\\ &=a^{1/(b+1)}((b+1)n)^{1/(b+1)-1}+O(\frac1{n^{2-1/(b+1)}})\\ &=a^{1/(b+1)}((b+1)n)^{-b/(b+1)}+O(\frac1{n^{2-1/(b+1)}})\\ &=\dfrac{a^{1/(b+1)}}{((b+1)n)^{b/(b+1)}}+O(\frac1{n^{1+b/(b+1)}})\\ \text{and}\\ f(g(n)) &=\dfrac{a}{g^b(n)}\\ &=\dfrac{a}{((a(b+1)n)^{1/(b+1)})^b}\\ &=\dfrac{a}{(a(b+1)n)^{b/(b+1)}}\\ &=\dfrac{a^{1/(b+1)}}{((b+1)n)^{b/(b+1)}}\\ \end{array} $

Another class of functions, suggested by Will Jagy, is $f(x) = \frac{a}{b^x}$ where $a > 0, b > 1$, the equation is $g'(n) =\frac{a}{b^{g(n)}} $ or $a = g'b^g = g'e^{g\ln(b)} =\frac1{\ln(b)}(e^{g\ln(b)})' =\frac1{\ln(b)}(b^g)' $.

Integrating, $a\ln(b)n+c =b^g $ so $g(n)\ln(b) =\ln(a\ln(b)n+c) $ or $g(n) =\dfrac{\ln(a\ln(b)n+c)}{\ln(b)} $.

If $a=1, b = e$ as in Will Jagy's example, $g(n) =\ln(n+c) $.

To check, if $c = 0$, $g(n) = \dfrac{\ln(a\ln(b)n)}{\ln(b)}$ so

$\begin{array}\\ g(n+1)-g(n) &=\dfrac{\ln(a\ln(b)(n+1))}{\ln(b)}-\dfrac{\ln(a\ln(b)n)}{\ln(b)}\\ &=\dfrac1{\ln(b)}(\ln(a\ln(b)(n+1))-\ln(a\ln(b)n))\\ &=\dfrac1{\ln(b)}\ln(1+1/n))\\ &=\dfrac1{n\ln(b)}+O(\frac1{n^2})\\ \text{and}\\ f(g(n)) &=\dfrac{a}{b^{g(n)}}\\ &=\dfrac{a}{b^{\frac{\ln(a\ln(b)n)}{\ln(b)}}}\\ &=\dfrac{a}{a\ln(b)n}\\ &=\dfrac1{\ln(b)n}\\ \end{array} $