Putnam 2006 - Exercise B.6 - Alternative solution verification and questions about generalizations CONTEXT
Here is the orginal problem statement.

Let $k$ be an integer greater than 1. Suppose $a_0 > 0$, and define
$$
a_{n+1} = a_n + \frac{1}{\sqrt[k]{a_n}}
$$
for $n > 0$. Evaluate
$$
\lim_{n \to \infty} \frac{a_n^{k+1}}{n^k}.
$$**


PROPOSED SOLUTION

*

*Note that for $n>0$
$$a_n \geq a_0 + \frac1{\sqrt[k]{a_0}}\sum_{j=1}^n \frac1{\sqrt[k]{j}},$$
and hence $(a_n)$ diverges.

EDIT. As pointed out in comment, this step is not correct. I am working on an alternative approach.
EDIT 2. A nice approach is proposed in the comment by Thomas Andrews


*Define $b_n = a_n^{\frac{k+1}k}$. (Observe that $(b_n)$, too, is divergent.) Now, we have \begin{eqnarray}\lim_{n\to \infty}(b_{n+1}-b_n)&= &\lim_{n\to \infty}\left(a_n+a_n^{-\frac1{k}}\right)^{\frac{k+1}k}-a_n^{\frac{k+1}k}=\\&=&\lim_{n\to\infty} \frac{\left(1+a_n^{-\frac{k+1}k}\right)^{\frac{k+1}k}-1}{a_n^{-\frac{k+1}k}}=\frac{k+1}{k},\end{eqnarray}where the fundamental limit$$\frac{(1+\alpha)^m-1}{\alpha}\to m, \ \ \ \mbox{for} \ \ \alpha\to 0$$has been used.

*By Stolz-Cesàro Theorem, we have $$\lim_{n\to\infty}\frac{b_n}{n} = \frac{k+1}k,$$
and hence $$\lim_{n\to\infty} \frac{a_n^{k+1}}{n^k} = \left(\frac{k+1}k\right)^k.$$
$\blacksquare$

QUESTIONS

*

*Is my solution correct?

*Is it correct to state that the solution is valid also for any real number $k\geq 1$?

*Can we further generalize? For example: what can be stated for $0<k<1$, maybe with some restriction on $a_0$?

 A: Step (1) was a bit hand-wavy. The rest of the argument looks fine.
A replacement for step 1
Since $a_n$ is increasing, it must converge or be divergent to $+\infty.$
If $a_n$ converges to $a>0,$ then $$\sum_{n=0}^{\infty}(a_{n+1}-a_n)$$ converges to $a-a_0,$ and thus $1/a_n^{1/k}=a_{n+1}-a_n\to 0.$ But $1/a_n^{1/k}\to\frac1{a^{1/k}}\neq 0,$ which is a contradiction.
So $a_n$ diverges to $+\infty.$

This works for any sequence $$c_0>0, c_{n+1}=f(c_n)$$ where $f:\mathbb R^{+}\to\mathbb R^+$ is continuous, with $f(x)>x$ for all $x,$ by the same reasoning. We can always conclude that $c_n$ is divergent to $+\infty.$ Essentially, a limit would have to be a fixed point of $f,$ and since $c_n$ is increasing, divergence means divergence to $+\infty.$

It seems like it will work for all real $k>0$ and $k<-1.$ It won’t work when $k\in(-1,0)$ because $\frac{k+1}{k}<0,$ so $b_n$ doesn’t diverge then.

Generalization of part (2).
Let $g(x)$ be a positive increasing differentiable function  with $g(x)\to\infty$ $$\lim_{x\to\infty} \frac{xg’(x)}{g(x)}=L.$$
If $$a_0>0,a_{n+1}=a_{n}\left(1+1/g(a_n)\right)$$ and $b_{n}=g(a_n).$ then I believe we can show: $$b_{n+1}-b_{n}\to L.$$
Specifically, $$g(a_{n+1})-g(a_n)=g(a_{n}+a_{n}/g(a_n))-g(a_n)=\frac{g’(z_n)a_n}{g(a_n)}$$ for some $z_n\in (a_n,a_{n+1}).$ So you need some tighter bound here on the rate of change on $f’$ to get the limit $L.$
If so, $\frac {b_{n}}n\to L,$ and hence $$\frac{g(a_n)}{n}\to L.$$
When $g(x)=x^{\alpha},\alpha>0,$ then $$\frac{xg’(x)}{g(x)}\to \alpha.$$ If $1-\alpha=-1/k,$ then $\alpha=\frac{k+1}{k}.$
Not sure about the conditions on $g.$ You might need something additional. Like $g’$ monotonic and $$\frac{g’(x)}{g’(x+x/g(x))}\to 1.$$ That might be expressed as some condition on $g’’,$ perhaps $$\frac{g’’(x)x}{g(x)g’(x)}\to 0.$$

