Lista de potencias de los números naturales

Question

Genial,
  Hace algún tiempo un amigo me mostró este sorprendente algoritmo y recientemente he tratado de encontrar alguna información sobre él en Internet pero no he podido encontrar nada... Por favor, ayuda.

Pseudocódigo:
Considera que 1 es el índice inicial de una lista

1.   entrada número natural n.
2.   dejemos s = lista de todos los números naturales {1, 2, 3, 4, 5, 6 ...}
3.   while (n>1) do
    3.1.   dejar caer cada n-ésimo elemento de s
    3.2.   para int i = 2 a ∞ hacer s[i] += s[i-1]
    3.3.   n = n-1
4.   Ahora s = {1 n , 2 n , 3 n , 4 n ...}

Ejemplo: n = 3
s = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...}

realizar 3.1: s = {1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16...}
realizar 3.2: s = {1, 3, 7, 12, 19, 27, 37, 48, 61, 75, 91 ...}
realizar 3.3: n = 2 > 1

realizar 3.1: s = {1, 7, 19, 37, 61, 91 ...}
realizar 3.2: s = {1, 8, 27, 64, 125, 216 ...}
realizar 3.3: n = 1 => fin del bucle while

El estado final de s es {1 3 , 2 3 , 3 3 , 4 3 , 5 3 ...}

Answer 1

Nota: [2014-11-24] Se han hecho algunas simplificaciones más, se han añadido algunos aspectos nuevos y se ha finalizado la prueba general. :-)

Nota: Esta es una buena pregunta que describe un interesante técnica de tamizado para generar $n$ -potencias de números naturales. También vale la pena señalar que hay un relación explícita para una arbitrariedad fija $n$ que proporciona una saltar de $k^n$ a $(k+1)^n$ .

Empecemos con una ligera reformulación del algoritmo que también puede ser conveniente.

Algoritmo para generar $n$ -potencias de números naturales

Dejemos que $S=\{1,2,\ldots,N\} \subset \mathbb{N}$ y $n\in \mathbb{N}$ .

• mientras ( $n>1$ ) hacer

  • dejar caer cada uno $n$ -ésimo elemento de $S$

  • reemplazar cada $j-th$ con la suma parcial del primer $j$ elementos

  • $n \rightarrow n-1$ (reducir $n$ por $1$ )

Resultado: Un conjunto finito $S^\prime=\{1^n,2^n,3^n,\ldots\}$ que sólo contenga consecutivos $n$ -a potencias a partir de $1$ .

Obsérvese que en la pregunta anterior $s[i] += s[i-1]$ debería denotarse de forma más precisa como \begin{align*} s^{(n-1)}[i]=s^{(n)}[i]+s^{(n-1)}[i-1],\tag{1} \end{align*} para que $s^{(n-1)}[i]=\sum_{j=1}^{i}s^{(n)}[j]$ pasa a ser en redondo $n-1$ el suma parcial de la primera $i$ elementos de $s^{(n)}$ de la ronda anterior $n$ .

Primer paso: Ejemplos

Para ver lo que está pasando, echamos un vistazo a dos ejemplos, concretamente a las potencias de $n=5$ y $n=6$ que son lo suficientemente pequeños para ser manejables, pero también lo suficientemente grandes para detectar algunos aspectos esenciales del algoritmo.

Ejemplo: $n=5$

\begin{array}{rrrrrrrrrrrrrrrrr} 1& 2& 3&4&\color{blue}{\it{5}}&\color{blue}{6}&7&8&9&\it{10}&11&12&13&14&\it{15}&16\\ 1& 3&6&\color{blue}{\it{10}}&&\color{blue}{16}& 23 &31&\it{40}&&51& 63&76&\it{90}&&106\\ 1& 4&\color{blue}{\it{10}}&&&\color{blue}{26}&49&\it{80}&&&131& 194&\it{270}&&&376\\ 1& \color{blue}{\it{5}}&&&&\color{blue}{31}&\it{80}&&&&211&\it{405}&&&&781\\ \mathbf{1}&&&&&\mathbf{32}&&&&&\mathbf{243}&&&&&\mathbf{1024}\\ &&T_{5,1}&&&&&T_{5,2}&&&&&T_{5,3}&&&\\ \end{array}

Ejemplo: $n=6$

\begin{array}{rrrrrrrrrrrrrrrrr} 1& 2& 3&4&5&\color{blue}{\it{6}}&\color{blue}{7}&8&9&\it{10}&11&\it{12}&13&14&\it{15}&16\\ 1& 3& 6&10&\color{blue}{\it{15}}&&\color{blue}{22}&30&39&49&\it{60}&&73&87&102&118\\ 1& 4& 10&\color{blue}{\it{20}}&&&\color{blue}{42}&72&111&\it{160}&&&233 &320&422&\it{540}\\ 1& 5&\color{blue}{\it{15}}&&&&\color{blue}{57}&129&\it{240}& &&&473&793&\it{1215}\\ 1& \color{blue}{\it{6}}&&&&&\color{blue}{63}&\it{192}&&&&&665&\it{1458}\\ \mathbf{1}&&&&&&\mathbf{64}&&&&&&\mathbf{729}\\ &&&T_{6,1}&&&&&&T_{6,2}&&&&&T_{6,3} \end{array}

