# 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

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

1. 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.
2. 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

1. Is my solution correct?
2. Is it correct to state that the solution is valid also for any real number $$k\geq 1$$?
3. Can we further generalize? For example: what can be stated for $$0, maybe with some restriction on $$a_0$$?
• (1) is not obvious to me. What am I missing? Commented Jan 10, 2022 at 19:33
• @ThomasAndrews thanks! I think I erroneously assumed $a_0>1$. I will edit the question to point out my mistake and try to find another approach!
– dfnu
Commented Jan 10, 2022 at 19:40
• $a_n$ is increasing, so if $a_n$ is convergent to some $a>0,$ then $a_{n+1}-a_n\to 0.$ But $a_{n+1}-a_n=1/a_{n}^{1/k}\to 1/a^{1/k}.$ Contradiction. So $a_n$ must diverge. Commented Jan 10, 2022 at 19:46
• @ThomasAndrews thanks! I was thinking, alternatively, to use the fact that if $a_0<1$, then $a_1>1$, so that we can still lower bound with the generalized harmonic series. But your approach is faster.
– dfnu
Commented Jan 10, 2022 at 19:48
• The rest of your answer looks fine. Commented Jan 10, 2022 at 19:51

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.

• Apparently all the steps of the proof remain valid if $k<-1$. Do you have some reason to be uncertain?
– dfnu
Commented Jan 10, 2022 at 21:30
• Was just thinking it through, tryi g to see if I missed anything. @dfnu Commented Jan 10, 2022 at 21:32
• So, it is possibile that $\frac{g'(z_n)a_n}{g(a_n)}\not \to L$, for $n\to \infty$, despite the hypothesis that $\frac{g'(x)x}{g(x)}\to L$ when $x\to \infty$. Correct?
– dfnu
Commented Jan 11, 2022 at 13:32
• @dfnu Yeah, I just haven’t worked out the right condition. Obviously, if $g’(z_n)/g’(a_n)\to 1,$ we get convergence to $L,$ but that is tricky to find conditions to ensure that. Commented Jan 11, 2022 at 17:40
• Thanks a lot! I came up with a much simpler and more stringent sufficient condition. Using your notation, $$a_{n+1} = a_n\left(1+\frac1{g(a_n)}\right),$$if $g(x)$ is positive and differentiable, $g(x) \to \infty$ for $x\to \infty$, and $\frac{g'(x)}{x^{\alpha-1}}\to L$ for some positive $\alpha$, then $$\frac{a_n^\alpha}{n}\to \frac{\alpha^2}L.$$
– dfnu
Commented Jan 12, 2022 at 0:20

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}mAlso $$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}}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}.$$