Is there a closed form expression for the "generalized" addition of the first $n$ numbers?

Firstly, I will explain what I am trying to do intuitively. We take the sum of the first $n$ positive integers. Let's say this sum is equal to $q$. Then you add that sum to the sum of the first $q$ positive integers. Let's say this new sum is equal to $m$. Then you add that to the sum of the first $m$ positive integers. The number of times this process is iterated is specified by some $k$, which, along with $n$, is the independent variable for this function.

Formally, suppose we define a function $\sigma: \mathbb{N}\times\mathbb{N} \rightarrow \mathbb{N}$ recursively as follows.

$$\sigma(0,n) = n$$ and if $k>0$, $$\sigma(k,n) = \sum_{j = 0}^{k-1}\sum_{i = 1}^{\sigma(j,n)} i$$

For example, $$\sigma(1,n) = \sum_{j = 0}^{0}\sum_{i = 1}^{\sigma(j,n)} i = \sum_{i = 1}^{\sigma(0,n)} i = \frac{n(n+1)}{2}$$

$$\sigma(2,n) = \sum_{j = 0}^{1}\sum_{i = 1}^{\sigma(j,n)} i = \sum_{i = 1}^{\sigma(0,n)} i + \sum_{i = 1}^{\sigma(1,n)} i = \sum_{i = 1}^{n} i + \sum_{i = 1}^{\frac{n(n+1)}{2}} i$$

Is there a "closed form" expression, or simply any general formula, for $\sigma(k,n)$?

Solution 1:

The recurrence can be written as:

$$ \begin{aligned} \sigma(k + 1, n) &= \sigma(k, n) + \frac{\sigma(k, n)^2 + \sigma(k, n)}{2}\\ &= \frac{\sigma(k, n)^2 + 3\sigma(k, n)}{2}\\ \end{aligned} $$

Since $n$ doesn't matter for this analysis, I'll rewrite with $\sigma(n, k) = \sigma_k$ for conciseness.

$$ \sigma_{k+1} = \frac{\sigma_k^2 + 3\sigma_k}{2} $$

This is a quadratic recurrence relation. I'll put it in standard form $S_{k+1} = aS_k^2 + bS_k + c$.

$$ \sigma_{k+1} = \frac{1}{2}\sigma_k^2 + \frac{3}{2}\sigma_k $$

Now we're just trying to find a closed form for a quadratic recurrence relation. Following Will Jagy's answer here, we first try to create another sequence $T_k$ with a recurrence of the form $T_{k+1} = T_k^2 + c$. It turns out this sequence is just:

$$ T_k = \frac{1}{2}\sigma_k + \frac{3}{4} $$

with the recurrence

$$ T_{k+1} = T_k^2 + \frac{3}{16} $$

(Check me!). Will Jagy then says that there are only two cases with a closed form: when $c = 0$ and when $c = -2$. Neither case holds, so there isn't a closed form.

I would love to know more about this problem in generality. Why are those two cases the only ones that can be solved?

Solution 2:

Let $s_n$ denote $\sigma(n, i)$.

Using Eli Rose's (now deleted) comment as guidance:

$$s_{n+1} = \sum_{i=1}^{s_n}i + s_n + s_{n-1} + \cdots + s_1$$ $$s_{n} = \sum_{i=1}^{s_{n-1}}i + s_{n-1} + \cdots + s_1$$ Subtracting them, we see $$s_{n+1}-s_n = \sum_{i=1}^{s_n}i + s_n - \sum_{i=1}^{s_{n-1}}i = \frac{s_n^2+s_n}{2} + s_n - \frac{s_{n-1}^2+s_{n-1}}{2}$$ So we get a recursive formula for $$2s_{n+1} = s_n^2 + 3s_n - s_{n-1}^2 - s_{n-1}$$

Since we know $s_1=i$ and $s_2=\frac{i(i+1)}{2}$ as given in the problem, we can use this formula to calculate $s_n$ for all $n$. (I apologize, I reversed the $n$ and the $i$ in my calculations, as compared to the original problem.)

Unfortunately, a closed form did not give very nice coefficients using several approaches.