Primero veamos el ejemplo $n=5$ orientado a la fila :

• La primera línea está formada por los números $1$ a $16$

• La siguiente línea ha dejado caer cada $5$ -y los valores fueron sustituidos por sus correspondientes sumas parciales

• Las siguientes líneas fueron modificadas en consecuencia

• Las entradas en negrita $1,32,243,1024$ son los resultados $n^5: 1^5,2^5,3^5$ y $4^5$ .

Pero aún más interesante es mirar el ejemplo según el triangular formas:

• Podemos ver tres triángulos completos y la primera columna de un cuarto triángulo

• El triángulo de la izquierda es una parte de un Triángulo de Pascal

• Todos los triángulos siguientes siguen exactamente el mismo esquema de adición que el Triángulo de Pascal

• Atención : El cursiva Las entradas sumadas e incrementadas en uno dan los valores de la primera columna del siguiente triángulo.

Veamos los triángulos más de cerca considerándolos como matrices triangulares superiores \begin{align*} T_{5,k}=\left(t_{i,j}^{(5,k)}\right)_{1\leq i,j\leq 5}\qquad k\geq 1 \end{align*}

Nota: En lo que sigue escribo los vectores orientados a la fila sin utilizando el símbolo de transposición para mejorar la legibilidad.

Fila superior de $T_{5,k}$

La descripción general de la primera fila del $k$ -ésima matriz $T_{5,k}$ es:

\begin{align*} \left(t_{1,j}^{(5,1)}\right)_{1\leq j \leq 5}&=(1,2,3,4,5)\\ \left(t_{1,j}^{(5,2)}\right)_{1\leq j \leq 5}&=(6,7,8,9,10)\\ &\ldots\\ \left(t_{1,j}^{(5,k)}\right)_{1\leq j \leq 5}&=\Big(5(k-1)+j\Big)_{1\leq j \leq 5}\qquad k \geq 1 \end{align*}

Diagonal menor de $T_{5,k}$

Los elementos de la diagonal menor

$$\text{diag}_{min} \left(T_{5,k}\right)=\left(t_{j,6-j}\right)_{1\leq j \leq 5}$$

de la matriz $T_{5,k}$ mostrar una buena relación

\begin{align*} \text{diag}_{min}\left(T_{5,1}\right)_{1\leq j \leq 5}&=(5,10,10,5,\mathbf{1})\\ &=\left(\binom{5}{1},\binom{5}{2},\binom{5}{3},\binom{5}{4},\mathbf{1^5}\right)\\ \text{diag}_{min}\left(T_{5,2}\right)_{1\leq j \leq 5}&=(10,40,80,80,\mathbf{32})\\ &=\left(\binom{5}{1}2^1,\binom{5}{2}2^2,\binom{5}{3}2^3,\binom{5}{4}2^4,\mathbf{2^5}\right)\\ \text{diag}_{min}\left(T_{5,3}\right)_{1\leq j \leq 5}&=(15,90,270,405,\mathbf{243})\\ &=\left(\binom{5}{1}3^1,\binom{5}{2}3^2,\binom{5}{3}3^3,\binom{5}{4}3^4,\mathbf{3^5}\right)\\ &\ldots\\ \text{diag}_{min}\left(T_{5,k}\right)_{1\leq j \leq 5} &=\left(\binom{5}{1}k^1,\binom{5}{2}k^2,\binom{5}{3}k^3,\binom{5}{4}k^4,\mathbf{k^5}\right)\\ \end{align*}

Columna más a la izquierda de $T_{5,k}$

Obsérvese que las entradas del columna de la izquierda de $T_{5,k}$ son los suma de los elementos de la diagonal menor de la matriz predecesora $T_{5,k-1}$ incrementado en uno. Por lo tanto, obtenemos

\begin{align*} \left(t_{j,1}^{(5,k)}\right)_{1\leq j \leq 5} &=\left(1+\sum_{l=1}^{j}\binom{5}{l}(k-1)^l\right)_{1\leq j \leq 5}\qquad\qquad k \geq 2\\ &=\left(\sum_{l=0}^{j}\binom{5}{l}(k-1)^l\right)_{1\leq j \leq 5}\\ \end{align*}

Tenga en cuenta que el entrada inferior de la columna de la izquierda se puede escribir de acuerdo con la descripción de la diagonal menor de $T_{5,k}$ como