If $h:\mathbb R^+\to\mathbb R^+$ is differentiable and $h(x)\to0$ as $x\to0^+,$ then we can define $$a_{n+1}=a_n(1+h(1/a_n))$$ then $g(x)=1/h(1/x)$ and $g’(x)=\frac{h’(1/x)}{x^2 h^2(1/x)}$ so the equivalent condition on $h$ is, with $y=1/x,$ the same $$\lim_{y\to0^+}\frac{yh’(y)}{h(y)}= L.\tag1$$
If $c_n=1/a_n,$ then $c_{n+1}=\frac{c_n}{1+h(c_n)}.$ And $b_n=g(a_n)=1/h(c_n)$ so $$b_{n+1}-b_n=\frac{h(c_n)-h(c_{n+1})}{h(c_n)h(c_{n+1})}$$
Then $$h(c_n)-h(c_{n+1})=(c_n-c_{n+1})h’(z_n)=\frac{c_n h(c_n)h’(z_n)}{1+h(c_n)}$$ for some $z_n\in(c_{n+1},c_n).$ So $$b_{n+1}-b_n=\frac{c_nh’(z_n)}{h(c_{n+1})(1+h(c_n))}=\frac{c_{n+1}h’(z_n)}{h(c_{n+1}}$$ So the limit is equal to $$\lim_{n\to\infty}\frac{c_{n+1}h’(z_n)}{h(c_{n+1})}$$
If $h’$ is monotonic, then $b_{n+1}-b_n$ is between $\frac{c_{n+1}h’(c_{n+1})}{h(c_{n+1})}$ and $\frac{c_{n+1}h’(c_n)}{h(c_{n+1})}.$ The first converges to $L.$
We still need $$\frac{h’(y)}{h’\left(\frac{y}{1+h(y)}\right)}\to 1\tag1$$ to be sure $b_{n+1}-b_n$ converges to $L.$
(1) will converge if $h’(y)$ converges to a non-zero value as $y\to0^+.$
Since $u(y)=\frac{y}{1+h(y)}$ has $$u’(y)=\frac{1}{1+h(y)}-\frac{yh’(y)}{(1+h(y))^2}$$ then since $h(y)\to0$ and $yh’(y)=h(y)\frac{yh’(y)}{h(y)}\to0,$ then $u’(y)\to 1.$ So by L’Hopital:
$$\lim_{y\to0^+}\frac{h’(y)}{h’(u(y))}=\lim_{y\to0^+}\frac{h(y)}{h(u(y))}$$
When $h(y)\sim Cy^{\alpha},$ for some $\alpha>0,$ then the limit is the same as the limit of $$(1+h(y))^{\alpha}\to1.$$
If $h(y)=y^{\alpha}P(y)$ where  $\frac{yP’(y)}{P(y)}\to0,$ then $$\frac{yh’(y)}{h(y)}=\frac{\alpha P(y)+yP’(y)}{P(y)}\to\alpha.$$
On the other hand, if $yh’(y)/h(y)\to L,$ then let $Q(y)=h(y)/y^{L}.$ Then $$\frac{yh’(y)}{h(y)}=\frac{LQ(y)+yQ’(y)}{Q(y)}=L+\frac{yQ’(y)}{Q(y)}.$$
So the limit (1) being $L$ means $h(y)=y^LP(y),$ for some $P$ satisfying $yP’(y)/P(y)\to0.$ If $h’$ is also monic near zero, $b_{n+1}-b_n\to L.$
$$h’(y)=y^{L-1}(LP(y)+yP’(y))$$
$$h’’(y)=y^{L-2}\left(L(L-1)P(y)+(L-1)yP’(y)+yLP’(y)+yP’(y)+y^2yP’’(y)\right)\\=y^{L-2}P(y)\left(L(L-1)+(L+1)\frac{yP’(y)}{P(y)}+\frac{y^2P’’(y)}{P(y)}\right)$$
So, at least when $L\neq1,$ it is enough that $\frac{y^2P’’(y)}{P(y)}\to0.$ It is sufficient for that expression to be bounded away from $L(L-1).$
When $L=1,$ we need $2P’(y)\neq -yP’’(y)$ near $0.$ This amounts to $y^2P’(y)$ not having infinitely many zero derivatives near zero.
A: Note that$$m=\sum_{n=0}^{m-1}(a_{n+1}-a_{n})a_{n}^\frac{1}{k}<\int_{a_{0}}^{a_{m}}x^{\frac{1}{k}}dx=\dfrac{k}{k+1}(a_{m}^{\frac{k+1}{k}}-a_{0}^{\frac{k+1}{k}}).$$Thus$$\dfrac{k+1}{k}m<a_{m}^{\frac{k+1}{k}}\Rightarrow\lim\limits_{m\rightarrow\infty}\dfrac{a_{m}^{k+1}}{m^{k}}\geq(\dfrac{k+1}{k})^{k}.$$Also $a_{m}^{-\frac{1}{k}}<(\dfrac{k+1}{k}m)^{-\frac{1}{k+1}},$implies that$$a_{n}=a_{0}+\sum_{m=0}^{n-1}a_{m}^{-\frac{1}{k}}<a_{0}+(\dfrac{k+1}{k})^{-\frac{1}{k+1}}\sum_{m=0}^{n-1}m^{-\frac{1}{k+1}}.$$However$$\sum_{m=0}^{n-1}m^{-\frac{1}{k+1}}<\int_{0}^{n}x^{-\frac{1}{k+1}}dx=\dfrac{k+1}{k}n^{\frac{k}{k+1}}$$We obtain$$\lim\limits_{n\rightarrow\infty}\dfrac{a_{n}^{k+1}}{n^{k}}\leq(\dfrac{k+1}{k})^{k}.$$In conclusion,$$\lim\limits_{n\rightarrow\infty}\dfrac{a_{n}^{k+1}}{n^{k}}=(\dfrac{k+1}{k})^{k}.$$
