12

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

MathematicsStudent1122
  • 12,462
  • Another way to express what you are looking for is a 'closed form' for the sum $\sum_k \sigma^{\circ k}(n)$ where $\sigma(n)=\frac{n(n+1)}{2}$. Not that this makes things easier; I don't see a nice way to compute the sum yet. – Ryan Vitale Dec 30 '15 at 20:05
  • @Alex: I changed my comment a few times, and am having trouble checking if it's actually correct. Does the current form seem right to you? – Eli Rose Dec 30 '15 at 20:14
  • No, I am about to post the correct form as an answer. That's the best I can do. – Alex Dec 30 '15 at 20:22
  • @Alex: Cool, yeah I see where my error was. I'll delete my comment. – Eli Rose Dec 30 '15 at 20:24

2 Answers2

4

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?

Community
  • 1
Eli Rose
  • 8,141
  • 1
    The recurrence $T_{k+1}=T_k^2+a_k$ is treated in section 2.2.3 Doubly Exponential Sequences from Mathematics for the Analysis of Algorithms by D.H. Greene and D.E. Knuth. They follow in their book the paper from A.V. Aho and N.J.A. Sloane. In this paper they also explicitily state, that they got the hints about the two closed forms $(c=0, c=-2)$ from D. Knuth. – Markus Scheuer Jan 04 '16 at 20:13
1

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.

Alex
  • 2,449