22
$\begingroup$

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 = {1n, 2n, 3n, 4n ...}


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 {13, 23, 33, 43, 53 ...}

$\endgroup$
5
  • 2
    $\begingroup$ What kind of information are you after? $\endgroup$ – user141592 Nov 16 '14 at 23:01
  • 1
    $\begingroup$ First, why the hell this algorithm works?!?! :D Second, can i find a research or something like this about it? Third who is the autor of this epicness? $\endgroup$ – mr-fotev Nov 16 '14 at 23:02
  • 2
    $\begingroup$ Welcome to Math.SE. While your enthusiasm is appreciated, your question should tell Readers what you are asking. Comments are somewhat peripheral and may be deleted after the purpose of clarifying the Question has been served. For more about participating here, take the Tour and read through the FAQ of the Help Center. $\endgroup$ – hardmath Nov 16 '14 at 23:09
  • $\begingroup$ What does "do s[i] += s[i-1]" mean? $\endgroup$ – Christian Blatter Nov 21 '14 at 19:00
  • 1
    $\begingroup$ @ChristianBlatter: It should be more precisely denoted as $s^{(n-1)}[i]=s^{(n)}[i]+s^{(n-1)}[i-1]$, so that $s^{(n-1)}[i]=\sum_{j=1}^{i}s^{(n)}[i]$ becomes in round $n-1$ the partial sum of the first $i$ elements of $s^{(n)}$ from the predecessor round $n$. After all I would really appreciate if you could add an answer to this question. Best regards, $\endgroup$ – Markus Scheuer Nov 21 '14 at 23:34
14
+100
$\begingroup$

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

$\endgroup$
11
  • $\begingroup$ looks great so far - nice work! :) $\endgroup$ – martin Nov 22 '14 at 1:02
  • $\begingroup$ @martin: Thanks, Martin! :-) $\endgroup$ – Markus Scheuer Nov 22 '14 at 6:32
  • $\begingroup$ @martin: While sitting at breakfast I had a look at my answer and found a striking coincidence of the intermediate solutions of the recurrence systems! $n=2: 2n+1, (n+1)^2$ and $n=3: 3n+1, 3n^2+3n+1, (n+1)^3$. You see? ... We have the precise description of the $j$-th component of $\psi_n^{(k)}$ at hand! It is $\sum_{l=0}^{j}\binom{n}{j}n^j$. I think the general proof could be soon available! I'll elaborate it tomorrow. :-) $\endgroup$ – Markus Scheuer Nov 22 '14 at 7:19
  • $\begingroup$ Yes! I was quite a way behind you - I had a go dividing each row by $n^k$ for $k<n$ and noticed that the integer solutions were revealingly regular! It is an interesting problem, but an explanation is well within reach I feel. Looking forward to your updates - I will continue to contemplate it too :) $\endgroup$ – martin Nov 22 '14 at 9:46
  • $\begingroup$ @martin: I'm also thinking about it and it seems it actually becomes rather simple! The essence is the representation $k^n=((k-1)+1)^n$ :-) But of course, this has to be elaborated and explained! :-) $\endgroup$ – Markus Scheuer Nov 22 '14 at 9:58
5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks for the answer, but I don't see how the algorithm exploits this phenomenon... Your strategy is "Construct the Pascal triangle but before addition multiply the left element with k." On each $i-th$ row of the resulting rows you have the coefficents in $(x+k)^i$ and when $x=1$ you get $(1+k)^i$ ... Well, I still can't see how this helps... What about the "dropping" part? What actually this procedure represents? $\endgroup$ – mr-fotev Nov 18 '14 at 18:05
  • $\begingroup$ @john_devou the point is that Pascal's triangle can be constructed using the method you describe -not the other way around. I am not saying it is a necessary condition to construct pt, but that your method is inherantly linked to it. $\endgroup$ – martin Nov 19 '14 at 0:35
0
$\begingroup$

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

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

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

$\endgroup$
1
  • $\begingroup$ Hi, Kevin! The interesting aspect was not how to calculate $n$-th powers? You would do it typically with the help of Bernoulli polynomials. The interesting thing was how does it work when using the algorithm? You see? :-) Regards, $\endgroup$ – Markus Scheuer Nov 25 '14 at 8:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.