Recursion-like sequences which are hard to relate recursively

Question

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

Answer 1

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

Answer 2

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

Answer 3

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