Recursion-like sequences which are hard to relate recursively Consider the sequence
\begin{align*}
   a_1&=1\\
   a_2&=2+\sqrt1\\
   a_3&=3+\sqrt{2+\sqrt1}\\
   &\kern5.5pt\vdots\\
   a_n&=n+\sqrt{n-1+\sqrt{\cdots+\sqrt{1}}}.
\end{align*}
Something like this is easy to work with inductively, since we can simply relate $a_n = n+\sqrt{a_{n-1}}$, and prove things that way. But now consider something which instead unfolds "on the inside", such as
\begin{align*}
   b_1&=1\\
   b_2&=1+\sqrt2\\
   b_3&=1+\sqrt{2+\sqrt{3}}\\
   &\kern5.5pt\vdots\\
   b_n&=1+\sqrt{2+\sqrt{\cdots+\sqrt{n}}},
\end{align*}
where it is not easy to relate $b_n$ to $b_{n-1}$. How does one work with such sequences, where we are typically interested in the same sorts of questions? Or another example, consider the sequence
\begin{align*}
   c_1&=1\\
   c_2&=1(1+2)\\
   c_3&=1(1+2(1+3))\\
   c_4&=1(1+2(1+3(1+4)))\\
   &\kern5.5pt\vdots\\
   c_n&=1(1+2(1+3(1+\cdots+(n-1)(1+n)\cdots))).
\end{align*}
Is it possible to prove inductively that $c_n = 1!+2!+\cdots+n!$, even though there is no obvious way to relate $c_n$ to $c_{n-1}$?
 A: I think the answer lies in looking at multivariable functions. Let's take your second example.
Define the function $$g(n,x)=\begin{cases}g(n-1,(n-1)(1+x))& \text{if } n > 1 \\x& \text{otherwise}\end{cases}$$ where $n\in\mathbb{N},x\in\mathbb{R}$.
It's easy to verify that $c_n=g(n,n)$.
Next, you can show that $g$ is an affine function in the second argument via induction. The base case is trivial since $g(1,x)=x$.
Now suppose $g(n,\cdot)$ is affine, meaning $$\exists k_n\in\mathbb{R}:\forall x,y\in\mathbb{R}:g(n,x)-g(n,y)=k_n(x-y)$$
Then for arbitrary $x,y\in\mathbb{R}$
$$g(n+1,x)-g(n+1,y)=g(n,n(1+x))-g(n,n(1+y))=k_nn(1+x-(1+y))=k_nn(x-y)$$ where we used the induction hypothesis in the 3rd equality. So our $k_{n+1}=k_nn$ which concludes the proof.
Since $g(n,\cdot)$ is affine, we would like to know the additive constant, so let's plug in $0$ and we get $g(n,0)=g(n-1,n-1)=c_{n-1}$. So we get the simple recursion $$c_{n+1}=g(n+1,n+1)=k_{n+1}(n+1)+c_n$$
And with the recursion $k_{n+1}=k_nn$ that we got before, we can easily solve for $c_n$ now.
Now, I unfortunately don't have a canonical answer. For example, I don't know how to use this approach for your first example. However, I have often found that going "2D" and trying to find simple recursions there, was the way to go.
(EDIT: After playing around a bit, using this approach for $b_n$, I haven't gotten a closed-form or a limit, however, it is easy to show that the sequence is increasing and bounded from above and therefore convergent and that the forwards difference goes to $0$. 2 things that I honestly wouldn't have seen at first glance.)
A: You can add $x$.
Let
$$\begin{align*}
   c_1'&=1x\\
   c_2'&=1(1+2x)\\
   c_3'&=1(1+2(1+3x))\\
   c_4'&=1(1+2(1+3(1+4x)))\\
   &\kern5.5pt\vdots\\
   c_n'&=1(1+2(1+3(1+\cdots+(n-1)(1+nx)\cdots))).
\end{align*}$$
So we know that $c_n'$ is $c_{n-1}'$ put $x$ as $(1+nx)$. Let $c_n'=A_n+B_nx$. So we have $A_n=A_{n-1}+B_{n-1}$ and $B_{n}=nB_{n-1}$. So you may need the recurrance relation like this.
To prove $c_n' = 1!+2!+\cdots+n!$ recursively, we can use induction to prove $A_{n}=1!+2!+\cdots+(n-1)!$ and $B_n=n!$. If this holds for $n-1$, we have $A_n=A_{n-1}+B_{n-1}=(1!+2!+\cdots+(n-2)!)+(n-1)!=1!+2!+\cdots+(n-1)!$, $B_n=nB_{n-1}=n\times (n-1)!=n!$. So $c_n$ is $c'_n$ to make $x=1$, $c_n=A_n+B_n=1!+2!+\cdots+(n-1)!+n!$.
For $b_n$, you can do it similarly (although there is no closed form). You can see $b'_n$ as functions: $b'_n(x)=1+\sqrt{2+\sqrt{\cdots+\sqrt{n+x}}}$, so we have $b'_{n+1}=b_n'(\sqrt{n+1+x})$. However, there may be no yield...
A: $c_n$ is th Hörner factorization of :
$$1! + 2! + 3! + \cdots + n!$$
In fact :

*

* $1! + 2! + 3! = 3! + 2! + 1! = 3 \times 2 \times 1 + 2 \times 1 + 1 = ((3 + 1) \times 2 + 1) \times 1 = c_3$.

* $\begin{array}[t]{lcl}
1! + 2! + 3! + 4! & = & 4! + 3! + 2! + 1! \\[2mm]
& = & 4 \times 3 \times 2 \times 1 + 3 \times 2 \times 1 + 2 \times 1 + 1 \\[2mm]
& = & (((4 + 1) \times 3 + 1) \times 2 + 1) \times 1 = c_4
\end{array}$.

* $\begin{array}[t]{lcl}
1! + 2! + \cdots + n! & = & n! + \cdots + 2! + 1! \\[2mm]
& = & n \times (n - 1) \times \cdots \times 1 + \cdots + 2 \times 1 + 1 \\[2mm]
& = & (\dots(((n + 1) \times (n - 1) + 1) \times \cdots + 1) 2 + 1) \times 1 = c_n
\end{array}$.

