List of powers of Natural Numbers

Question

Greatings,
  Some time ago a friend of mine showed me this astonishing algorithm and recently i tried to find some information about it on the internet but couldn't find anything... Please help.

Pseudocode:
Consider that 1 is the starting index of a list

1.  input natural number n.
2.  let s = list of all natural numbers {1, 2, 3, 4, 5, 6 ...}
3.  while (n>1) do
    3.1.  drop each n-th elementh from s
    3.2.  for int i = 2 to ∞ do s[i] += s[i-1]
    3.3.  n = n-1
4.  Now s = {1ⁿ, 2ⁿ, 3ⁿ, 4ⁿ ...}

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

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

perform 3.1:  s = {1, 7, 19, 37, 61, 91 ...}
perform 3.2:  s = {1, 8, 27, 64, 125, 216 ...}
perform 3.3:  n = 1 => end of while loop

The final state of s is {1³, 2³, 3³, 4³, 5³ ...}

Answer 1

Note: [2014-11-24] Some more simplifications done, some new aspects added and general proof now finalised. :-)

Note: This is a nice question describing an interesting sieve technique to generate $n$-th powers of natural numbers. It's also worth noting that there's an explicit relationship for fixed arbitrary $n$ which provides a hop from $k^n$ to $(k+1)^n$.

Let's start with a slight reformulation of the algorithm which may also be convenient.

Algorithm to generate $n$-th powers of natural numbers

Let $S=\{1,2,\ldots,N\} \subset \mathbb{N}$ and $n\in \mathbb{N}$.

• while ($n>1$) do

  • drop each $n$-th element from $S$

  • replace each $j-th$ element with the partial sum of the first $j$ elements

  • $n \rightarrow n-1$ (reduce $n$ by $1$)

Result: A finite set $S^\prime=\{1^n,2^n,3^n,\ldots\}$ containing only consecutive $n$-th powers starting from $1$.

Observe that in the question above $s[i] += s[i-1]$ should be more precisely denoted as \begin{align*} s^{(n-1)}[i]=s^{(n)}[i]+s^{(n-1)}[i-1],\tag{1} \end{align*} so that $s^{(n-1)}[i]=\sum_{j=1}^{i}s^{(n)}[j]$ becomes in round $n-1$ the partial sum of the first $i$ elements of $s^{(n)}$ from the predecessor round $n$.

First step: Examples

In order to see what's going on we take a look at two examples, namely at the powers of $n=5$ and $n=6$ which are small enough to be manageable, but also large enough to detect some essential aspects of the algorithm.

Example: $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}

Example: $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}

At first let's take a look at the example $n=5$ row-oriented:

• The first line consists of the numbers $1$ to $16$

• The next line has dropped each $5$-th entry and the values were replaced with their corresponding partial sums

• The following lines were changed accordingly

• The boldface entries $1,32,243,1024$ are the results $n^5: 1^5,2^5,3^5$ and $4^5$.

But even more interesting is to look at the example according to the triangular shapes:

• We can see three complete triangles and the first column of a forth triangle

• The leftmost triangle is a part of a Pascal triangle

• All following triangles follow exactly the same addition scheme as the Pascal triangle

• Attention: The italic entries summed up and incremented by one yield the values of the first column of the next triangle.

Let's have a look at the triangles more closely considering them as upper triangular matrices \begin{align*} T_{5,k}=\left(t_{i,j}^{(5,k)}\right)_{1\leq i,j\leq 5}\qquad k\geq 1 \end{align*}

Note: In the following I write vectors row-oriented without using the transpose symbol in order to enhance readability.

Top row of $T_{5,k}$

The general description of the first row of the $k$-th matrix $T_{5,k}$ is:

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

Minor diagonal of $T_{5,k}$

The elements of the minor diagonal

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

of the matrix $T_{5,k}$ show a nice relationship

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

Leftmost column of $T_{5,k}$

Observe that the entries of the leftmost column of $T_{5,k}$ are the sum of the elements of the minor diagonal of the predecessor matrix $T_{5,k-1}$ incremented by one. Therefore we get

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

Note, that the bottom entry of the leftmost column can be written in accordance with the description of the minor diagonal of $T_{5,k}$ as

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

---

General description of the upper diagonal matrix $T_{n,k}$:

Now we are in a position to describe the upper diagonal matrix $T_{n,k}$ in general

Proposition: The following statement is valid: The upper diagonal Matrix

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

characterized by the

• Top row of $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*}

and by the

• Leftmost column of $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*}

together with an

• Addition scheme corresponding to that of a Pascal Triangle:

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

has following properties

• The bottom element of the leftmost column is $k^n$:

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

• The elements of the minor diagonal

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

  fulfil

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

