# How to prove a numerical identity?

Let be a function power function

f[s_, r_] := Piecewise[{{s^r, s >= 0}, {0, True}}];


And its convolution

Conv[s_, r_] := Sum[f[k, r]*f[s - k, r], {k, -Infinity, +Infinity}];


Proposition 1. Let be a real coefficients $$A_{m,j}$$ defined as follows

A[n_, k_] := 0
A[n_, k_] := (2 k + 1)*Binomial[2 k, k]*
Sum[A[n, j]*Binomial[j, 2 k + 1]*(-1)^(j - 1)/(j - k)*
BernoulliB[2 j - 2 k], {j, 2 k + 1, n}] /; 2 k + 1 <= n
A[n_, k_] := (2 n + 1)*Binomial[2 n, n] /; k == n;


Then for every $$n,m \in \mathbb{N}$$ there is an identity,

$$n^{2m+1}+1=\sum_{r=0}^{m}A_{m,r}\mathrm{Conv}_r[n], \ n>0 \ \tag1$$ where $$\mathrm{Conv}_r[n]=(f_{r}*f_{r})[n]=\sum_{t}f_r(t)f_r(n-t)$$.

Expression $$(1)$$ is implemented in Mathematica as folows

MainIdentity[m_, n_] := Sum[A[m, r]*Conv[n, r], {r, 0, m}];


And numerically it is equal to $$n^{2m+1}$$ for any naturals $$m,n$$, for example the tabular arrangement

n = 3; Table[MainIdentity[m, n], {m, 0, 11}]


gives

{4, 28, 244, 2188, 19684, 177148, 1594324, 14348908, 129140164}


Which is set of $$3^{2m+1}+1, \ m=0,1,2,3.. \$$. But when the condition is checked by mathematica with == operator,

FullSimplify[MainIdentity[m, n], Assumptions -> n > 0] ==
First@FullSimplify[n^(2 m + 1) + 1, Assumptions -> n > 0]


it gives False.

Question 1: Is there any other methods of comparison, so we can verify the formula $$(1)$$ ?

Question 2: Execution time of the Mathematica implementation of $$(1)$$ is very slow, can we optimaze the solution in order to decrese exec. time ?

• An important question: What is 0^0 for you? – Henrik Schumacher Apr 6 at 9:36
• For Q1 you can use PossibleZeroQ to check if the difference between the expressions is zero: reference.wolfram.com/language/ref/PossibleZeroQ.html – Roman Apr 6 at 9:38
• What's the purpose of First in [...] == First@FullSimplify[n^(2 m + 1) + 1, Assumptions -> n > 0]. Not that it returns 1! – Henrik Schumacher Apr 6 at 9:48
• @HenrikSchumacher I think now it is common agreement that $0^0 = 1$, I prefer to reffer it to Knuth's Concrete mathematics. Concerning First I dont really know Mathematica well, so I just entered my function into the pattern I found in one of my previous questions here – Petro Kolosov Apr 6 at 9:48
• When n or k is not numerical, the conditions 2 k + 1 <= n and k == n are not evaluated and A[n,k] evaluates to the first, unconditioned definition of A which is 0. So in total, your definition of A is not appropriate for symbolic evaluation. – Henrik Schumacher Apr 6 at 10:32

Towards Question 2: Make it a finite sum in Conv. Indeed, there are only finitely many nonzero summands. Or better use Dot.

f2[s_, r_] := s^r UnitStep[s];
Conv2[s_, r_] := #.Reverse[#] &[f2[Range[0, s], r]]

m = 10;
aa = Outer[Conv, Range[0, m], Range[1, m]]; // AbsoluteTiming // First
bb = Outer[Conv2, Range[0, m], Range[1, m]]; // AbsoluteTiming // First
aa == bb


11.0072

0.001253

True

• As I see you use == on the values of Timings or ? Still, the main aim is to show that MainIdentity[m_, n_] == n^(2m+1)+1. – Petro Kolosov Apr 6 at 9:53
• How to check identity $(1)$ in main question ? – Petro Kolosov Apr 6 at 10:08
• I applied == to the outputs of Conv and Conv2 in order to check that the produce the same results. The timings are supposed to show you that the new definition of Conv and f lead to 10000-times faster evaluation for numeric input. – Henrik Schumacher Apr 6 at 10:31