# Rewrite the power sum in terms of convolution

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 ?

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.

• This also gives a correct results, but I need have time to study on it. By the way, can you review my own codes ? May be can you see some errors ? – Petro Kolosov Mar 11 at 16:21
• I used your example as follows: f[n_, r_] := Range[0, n - 1]^r; conv[n_, r_] := ListConvolve[f[n, r], f[n, r]]; The verification gives False: FullSimplify[Sum[k^t (m - k)^t, {k, 0, m - 1}], Assumptions -> t > 0] === First@FullSimplify[conv[m, t], Assumptions -> t > 0] – Petro Kolosov Mar 11 at 18:35
• It surely needs to have something to work with... like a number for n. Look at conv[30,t] and you'll see it's identical to the corresponding sum. – bill s Mar 11 at 19:30
• Here the main idea to connect identity in odd power with convolutions of power difined on finite interval, above method gives wrong table using Column[Table[conv[n - k, k], {n, 0, 10}, {k, 0, n}], Left] and really I dont understand why – Petro Kolosov Mar 11 at 20:12
• direct substitution m=30 to FullSimplify[Sum[k^t (30 - k)^t, {k, 0, 30 - 1}], Assumptions -> t > 0] === First@FullSimplify[conv[30, t], Assumptions -> t > 0] gives False in my mathematica – Petro Kolosov Mar 11 at 20:19