Proof: For each $n\geq 2$ fixed, arbitrary we prove the proposition by induction for $k \geq 1$

Let $n\geq 2$ be fixed, arbitrary.

Base case: $k=1$

We have to show that the upper triangle matrix $T_{n,1}, n\geq 2$ fulfils

• Top row of $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*}

The algorithm starts with $S=\{1,2,3,\ldots\}$. Since this is represented by the top row of $T_{n,k}$ which contains the $k-th$ block of $n$ consecutive numbers, the top row of $T_{n,1}$ contains the first $n$ natural numbers and the statement is true.

• Leftmost column of $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*}

Since the leftmost element $1$ is never changed by the algorithm, the leftmost column of $T_{n,1}$ is always $1$.

• Addition scheme corresponding to that of the Pascal Triangle

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

The addition scheme of the upper triangle of the matrix corresponds to the relationship (1) of the algorithm: \begin{align*} s^{(n-1)}[i]=s^{(n)}[i]+s^{(n-1)}[i-1] \end{align*} The zero in position $(2,n)$ corresponds to the fact, that in the first round of the algorithm each $n-th$ element has been dropped.

The zeros in position $(3,n-1)$ an $(3,n)$ correspond to the fact that in the second round of the algorithm each $(n-1)$-th element has been also dropped.

Continuing this way results in zeros filling the lower triangular part of the matrix $T_{n,1}$ and so the statement is true.

• The bottom element of the leftmost column is:

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

This is simply a consequence of the fact, that the leftmost column of the matrix contains only $1$s.

• The elements of the minor diagonal are:

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

The minor diagonal of $T_{n,1}$ is the $n$-th row of the Pascal Triangle and has therefore the entries $\binom{n}{j}$, with $1\leq j \leq n$ and the statement is true.

Conclusion: The base step is fulfilled.

Induction hypothesis: $k$

Let's assume the proposition is true for $k \geq 1$

Inductive step: $k \longrightarrow k+1$

• Top row of $T_{n,k+1}$:

According to the induction hypotheses the top row of $T_{n,k}$ is of the form \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*}

Since the $T_{n,k+1}$ is the successor matrix on the right hand side of $T_{n,k}$ the first row consists of the elements \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*} and the statement is true for $k+1$

• Leftmost column of $T_{n,k+1}$:

According to the induction hypothesis the minor diagonal of $T_{n,k}$ is of the form

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

Now, the elements $(t_{1,j}^{(n,k+1)})_{1\leq j \leq n}$ of the leftmost column of $T_{n,k+1}$ are according to the relationship (1) of the algorithm: \begin{align*} s^{(n-1)}[i]=s^{(n)}[i]+s^{(n-1)}[i-1] \end{align*} the partial sums of the minor diagonal of $T_{n,k}$ incremented by one

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

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

and the statement is true for $k+1$

• Addition scheme corresponding to that of the Pascal Triangle

Since the additions scheme is completely independent from $k$, the explanation already stated in the base case of this induction proof is also verbatim valid.

Therefore the statement is true for $k+1$.

• The bottom element of the leftmost column of $T_{n,k+1}$

The leftmost column is already known and so we get according to (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*}

So, the statement is true for $k+1$.

• The last point we have to show is: The elements of the minor diagonal

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

fulfil

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

Note: This is the most interesting step of the whole proof: The hop from one minor diagonal to the next:

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

In order to prove it we consider the relationship of the diagonal element $t_{j,n+1-j}^{(n,k+1)}$ with the elements of the top row and the elements of the leftmost column, which are already known. The relationship is given by the addition scheme (1) according to the Pascal Triangle.

In fact we have to do a little bit of lattice path calculation in order to derive this relationship.

---

Lattice pathes: Observe, the number $\binom{n}{k}$ can be considered as the number of lattice pathes of length $n$ containing $k$ horizontal $(1,0)$-steps and $n-k$ vertical $(0,1)$-steps.

This is valid because there are $\binom{n}{k}$ choices to select $k$ steps in horizontal direction leaving the remaining $n-k$ steps for the vertical direction.

Note: You might want to look at example 1 or example 2 if you are not familiar with this technique.

---

We will simplify the calculations by not starting at the top row and the leftmost column of $T_{n,k+1}$, but instead going one step back to the minor diagonal of $T_{n,k}$ an analyse an

extended Triangle $\widetilde{T}_{n,k+1}$

We consider the minor diagonal

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

of the upper triangular matrix $T_{n,k}$ as the first column of the next matrix $T_{n,k+1}$ and create an extended triangular matrix $\widetilde{T}_{n,k+1}$.

In doing so, we don't have to cope with the partial sums

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

