Recursive definition of this sequence

Question

I'm having some trouble finding a recursive definition for the following sequence:

$x_0 = \sqrt{1+n}$

$x_1 = \sqrt{1+n\sqrt{1+(n+1)}}$

$x_2 = \sqrt{1+n\sqrt{1+(n+1)\sqrt{1+(n+2)}}}$

$x_3 = \sqrt{1+n\sqrt{1+(n+1)\sqrt{1+(n+2)\sqrt{1+(n+3)}}}}$

and so on (where $n \in \mathbb{N}$). I tried using something like $x_{i+1} = \sqrt{1 + n f(x_i)}$ where $f$ would be a function that sends $n$ to $n+1$ wherever $n$ appears in $x_i$. So for instance $f(x_0) = \sqrt{1 + (n+1)}$ and $f(x_1) = \sqrt{1+(n+1)\sqrt{1+(n+2)}}$. My problem is that I can't figure out an explicit form for $f$. If it's any help, the limit of the sequence is $n+1$.

Answer 1

One has $x_k(n) = f_{k+1}(n)$, where $(f_k)_{k \geqslant 0}$ is the sequence of functions defined recursively as follows:

$f_0(n) = 1$

$f_{k+1}(n) = \sqrt{1+nf_k(n+1)}$

Indeed,

$f_0(n) = 1$

$f_1(n) = \sqrt{1+n}$

$f_2(n) = \sqrt{1+n\sqrt{1+(n+1)}}$

$f_3(n) = \sqrt{1+n\sqrt{1+(n+1)\sqrt{1+(n+2)}}}$

etc.

Answer 2

Recall that a sequence $(x_k)$ can be defined recursively if there exists some function $g$ such that $x_{k+1}=g(x_k)$ for every $k$.

Of course, every given strictly increasing sequence, such as the sequences considered in the question, can be defined recursively, using any function $g$ defined on $X=\{x_k\mid k\geqslant0\}$ by $g(x_k)=x_{k+1}$ and, say, by $g(x)=0$ for every $x\notin X$.

This version of the question is rather shallow since every sequence $(x_k)$ can be defined recursively in this sense except if there exists $k<\ell$ such that $x_k=x_\ell$ and $x_{k+1}\ne x_{\ell+1}$, which never happens for strictly monotonous sequences.

A more interesting version would be to ask whether all the sequences $(x_k)$ in the question can be simultaneously defined recursively, that is, whether there exists a common function $g$ for every value of $x_0$, or, equivalently, for every value of $n$.

Then the answer is negative.

To wit, for $n=4$, $x_0=\sqrt5$ and $x_1=\sqrt{1+4\sqrt6}$ while, for $n=2$, $x_1=\sqrt5$ and $x_2=\sqrt{1+2\sqrt{1+3\sqrt5}}$, thus, one would need that $$\sqrt{1+4\sqrt6}=g(\sqrt5)=\sqrt{1+2\sqrt{1+3\sqrt5}}$$ which is absurd.