\begin{align*} t_{5,1}^{(5,k)}&=\sum_{l=0}^{5}\binom{5}{l}(k-1)^l=\mathbf{k^5},\qquad k \geq 2 \end{align*}

---

Descripción general de la matriz diagonal superior $T_{n,k}$ :

Ahora estamos en condiciones de describir la matriz diagonal superior $T_{n,k}$ en general

Propuesta: La siguiente afirmación es válida: La matriz diagonal superior

\begin{align*} T_{n,k}=\left(t_{i,j}^{(n,k)}\right)_{1\leq i,j\leq n}\qquad k\geq 1,n \geq 2 \end{align*}

caracterizado por la

• Fila superior de $T_{n,k}$ :

\begin{align*} \left(t_{1,j}^{(n,k)}\right)_{1\leq j \leq n}&=\Big(n(k-1)+j\Big)_{1\leq j \leq n},\qquad k \geq 1,n\geq 2 \end{align*}

y por el

• Columna más a la izquierda de $T_{n,k}$ :

\begin{equation*} \left(t_{j,1}^{(n,1)}\right)_{1\leq j \leq n}= \begin{cases} \left(1\right)_{1\leq j \leq n}&\qquad k=1\\ \\ \left(\sum_{l=0}^{j}\binom{n}{l}(k-1)^l\right)_{1\leq j \leq n}&\qquad k \geq 2\\ \end{cases} \end{equation*}

junto con un

• Esquema de adición correspondiente a la de un Triángulo de Pascal:

\begin{equation*} (t_{i,j})^{(n,k)} = \begin{cases} (t_{i-1,j})^{(n,k)}+(t_{i,j-1})^{(n,k)}&\qquad 2 \leq i\leq n,\quad 2 \leq j \leq i,\quad k \geq 1\\ 0&\qquad 2 \leq i\leq n,\quad i < j \leq n,\quad k \geq 1 \end{cases} \end{equation*}

tiene las siguientes propiedades

• El elemento inferior de la columna de la izquierda es $k^n$ :

  $$t_{n,1}^{(n,k)} = \mathbf{k^n}, \qquad\qquad k \geq 1, n \geq 2$$

• Los elementos del diagonal menor

  $$\text{diag}_{min} \left(T_{n,k}\right)=\left(t_{j,n+1-j}\right)_{1\leq j \leq n}$$

  cumplir con

\begin{align*} \text{diag}_{min}\left(T_{n,k}\right) &=\left(\binom{n}{1}k^1,\binom{n}{2}k^2,\ldots,\binom{n}{n-1}k^{n-1},\mathbf{k^n}\right)\\ \end{align*}

Prueba: Para cada $n\geq 2$ fija, arbitraria demostramos la proposición por inducción para $k \geq 1$

Dejemos que $n\geq 2$ ser fijo, arbitrario.

Caso base: $k=1$

Tenemos que demostrar que el matriz del triángulo superior $T_{n,1}, n\geq 2$ cumple con

• Fila superior de $T_{n,1}$

\begin{align*} \left(t_{1,j}^{(n,1)}\right)_{1\leq j \leq n}&=(j)_{1\leq j \leq n},\qquad n\geq 2 \end{align*}

El algoritmo comienza con $S=\{1,2,3,\ldots\}$ . Como esto está representado por la fila superior de $T_{n,k}$ que contiene el $k-th$ bloque de $n$ números consecutivos, la fila superior de $T_{n,1}$ contiene el primer $n$ números naturales y la afirmación es verdadera.

• Columna más a la izquierda de $T_{n,1}$

\begin{align*} \left(t_{j,1}^{(n,1)}\right)_{1\leq j \leq n}=\left(1\right)_{1\leq j \leq n} \end{align*}

Dado que el elemento más a la izquierda $1$ nunca es modificado por el algoritmo, la columna más a la izquierda de $T_{n,1}$ es siempre $1$ .

• Esquema de adición correspondiente a la del Triángulo de Pascal

\begin{equation*} (t_{i,j})^{(n,1)} := \begin{cases} (t_{i-1,j})^{(n,1)}+(t_{i,j-1})^{(n,1)}&\qquad 2 \leq i\leq n,\quad 2 \leq j \leq i\\ 0&\qquad 2 \leq i\leq n,\quad i < j \leq n \end{cases} \end{equation*}

El esquema de adición del triángulo superior de la matriz corresponde a la relación (1) del algoritmo: \begin{align*} s^{(n-1)}[i]=s^{(n)}[i]+s^{(n-1)}[i-1] \end{align*} El cero en posición $(2,n)$ corresponde al hecho de que en el primera ronda del algoritmo cada $n-th$ ha sido eliminado.

Los ceros en posición $(3,n-1)$ un $(3,n)$ corresponden al hecho de que en el segunda ronda del algoritmo cada $(n-1)$ También se ha suprimido el elemento "-th".

