¿Existe una expresión en forma cerrada para la suma "generalizada" de los primeros $n$ números?

Question

En primer lugar, explicaré lo que estoy intentando hacer intuitivamente. Tomamos la suma de los primeros $n$ enteros positivos. Supongamos que esta suma es igual a $q$. Luego agregas esa suma a la suma de los primeros $q$ enteros positivos. Supongamos que esta nueva suma es igual a $m$. Luego agregas eso a la suma de los primeros $m$ enteros positivos. El número de veces que se itera este proceso está especificado por algún $k$, que, junto con $n$, es la variable independiente de esta función.

Formalmente, supongamos que definimos una función $\sigma: \mathbb{N}\times\mathbb{N} \rightarrow \mathbb{N}$ de forma recursiva de la siguiente manera.

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

Por ejemplo, $$\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$$

¿Existe una expresión en "forma cerrada" o simplemente alguna fórmula general para $\sigma(k,n)$?

Answer 1

La recurrencia se puede escribir como:

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

Dado que $n$ no importa para este análisis, lo reescribiré con $\sigma(n, k) = \sigma_k$ para mayor concisión.

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

Esta es una relación de recurrencia cuadrática. La pondré en forma estándar $S_{k+1} = aS_k^2 + bS_k + c$.

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

Ahora solo estamos tratando de encontrar una forma cerrada para una relación de recurrencia cuadrática. Siguiendo la respuesta de Will Jagy aquí, primero intentamos crear otra secuencia $T_k$ con una recurrencia de la forma $T_{k+1} = T_k^2 + c. Resulta que esta secuencia es simplemente:

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

con la recurrencia

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

(¡Verifíquenlo!). Luego Will Jagy dice que solo hay dos casos con una forma cerrada: cuando $c = 0$ y cuando $c = -2$. Ningún caso se cumple, por lo que no hay una forma cerrada.

Me encantaría saber más sobre este problema en general. ¿Por qué esos dos casos son los únicos que se pueden resolver?

Answer 2

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

Utilizando el comentario de Eli Rose (ahora eliminado) como guía:

$$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$$ Restándolos, vemos $$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}$$ Entonces obtenemos una fórmula recursiva para $$2s_{n+1} = s_n^2 + 3s_n - s_{n-1}^2 - s_{n-1}$$

Dado que sabemos que $s_1=i$ y $s_2=\frac{i(i+1)}{2}$ como se indica en el problema, podemos usar esta fórmula para calcular $s_n$ para todos los $n$. (Me disculpo, invertí el $n$ y el $i$ en mis cálculos, en comparación con el problema original.)

Desafortunadamente, una forma cerrada no dio coeficientes muy bonitos utilizando varios enfoques.