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}$?

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