Si se continúa así, los ceros llenan la parte triangular inferior de la matriz $T_{n,1}$ por lo que la afirmación es cierta.

• El elemento inferior de la columna de la izquierda es:

\begin{align*} t_{n,1}^{(n,1)} = \mathbf{1}, \qquad\qquad n \geq 2 \end{align*}

Esto es simplemente una consecuencia del hecho de que la columna más a la izquierda de la matriz contiene sólo $1$ s.

• Los elementos del diagonal menor son:

\begin{align*} \text{diag}_{min}\left(T_{n,1}\right) &=\left(\binom{n}{1},\binom{n}{2},\ldots,\binom{n}{n-1},\mathbf{1}\right)\\ \end{align*}

El diagonal menor de $T_{n,1}$ es el $n$ -de la fila del Triángulo de Pascal y tiene, por tanto, las entradas $\binom{n}{j}$ con $1\leq j \leq n$ y la afirmación es verdadera.

Conclusión: Se cumple el paso base.

Hipótesis de inducción: $k$

Supongamos que la proposición es verdadera para $k \geq 1$

Paso inductivo: $k \longrightarrow k+1$

• Fila superior de $T_{n,k+1}$ :

Según las hipótesis de inducción, la fila superior de $T_{n,k}$ es de la forma \begin{align*} \left(t_{1,j}^{(n,k)}\right)_{1\leq j \leq n}&=\Big(n(k-1)+j\Big)_{1\leq j \leq n}\qquad n\geq 2 \end{align*}

Desde el $T_{n,k+1}$ es la matriz sucesora del lado derecho de $T_{n,k}$ la primera fila está formada por los elementos \begin{align*} \left(t_{1,j}^{(n,k+1)}\right)_{1\leq j \leq n}&=\Big(nk+j\Big)_{1\leq j \leq n}\qquad n\geq 2 \end{align*} y la afirmación es cierta para $k+1$

• Columna más a la izquierda de $T_{n,k+1}$ :

Según la hipótesis de la inducción, el diagonal menor de $T_{n,k}$ es de la forma

$$\text{diag}_{min} \left(T_{n,k}\right)=\left(t_{j,n+1-j}\right)_{1\leq j \leq n}$$

Ahora, los elementos $(t_{1,j}^{(n,k+1)})_{1\leq j \leq n}$ de la columna más a la izquierda de $T_{n,k+1}$ están de acuerdo con la relación (1) del algoritmo: \begin{align*} s^{(n-1)}[i]=s^{(n)}[i]+s^{(n-1)}[i-1] \end{align*} el sumas parciales de la diagonal menor de $T_{n,k}$ incrementado en uno

\begin{align*} \text{diag}_{min} \left(T_{n,k}\right)=\left(t_{j,n+1-j}\right)_{1\leq j \leq n} \end{align*} y por lo tanto

\begin{align*} \left(t_{1,j}^{(n,k+1)}\right)_{1\leq j \leq n}&=\left(1+\sum_{1\leq l \leq j}\left(t_{j,n+1-j}^{(n,k)}\right)\right)_{1\leq j \leq n}\tag{2}\\ &=\left(1+\sum_{1\leq l \leq j}\binom{n}{l}k^{l}\right)_{1\leq j \leq n}\\ &=\left(\sum_{0\leq l \leq j}\binom{n}{l}k^{l}\right)_{1\leq j \leq n}\\ \end{align*}

y la afirmación es cierta para $k+1$

• Esquema de adición correspondiente a la del Triángulo de Pascal

Como el esquema de adiciones es totalmente independiente de $k$ La explicación que ya se ha dado en el caso base de esta prueba de inducción también es válida al pie de la letra.

Por lo tanto, la afirmación es verdadera para $k+1$ .

• El elemento inferior de la columna más a la izquierda de $T_{n,k+1}$

La columna de la izquierda ya es conocida, por lo que obtenemos según (2)

\begin{align*} t_{n,1}^{(n,k+1)} &= \sum_{0\leq l \leq n}\binom{n}{l}k^{n}\\ &=\mathbf{(k+1)^n}, \qquad\qquad n \geq 2 \end{align*}

Por tanto, la afirmación es cierta para $k+1$ .

• El último punto que tenemos que mostrar es: Los elementos de la diagonal menor

\begin{align*} \text{diag}_{min} \left(T_{n,k+1}\right)=\left(t_{j,n+1-j}^{(n,k+1)}\right)_{1\leq j \leq n} \end{align*}

cumplir con

\begin{align*} \text{diag}_{min}&\left(T_{n,k+1}\right)\\ &=\left(\binom{n}{1}(k+1)^1,\binom{n}{2}(k+1)^2,\ldots,\binom{n}{n-1}(k+1)^{n-1},\mathbf{(k+1)^n}\right)\\ \end{align*}

