Rewrite the power sum in terms of convolution

Question

Let be an identity $$n^{2m+1}=\sum_{r=0}^{m}A_{m,r}\sum_{k=0}^{n-1}k^r(n-k)^r,$$ where $A_{m,r}$ are real coefficients, see A302971 for numerators and formula of $A_{m,r}$. Here we can notice that $\sum_{k=0}^{n-1}k^r(n-k)^r$ is discrete convolution of power function it itself, defined on finite interval $[0,n-1]$. Let's define the power function $f_{r,n-1}(s)$, such that $f_{r,n-1}(s)*f_{r,n-1}(s)\equiv\sum_{k=0}^{n-1}k^r(n-k)^r$ $$f_{r,n}(s)=\begin{cases} s^r, \quad s\in[0,n],\\ 0, \quad otherwise. \end{cases}$$ So, now it would be smoothly seen that convolution of $f_{r,n-1}(n-1)$ to itself should be equal to $\sum_{k=0}^{n-1}k^r(n-k)^r$. The following code should have verify it, but it seems to me that it contains some mistakes,

f[m_, s_, n_] := Piecewise[{{s^m, 0 < s < n}, {0, True}}];
DiscreteConvolution[m_, n_] := 
  Sum[f[m, n - k, n]*f[m, k, n], {k, -Infinity, +Infinity}];
F[m_, t_] := DiscreteConvolution[t, m];
T[n_, k_] := F[n - k + 1, k];
Column[Table[T[n, k], {n, 0, 10}, {k, 0, n}], Left]

By this state, it gives correct convolution values of power function over $n$ as columns of the following table

 {{0}},
 {{1, 0}},
 {{2, 1, 0}},
 {{3, 4, 1, 0}},
 {{4, 10, 8, 1, 0}},
 {{5, 20, 34, 16, 1, 0}},
 {{6, 35, 104, 118, 32, 1, 0}},
 {{7, 56, 259, 560, 418, 64, 1, 0}},
 {{8, 84, 560, 2003, 3104, 1510, 128, 1, 0}},
 {{9, 120, 1092, 5888, 16003, 17600, 5554, 256, 1, 0}},
 {{10, 165, 1968, 14988, 64064, 130835, 101504, 20758, 512, 1, 0}}

But if I change the definition of function f[m_, s_, n_] from n->n-1 it produces the wrong values of convolutions. For instance, the discrete analog of above code

Unprotect[Power];
Power[0 | 0., 0 | 0.] = 1;
Protect[Power];
F[m_, t_] := Sum[k^t (m - k)^t, {k, 0, m - 1}];
T[n_, k_] := F[n - k, k];
Column[Table[T[n, k], {n, 0, 10}, {k, 0, n}], Left]

gives the correct result

 {{0}},
 {{1, 0}},
 {{2, 0, 0}},
 {{3, 1, 0, 0}},
 {{4, 4, 1, 0, 0}},
 {{5, 10, 8, 1, 0, 0}},
 {{6, 20, 34, 16, 1, 0, 0}},
 {{7, 35, 104, 118, 32, 1, 0, 0}},
 {{8, 56, 259, 560, 418, 64, 1, 0, 0}},
 {{9, 84, 560, 2003, 3104, 1510, 128, 1, 0, 0}},
 {{10, 120, 1092, 5888, 16003, 17600, 5554, 256, 1, 0, 0}}

That proves an identity $$n^{2m+1}=\sum_{r=0}^{m}A_{m,r}\sum_{k=0}^{n-1}k^r(n-k)^r,$$ The problem: How to redefine function f[m_, s_, n_] in existing code, such that it will produce correct values of convolution over various intervals ? Or how to rewrite the last one code in terms of convolutions of power function ?

Answer 1

Let's focus on the part that is giving you trouble: the term $\sum_{k=0}^{m-1}k^t(m-k)^t$, which is written in code as:

Sum[k^t (m - k)^t, {k, 0, m - 1}]

For example, with m=30, you get:

Your stated goal is to express this in term of a discrete convolution. Here's one way to do that. Let

kt = Range[0, 30]^t;

be one of the signals. Then the sum is equal to

conv = ListConvolve[kt, kt]

which turns the sum into a convolution. I have chosen to use ListConvolve because your convolution is over a finite number of terms whereas DiscreteConvolve is taken over a (doubly infinite) series, that is, over all k from -Infinity to +Infinity. To see these are the same:

FullSimplify[Sum[k^t (m - k)^t, {k, 0, m - 1}], Assumptions -> t > 0] === 
First@FullSimplify[conv, Assumptions -> t > 0]

returns True. The t>0 assumption is needed because otherwise the term 0^t is undefined.