I asked this question of MSE, but to no avail; alas, here I am.
Let $k>0$, $C\geq 1$, $\alpha \in (0,1]$, and let $(x_n)_{n\geq 1}$, be a sequence of real numbers given by the recursion $$ x_{n+1} = k |C|^{\alpha} + |x_{n}|^{\alpha} \qquad x_0=0. $$ Is there a simple "non-recursive" expression for $x_{n}$, for $n>0$? At the very worst, is there a tight-upper bound for $x_n$ only depending on $C,k,$ and $\alpha$? I was trying to obtain an upper-bound by the geometric sums $\sum_{i=1}^n{k C}^{\alpha}$ but I'm no longer convinced this is correct.

  • $\begingroup$ What is the significance of $f$? You don't seem to use it again. $\endgroup$ – Christian Remling Dec 6 '20 at 19:57
  • $\begingroup$ Please include a link to the question on m.se, and include a link there to the question here. $\endgroup$ – Gerry Myerson Dec 6 '20 at 21:20
  • $\begingroup$ @GerryMyerson I look down the MSE question. When I migrted it here $\endgroup$ – Wasserstein's Apprentice Dec 7 '20 at 7:08

It seems extremely unlikely that a simple "non-recursive" expression for $x_n$ is possible. However, let us obtain an exact upper bound on the $x_n$'s.

Let $a:=\alpha\in(0,1]$ and $b:=k|C|^a\in(0,\infty)$. It is clear that $x_n\ge0$ for all $n$. So, $$x_0=0,\quad x_1=b,\tag{1}$$ and $$x_{n+1}=g(x_n)\tag{2}$$ for $n\ge1$, where $g(u):=b+u^a$. To avoid trivialities, assume that $a\ne1$, so that $a\in(0,1)$. Then $h(u):=g(u)-u$ is concave in real $u\ge0$, with $h(0)=b>0$ and $h(\infty-)=-\infty$. So, there is a unique root $u_b\in(0,\infty)$ of the equation $h(u)=0$ and, moreover, $h\ge0$ on the interval $[0,u_b]$, that is, $$g(u)\ge u\quad \forall u\in[0,u_b],\tag{2.5}$$ whereas $$b+u_b^a=g(u_b)=u_b.\tag{2.75}$$ In particular, it follows that $$u_b\ge b.\tag{3}$$

Let us show, by induction on $n\ge0$, that $$x_n\le u_b\tag{4}$$ for all $n\ge0$. Indeed, by (1) and (3), (4) holds for $n=0,1$. Supposing now that (4) holds for some $n\ge1$, we have $$x_{n+1}=g(x_n)\le g(u_b)=u_b,$$ in view of (2) and because the function $g$ is increasing. So, (4) holds for all $n\ge0$.

Now (2), (2.5), and (4) imply $$x_{n+1}=g(x_n)\ge x_n.$$ So, $(x_n)$ is a nondecreasing sequence in $[0,u_b]$. Therefore and in view of (2) and (2.75), $$x_n\uparrow u_b$$ as $n\uparrow\infty$.

Thus, in view of (4), $u_b$ is the best upper bound on the $x_n$'s.

If $a$ is rational, then the unique root $u_b$ of the equation $u_b=g(u_b)$ will be algebraic in $b$. E.g., if $a=1/2$, then $u_b=(1+2 b+\sqrt{1+4 b})/2$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.