Nota: Esto es lo más paso interesante de toda la prueba : El saltar de una diagonal menor a la siguiente:

\begin{align*} \text{diag}_{min} \left(T_{n,k}\right)&\qquad\longrightarrow\qquad\text{diag}_{min} \left(T_{n,k+1}\right)\\ \\ \binom{n}{j}k^j&\qquad\longrightarrow\qquad\binom{n}{j}(k+1)^j\qquad 1 \leq j \leq n \end{align*}

Para demostrarlo consideramos la relación del elemento diagonal $t_{j,n+1-j}^{(n,k+1)}$ con los elementos de la fila superior y los elementos de la columna de la izquierda, que ya son conocidos. La relación viene dada por el esquema de adición (1) según el Triángulo de Pascal .

De hecho tenemos que hacer un poco de cálculo de la trayectoria de la red para derivar esta relación.

---

Caminos de rejilla : Observe, el número $\binom{n}{k}$ puede considerarse como el número de trayectorias de la red de longitud $n$ que contiene $k$ horizontal $(1,0)$ -pasos y $n-k$ vertical $(0,1)$ -pasos.

Esto es válido porque hay $\binom{n}{k}$ opciones para seleccionar $k$ pasos en dirección horizontal dejando el resto $n-k$ pasos para la dirección vertical.

Nota: Puede que quieras mirar ejemplo 1 o ejemplo 2 si no está familiarizado con esta técnica.

---

Vamos a simplificar los cálculos al no comenzar en la fila superior y la columna más a la izquierda de $T_{n,k+1}$ pero, en cambio, retrocediendo un paso hacia el diagonal menor de $T_{n,k}$ un análisis de un

Triángulo ampliado $\widetilde{T}_{n,k+1}$

Consideramos que el diagonal menor

\begin{align*} \text{diag}_{min}&\left(T_{n,k}\right)=\left(\binom{n}{1}k^1,\binom{n}{2}k^2,\ldots,\binom{n}{n-1}k^{n-1},\mathbf{k^n}\right)\\ \end{align*}

de la matriz triangular superior $T_{n,k}$ como el primera columna de la siguiente matriz $T_{n,k+1}$ y crear un matriz triangular ampliada $\widetilde{T}_{n,k+1}$ .

Al hacerlo, no tenemos que enfrentarnos a la sumas parciales

$$\sum_{m=1}^{j}\binom{n}{m}k^j\qquad\qquad 1 \leq j \leq n$$

de los elementos de la primera columna de $T_{n,k+1}$ pero en su lugar podemos utilizar

$$\binom{n}{j}k^j\qquad\qquad 1 \leq j \leq n$$ .

Además completar el triángulo de Pascal añadiendo un fila superior que sólo contiene $1s$

Obsérvese que el algoritmo puede ser reformulado de manera equivalente comenzando con una fila superior que sólo contenga $1$ s en lugar de comenzar con una fila superior de los números naturales. Sólo tenemos que realizar un paso adicional construyendo primero una secuencia de sumas parciales para obtener los números naturales antes de empezar a soltar el $n$ -en los elementos.

Ejemplo: $n=6:$

\begin{array}{rrrrrrrrrrrr} 1&1&1&1&1&1&1&1&1&1&1&1\\ 1&2&3&4&5&6&7&8&9&10&11&12\\ 1&3&6&10&15& &22&30&39&49&60&\\ &&\ldots&&&&&&\ldots&&& \end{array}

La ventaja es que, en lugar de multiplicar las sumas combinatorias con los elementos $(n(k+1)+j)$ de la fila superior de $T_{n,k+1}$ podemos utilizar simplemente el factor $1$ .

Volvamos al ejemplo $T_{6,2}$ desde arriba y analizar el elemento $t_{4,3}^{(6,2)}=240$ con la ayuda del ampliado matriz $\widetilde{T}_{6,2}$

\begin{array}{rcrrrrrrrrcrrrrr} 1&|&\mathbf{1}&\mathbf{1}&\mathbf{1}&1&1&1&\qquad1&|&\mathbf{1}&\mathbf{1}&\mathbf{1}&1&1&1\\ \hline \mathbf{6}&|&7&8&9&10&11&\it{12}&\mathbf{6}&|&\mathbf{\it{10}}&\mathbf{\it{4}}&\mathbf{\it{1}}&&&\\ \mathbf{15}&|&22&30&39&49&\it{60}&&\mathbf{15}&|&\mathbf{\it{6}}&\mathbf{\it{3}}&\mathbf{\it{1}}&&&\\ \mathbf{20}&|&42&72&111&\it{160}&&&\mathbf{20}&|&\mathbf{\it{3}}&\mathbf{\it{2}}&\mathbf{\it{1}}&&&\\ \mathbf{15}&|&57&129&\mathbf{240}&&&&\mathbf{15}&|&\mathbf{\it{1}}&\mathbf{\it{1}}&\mathbf{240}&&&\\ 6&|&63&\it{192}&&&&&6&|&&&&&&\\ 1&|&64&&&&&&1&|&&&&&&\\ &&&&\widetilde{T}_{6,2}&&&&&&&& \end{array}