of the elements of the first column of $T_{n,k+1}$ but we can instead use

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

We additionally complete the Pascal Triangle by adding a top row containing only $1s$

Observe, that the algorithm can be equivalently reformulated by starting with a top row containing only $1$s instead of starting with a top row of the natural numbers. We only have to perform an additional step by building first a sequence of partial sums to get the natural numbers before start dropping the $n$-th elements.

Example: $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}

The benefit is, that instead of multiplying combinatorial sums with the elements $(n(k+1)+j)$ of the top row of $T_{n,k+1}$ we can simply use the factor $1$.

Let's go back to the example $T_{6,2}$ from above and analyse the element $t_{4,3}^{(6,2)}=240$ with the help of the extended matrix $\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}

In the table above we see in the right triangle the number of pathes starting in $$t_{4,3}^{(6,2)}=240\qquad$$ and going to points of the leftmost column, resp. to points of the top row. From this pattern we deduce:

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

With this example in mind we can derive the general formula for the elements of the minor diagonal:

General formula for the hop from $\binom{n}{j}k^j$ to $\binom{n}{j}(k+1)^j$:

Let's assume we have an element $$t_{j,n-j+1}^{(n,k+1)}\qquad\qquad 1 \leq j \leq n$$ of the minor diagonal in the $j-th$ row and $n-j+1$ column of the original upper triangular matrix $T_{n,k+1}$, then we have to determine the number of pathes from $$(m,1)\qquad\text{to}\qquad(j,n-j+1) \qquad 1\leq m \leq j$$ corresponding to the leftmost column entries $(1,1)$ to $(j,1)$ and we have to determine the number of pathes from $$(1,m)\qquad\text{to}\qquad(j,n+1-j) \qquad 1\leq m \leq n-j+1$$ corresponding to the top row entries $(1,1)$ to $(1,n+1-j)$

Note: Let $0\leq x_1\leq x_2$ and $0\leq y_1\leq y_2$. The number of pathes $N_{(x_1,y_1)}^{(x_2,y_2)}$ from $(x_1,y_1)$ to $(x_2,y_2)$ is $$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}$$

We observe: The number of pathes from $(m,1)$ to $(j,n-j+1)$ and the number of pathes from $(1,m)$ to $(j,n-j+1)$ is $$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}$$

Now we can formulate the binomial identity which we have to proof to show the last part of the inductive step.

Binomial identity:

The following is valid for $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*}

We calculate each sum of (3) separately:

The first sum of the 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*}

The second sum of the 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*}

Observe that we have transformed the sum in (5) into a telescoping sum using the binomial identity \begin{align*} \binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1} \end{align*}

Now adding both expressions (4) and (5) and the RHS: $$t_{j,n+1-j}^{(n,k+1)}=\binom{n}{j}(k+1)^n, \qquad 1 \leq j \leq n, n \geq 2$$ follows.

Conclusion: Inductive step $k \longrightarrow k+1$ is korrect.

---

Summary:

• The analysis of the algorithm leads for fixed, arbitrary $n\geq 2$ to an analysis of successive upper triangular matrices $$T_{n,k} \qquad \longrightarrow \qquad T_{n,k+1}$$.
• Looking at examples for $n=5$ and $n=6$ yields an interesting relationship of the elements of the minor diagonal of successive matrices $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$$
• This is a direct consequence of the algorithm and the relationship can be described via the binomial identity:

\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

Observations

The case for $n=2$ clearly results from the square numbers being represented as the sum $1+3+5+7+9\dots$

Examining for higher powers however, reveals a relationship to Pascal's triangle.

Using the functions:

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}]

setting $\text{range}=n$

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

gives

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

which is Pascal's triangle, and setting $\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

gives

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

with $\{1,16,81,256\}$ being $\{1^{4},2^{4},3^{4},4^{4}\}$ as described in the question.

The last numbers of each line are $\{16,96,256,256\}$ and follow the following pattern:

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

which gives the identity

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

giving the expected $n^{n}.$

Looking at the $n^{2}$ case again in its full for as given by the description of the algorithm in the question, it is evident that any number in line $\color{blue}a$ is the sum of all numbers in line $\color{blue}b$ above it:

\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

Another point of interest is a possible relation to an analog of Pascal's triangle to generate powers:

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

where the sum of each row results in the square numbers. The same can be done for the cubes:

...whose entries are the coefficients of $(x + 2)\text{Row Number}$, instead of $(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}]

I am curious as to whether these observations can be explained more rigorously, hence the bounty.

Answer 3

You can calculate the closed form formulas for sums of natural powers using finite differences. What I mean is this:

Link

What this appears to be doing is directly calculating the the powers themselves using finite differences.