En la tabla anterior vemos en el triángulo de la derecha el número de caminos a partir de $$t_{4,3}^{(6,2)}=240\qquad$$ y que van a los puntos de la columna más a la izquierda, respectivamente a los puntos de la fila superior. De este patrón deducimos:

\begin{align*} \mathbf{240}&=129 + 111\\ &=(57+42)+(72+39)\\ &=((\mathbf{15}+42)+(\mathbf{20}+22))+((42+30)+(30+9))\\ &\ldots\\ &=(\it{10}\cdot\mathbf{6}+\it{6}\cdot\mathbf{15}+\it{3}\cdot\mathbf{20}+\it{1}\cdot\mathbf{15}) +(\it{10}\cdot\mathbf{1}+\it{4}\cdot\mathbf{1}+\it{1}\cdot\mathbf{1}) \end{align*}

Con este ejemplo en mente podemos derivar la fórmula general para los elementos de la diagonal menor:

Fórmula general para el salto de $\binom{n}{j}k^j$ a $\binom{n}{j}(k+1)^j$ :

Supongamos que tenemos un elemento $$t_{j,n-j+1}^{(n,k+1)}\qquad\qquad 1 \leq j \leq n$$ de la diagonal menor en el $j-th$ fila y $n-j+1$ columna de la original matriz triangular superior $T_{n,k+1}$ entonces tenemos que determinar el número de caminos de $$(m,1)\qquad\text{to}\qquad(j,n-j+1) \qquad 1\leq m \leq j$$ correspondiente a las entradas de la columna más a la izquierda $(1,1)$ a $(j,1)$ y tenemos que determinar el número de caminos de $$(1,m)\qquad\text{to}\qquad(j,n+1-j) \qquad 1\leq m \leq n-j+1$$ correspondiente a las entradas de la fila superior $(1,1)$ a $(1,n+1-j)$

Nota: Dejemos que $0\leq x_1\leq x_2$ y $0\leq y_1\leq y_2$ . El número de caminos $N_{(x_1,y_1)}^{(x_2,y_2)}$ de $(x_1,y_1)$ a $(x_2,y_2)$ es $$N_{(x_1,y_1)}^{(x_2,y_2)}=\binom{x_2-x_1+y_2-y_1}{x_2-x_1}=\binom{x_2-x_1+y_2-y_1}{y_2-y_1}$$

Observamos: El número de caminos de $(m,1)$ a $(j,n-j+1)$ y el número de caminos de $(1,m)$ a $(j,n-j+1)$ es $$N_{(m,1)}^{(j,n-j+1)}\binom{n-m}{n-j}\qquad\text{resp.}\qquad N_{(1,m)}^{(j,n-j+1)}\binom{n-m}{j-1}$$

Ahora podemos formular la identidad binomial que tenemos que probar para demostrar la última parte del paso inductivo.

Identidad binomial :

Lo siguiente es válido para $1\leq j \leq n$ :

\begin{align*} \sum_{m=1}^{j}\binom{n-m}{n-j}t_{j,n+1-j}^{(n,k)}&+\sum_{m=1}^{n-j}\binom{n-m}{j-1} =t_{j,n+1-j}^{(n,k+1)}\\ \text{resp. }&\\ \sum_{m=1}^{j}\binom{n-m}{n-j}\binom{n}{m}k^n&+\sum_{m=1}^{n-j}\binom{n-m}{j-1}\tag{3} =\binom{n}{j}(k+1)^n \end{align*}

Calculamos cada suma de (3) por separado:

La primera suma del LHS:

\begin{align*} \sum_{m=1}^{j}&\binom{n-m}{n-j}\binom{n}{m}k^n\\ &=\sum_{m=1}^{j}\frac{(n-m)!}{(n-j)!(j-m)!}\frac{n!}{m!(n-m)!}k^m\\ &=\frac{n!}{(n-j)!}\sum_{m=1}^{j}\frac{1}{(j-m)!m!}k^m\\ &=\binom{n}{j}\sum_{m=1}^{j}\binom{j}{m}k^m\\ &=\binom{n}{j}\left((k+1)^j-1\right)\\ &=\binom{n}{j}(k+1)^j-\binom{n}{j} \tag{4} \end{align*}

La segunda suma del LHS:

\begin{align*} \sum_{m=1}^{n+1-j}&\binom{n-m}{j-1}\\ &=\sum_{m=1}^{n+1-j}\left(\binom{n-m+1}{j}-\binom{n-m}{j}\right)\\ &=\sum_{m=0}^{n-j}\binom{n-m}{j}-\sum_{m=1}^{n+1-j}\binom{n-m}{j}\\ &=\binom{n}{j}-\binom{j-1}{j}\\ &=\binom{n}{j} \tag{5} \end{align*}

Obsérvese que hemos transformado la suma en (5) en una suma telescópica utilizando el identidad binomial \begin{align*} \binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1} \end{align*}

Ahora sumando las dos expresiones (4) y (5) y la RHS: $$t_{j,n+1-j}^{(n,k+1)}=\binom{n}{j}(k+1)^n, \qquad 1 \leq j \leq n, n \geq 2$$ sigue.

Conclusión: Paso inductivo $k \longrightarrow k+1$ es korrecto.

---

Resumen:

• El análisis del algoritmo lleva para fijo, arbitrario $n\geq 2$ a un análisis de matrices triangulares superiores sucesivas $$T_{n,k} \qquad \longrightarrow \qquad T_{n,k+1}$$ .
• Mirando los ejemplos para $n=5$ y $n=6$ se obtiene una interesante relación de los elementos de la diagonal menor de matrices sucesivas $T_{n,k}$ $$\binom{n}{j}k^j \qquad \longrightarrow \qquad\binom{n}{j}(k+1)^j,\qquad\qquad n \geq 2, 1 \leq j \leq n, k \geq 1$$
• Esto es una consecuencia directa del algoritmo y la relación se puede describir a través de la identidad binomial:

\begin{align*} \sum_{m=1}^{j}\binom{n-m}{n-j}\binom{n}{m}k^n&+\sum_{m=1}^{n-j}\binom{n-m}{j-1} =\binom{n}{j}(k+1)^n \end{align*}

Answer 2

Observaciones

El caso de $n=2$ resulta claramente de los números cuadrados que se representan como la suma $1+3+5+7+9\dots$

Sin embargo, el examen de los poderes superiores revela una relación con el triángulo de Pascal.

Utilizando las funciones:

fn[nu_][{o_, a_}] := {# - 1, Delete[a, #]} &@Mod[nu + o, Length@a, 1]
ff[n_, w_] := Last@NestList[fn[n], {0, w}, Floor[Length@w/n]][[All, 2]]
f1[l_] := Table[Total[Take[l, a]], {a, 1, Length@l}]

ajuste $\text{range}=n$

n = 4; list = Range@(n^2);
aa = NestList[{#[[1]] - 1, f1[ff[#[[1]], #[[2]]]]} &, {n, list}, 
n - 1][[All, 2]] // ColumnForm

da

\begin{array}{c} \{1,2,3,4\} \\ \{1,3,6\} \\ \{1,4\} \\ \{1\} \\ \end{array}

que es el triángulo de Pascal, y poniendo $\text{range}=n^{2}$

n = 4; list = Range@(n^2);
aa = NestList[{#[[1]] - 1, f1[ff[#[[1]], #[[2]]]]} &, {n, list}, 
n - 1][[All, 2]] // ColumnForm

da

\begin{array}{c} \{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16\} \\ \{1,3,6,11,17,24,33,43,54,67,81,96\} \\ \{1,4,15,32,65,108,175,256\} \\ \{1,16,81,256\} \\ \end{array}

con $\{1,16,81,256\}$ ser $\{1^{4},2^{4},3^{4},4^{4}\}$ como se describe en la pregunta.

Los últimos números de cada línea son $\{16,96,256,256\}$ y seguir el siguiente patrón:

$\left\{\dfrac{16}{96},\dfrac{96}{256},\dfrac{256}{256}\right\}=\left\{\dfrac{1+1}{n^2- n},\dfrac{2+1}{n^2-2 n},\dfrac{3+1}{n^2-3 n}\right\}$

que da la identidad

\begin{align} &\prod _{k=1}^{n-1} \frac{(k+1) n^2}{n^2-k n}&=\frac{(-n)^{n-1} \Gamma (n+1)}{(1-n)_{n-1}}&\tag{1}\\ \end{align}

dando la esperada $n^{n}.$

Mirando el $n^{2}$ caso de nuevo en su totalidad para como lo da la descripción del algoritmo en la pregunta, es evidente que cualquier número en línea $\color{blue}a$ es la suma de todos los números de la línea $\color{blue}b$ por encima de ella:

\begin{matrix} \color{blue}a&&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16 \\ \color{blue}b&&1&2&3&5&6&7&9&10&11&13&14&15 \\ \color{blue}a&&{1}&{3}&{6}&{11}&{17}&24&33&43&54&67&81&96 \\ \color{blue}b&&\color{red}1&\color{red}3&\color{red}{11}&\color{red}{17}&\color{red}{33}&\color{red}{43}&67&81 \\ \color{blue}a&&1&4&15&32&65&\color{red}{108}&175&256 \\ \color{blue}b&&1&15&65&175 \\ \color{blue}a&&1&16&81&256 \\ \end{matrix}

n = 4; list = Range@(n^2);
fn[nu_][{o_, a_}] := {# - 1, Delete[a, #]} &@Mod[nu + o, Length@a, 1]
ff[n_, w_] := Last@NestList[fn[n], {0, w}, Floor[Length@w/n]][[All, 2]]
f1[l_] := Table[Total[Take[l, a]], {a, 1, Length@l}]
aa = NestList[{#[[1]] - 1, f1[ff[#[[1]], #[[2]]]]} &, {n, list}, n - 1][[All, 2]];
ab = Most@Flatten[Transpose[{aa, bb = Table[ff[n - x,aa[[x + 1]]],{x, 0, n - 1}]}], 1];
ab // ColumnForm

Otro punto de interés es una posible relación con un análogo del triángulo de Pascal para generar potencias:

\begin{matrix} \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}1 & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10}&\sum\\ \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{black}1 & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10}&1\\ \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{black}1 & \color{white}{10} & \color{black}1 & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10}&2\\ \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{black}1 & \color{white}{10} & \color{black}2 & \color{white}{10} & \color{black}1 & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10}&4\\ \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{black}1 & \color{white}{10} & \color{black}3 & \color{white}{10} & \color{black}3 & \color{white}{10} & \color{black}1 & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10}&8\\ \color{white}{10} & \color{white}{10} & \color{black}1 & \color{white}{10} & \color{black}4 & \color{white}{10} & \color{black}6 & \color{white}{10} & \color{black}4 & \color{white}{10} & \color{black}1 & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10}&16\\ \color{white}{10} & \color{black}1 & \color{white}{10} & \color{black}5 & \color{white}{10} & \color{black}10 & \color{white}{10} & \color{black}10 & \color{white}{10} & \color{black}5 & \color{white}{10} & \color{black}1 & \color{white}{10} & \color{white}{10} & \color{white}{10}&32\\ \color{black}1 & \color{white}{10} & \color{black}6 & \color{white}{10} & \color{black}15 & \color{white}{10} & \color{black}20 & \color{white}{10} & \color{black}15 & \color{white}{10} & \color{black}6 & \color{white}{10} & \color{black}1 & \color{white}{10} & \color{white}{10}&64\\ \end{matrix}

donde la suma de cada fila da como resultado los números cuadrados. Lo mismo puede hacerse con los cubos:

...cuyas entradas son los coeficientes de $(x + 2)\text{Row Number}$ , en lugar de $(x + 1)\text{Row Number}$ :

\begin{matrix} \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}1 & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10}&\sum\\ \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{black}1 & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10}&1\\ \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{black}1 & \color{white}{10} & \color{black}2 & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10}&3\\ \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{black}1 & \color{white}{10} & \color{black}4 & \color{white}{10} & \color{black}4 & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10}&9\\ \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{black}1 & \color{white}{10} & \color{black}6 & \color{white}{10} & \color{black}12 & \color{white}{10} & \color{black}8 & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10}&27\\ \color{white}{10} & \color{white}{10} & \color{black}1 & \color{white}{10} & \color{black}8 & \color{white}{10} & \color{black}24 & \color{white}{10} & \color{black}32 & \color{white}{10} & \color{black}16 & \color{white}{10} & \color{white}{10} & \color{white}{10} & \color{white}{10}&81\\ \color{white}{10} & \color{black}1 & \color{white}{10} & \color{black}10 & \color{white}{10} & \color{black}40 & \color{white}{10} & \color{black}80 & \color{white}{10} & \color{black}80 & \color{white}{10} & \color{black}32 & \color{white}{10} & \color{white}{10} & \color{white}{10}&243\\ \color{black}1 & \color{white}{10} & \color{black}12 & \color{white}{10} & \color{black}60 & \color{white}{10} & \color{black}160 & \color{white}{10} & \color{black}240 & \color{white}{10} & \color{black}192 & \color{white}{10} & \color{black}64 & \color{white}{10} & \color{white}{10}&729\\ \end{matrix}

f[k_, a_] :=  
Join[{1}, Table[k*a[[n]] + a[[n + 1]], {n, 1, Length@a - 1}], {k^Length@a}]
a = {1}; k = 4; max = 10;
Column[tab = NestList[{#[[1]], f[#[[1]], #[[2]]]} &, {k, a}, max][[All, 2]], Center]
Table[Total[tab[[n]]], {n, 1, Length@tab}]

Tengo curiosidad por saber si estas observaciones pueden explicarse con más rigor, de ahí la recompensa.

Answer 3

Puedes calcular las fórmulas cerradas de las sumas de potencias naturales mediante diferencias finitas. Lo que quiero decir es lo siguiente:

http://mathforum.org/library/drmath/view/56982.html

Lo que parece que se hace es calcular directamente las propias potencias mediante diferencias finitas.