Some Remarks on a recent article by J. -P. Allouche

Shalosh B. EKHAD and Doron ZEILBERGER

In a recent article [A], the author tries very hard to “explain” a puzzling remark made by Otto G. Ruehr in his solution [R] to American Mathematical Monthly elementary problem E2765 (proposed in 1979 by Naoki Kimura).

Frankly, we don’t see the point of going to such great lengths to prove that routinely-provable identity A implies routinely-provable identity B. It is much faster to prove them both from scratch. As we will soon see, Ruehr’s remark was most probably a non-sequitur, and it is very unlikely that it followed [A]’s exegesis.

The original problem was to prove that for every continuous function f the following identity holds

∫− \frac{1}{2}^{\frac{3}{2}} f(3x^{2} − 2x^{3}) dx = 2 ∫_{0}^{1} f(3x^{2} − 2x^{3}) dx .

After giving his change-of-variable proof, Ruehr makes the following remark.

“An interesting alternative approach would be to use the Weierstrass Approximation Theorem to reduce that problem to that of a polynomial f, and in turn, by linearity to that of establishing the given equation for f(z) = z^{n}.”

In other words one had to prove, that for every non-negative integer n,

∫− \frac{1}{2}^{\frac{3}{2}} (3x^{2} − 2x^{3})^{n} dx = ∫_{0}^{1} 2 (3x^{2} − 2x^{3})^{n} dx .  (Ruehr)

While this was non-trivial back in 1980, it is routinely provable today, using the Almkvist-Zeilberger algorithm [AZ], implemented in the Maple package EKHAD.txt [Z]. Just type:

AZdI((3*x**2-2*x**3)**n,x,n,N,-1/2,3/2)[1];  AZdI(2*(3*x**2-2*x**3)**n,x,n,N,0,1)[1];

for the left and right sides, respectively, and in a split second you would get the same output:

[9 (n + 1) (2 n + 1) - 2 (3 n + 4) (3 n + 2) N, 2] ,

which means that both the left side and the right side satisfy the first-order inhomogeneous linear recurrence equation with polynomial coefficients

9(n + 1)(2n + 1)f(n) − 2(3n + 4)(3n + 2)f(n + 1) = 2 .

Since L(0) = R(0) = 2, this immediately implies (Ruehr), without any need for a clever change of variable.

If you take Ruehr’s suggestion literally, then you would get a certain binomial coefficients identity that is easily provable by the Zeilberger algorithm, supplying yet another routine proof. This summation identity, that the reader can easily derive by using the binomial theorem on (3 − 2x)^{n} and integrating term-by-term (as suggested in [R]) has nothing whatsoever to do with the following two binomial coefficients identities that Ruehr claims are ‘equivalent’. We would never know what Ruehr had in mind (he probably got mixed up with another problem), and frankly we don’t really care. At any rate, we are sure that it is not via Allouche’s extremely circuitous route.

These ‘equivalent’ (per Ruehr) identities are

∑_{j=0}^{2n}(−4)^{j}\binom{3n + 1}{n + j + 1} = ∑_{j=0}^{n} 2^{j}\binom{3n + 1}{n − j} ,

∑_{j=0}^{2n}(−3)^{j}\binom{3n − j}{n} = ∑_{j=0}^{n} 3^{j}\binom{3n − j}{2n} .

As already pointed out in [MTWZ] these two new identities (that, in spite of [A], are completely unrelated to the original integral identity (Ruehr)) are also routinely provable with Maple. In fact it is also strange that they are listed as two different identities. All four sums happen to be identical.

Go into Maple, and type

Z:=SumTools[Hypergeometric][ZeilbergerRecurrence];  ,

then type

Z(3**j*binomial(3*n-j,2*n),n,j,f,0..n);  Z((-3)**j*binomial(3*n-j,n),n,j,f,0..2*n);
Z(2**j*binomial(3*n+1,n-j),n,j,f,0..n);Z((-4)**j*binomial(3*n+1,n+j+1),n,j,f,0..2*n);

and find out, in one nano-second, that all four sums satisfy the same linear recurrence, namely

−27 f (n) + 4 f (n + 1) = −3 \frac{(3n + 1)!}{(2n + 1)!(n + 1)!}

As also pointed out in [MTWZ] these four sums are all equal to OEIS sequence A6256 [S] whose definition is yet another binomial coefficient sum

∑_{k=0}^{n} \binom{3k}{k}\binom{3n − 3k}{n − k} .

Typing

Z(binomial(3*k,k)*binomial(3*n-3*k,n-k),n,k,f,0..n);

gives that it satisfies a second-order homogeneous linear recurrence equation with polynomial coefficients

−81 (3 n + 2) (3 n + 4) f (n)+(216 n^{2} + 594 n + 420) f (n + 1)−8 (2 n + 3) (n + 2) f (n + 2) = 0 ,

that is routinely equivalent to the above first-order inhomogeneous recurrence for the Ruehr sums.

Conclusion

In the conclusion to [A], the author states

“The literature about sums involving binomial coefficients is huge.”

He should have added,

“... and mostly obsolete^{1} (thanks to the Wilf-Zeilberger [PWZ] algorithmic proof theory, implemented in Maple, Mathematica and other systems)”.

Both the integral formula with f(z) = z^{n} and the two binomial coefficients identities, are nowadays routinely provable, and it has very little mathematical interest to do exegesis of what Ruehr had in mind. Of course, it may be of some psychological or literary interest. After all literary scholars often go to great lengths to try and understand ‘what the great poet had in mind’, and most often get it wrong. Often the poet had nothing in mind, and if she did, it was something very mundane.

Parody

Let’s use an analogy. Suppose that in the American Mathematical Monthly analog of Egypt in 5000BC there was a papyrus that gives an elegant proof of the identity

123 · 321 = 39483 ,  (1)

and then it comments that it is equivalent to

111 · 449 = 49839 ,  (2)

but that the latter identity is no easier to prove than the former one. In a logical sense, that ancient savant would have been right, since all correct statements are logically equivalent. But some mathematical historian could have been tempted to ‘explain’ how Professor Ahmes may have reasoned. Since 111 = (123 − 12) and 449 = 321 + 128 (proofs left to the reader), we have

111 · 449 = (123 − 12)(321 + 128) = 123 · 321 + 123 · 128 − 12 · 321 − 12 · 128
= 123 · 321 + 15744 − 3582 − 1536 .

1 There is still room for elegant and insightful combintorial proofs of such identities, of course, see [MTWZ] for two

such gorgeous proofs.

Using Eq. (1), the first product equals 39483, and it follows that indeed

111 · 449 = 39483 + 15744 − 3852 − 1536 = 49839 QED.

With all due respect, it is much easier to prove identities (1) and (2) separately, than to only prove (1) and then to deduce (2) from it.

Postscript (Added March 23, 2019)

It turns out that the two sequences, A(n) := ∫_{0}^{1} (3x^{2} − 2x^{3})^{n} dx and B(n) := ∑_{j=0}^{n} 2^{j}\binom{3n+1}{n−j} (that equals the other three binomial coefficients sums), are related. In fact

A(n) = \frac{(2n)!n!}{(3n + 1)!} B(n) .

This follows by ‘solving’ the two first-order linear inhomogeneous recurrences derived above for A(n) and B(n), in terms of indefinite sums (A(n) is defined as a definite integral and B(n) as a definite sum).

Solving the recurrences 9(n + 1)(2n + 1)A(n) − 2(3n + 4)(3n + 2)A(n + 1) = 1 and −27 B (n) + 4 B (n + 1) = −3 \frac{(3n+1)!}{(2n+1)!(n+1)!} derived above yields that

B(n) = (\frac{27}{4})^{n} (1 − ∑_{k=1}^{n}(\frac{4}{27})^{k} \frac{(3k − 2)!}{(2k − 1)!k!}) ,

with a similar formula for A(n) that proves that A(n)/B(n) = \frac{(2n)!n!}{(3n+1)!}. Alternatively, performing the dependent change of variable A(n) = \frac{(2n)!n!}{(3n+1)!} B(n) on the recurrence for A(n) yields the recurrence for B(n).

PostPostscript (Added March 24, 2019) In hindsight, the binomial coefficients identity

∑_{j=0}^{2n}(−4)^{j}\binom{3n + 1}{n + j + 1} = ∑_{j=0}^{n} 2^{j}\binom{3n + 1}{n − j} ,  (RuehrSum)

is ‘equivalent’ to the integral identity

∫− \frac{1}{2}^{\frac{3}{2}} (3x^{2} − 2x^{3})^{n} dx = ∫_{0}^{1} 2 (3x^{2} − 2x^{3})^{n} dx .  (RuehrIntegral)

Multiplying both sides of (RuehrSum) by \frac{(2n)!n!}{(3n+1)!}, simplifying, replacing \frac{n!j!}{(n+j+1)!} in the left sum and \frac{(2n)!j!}{(2n+j+1)!} in the right sum by ∫_{0}^{1} x^{n}(1 − x)^{j} and ∫_{0}^{1} x^{2n}(1 − x)^{j} respectively, and using the binomial theorem, leads to the following integral identity

∫_{0}^{1} x^{n}(4x − 3)^{2n} dx = ∫_{0}^{1} x^{2n}(3 − 2x)^{n} dx ,

that is presuambly equivalent to (RuehrIntegral).

References

[A] J. -P. Allouche, Two binomial identities of Ruehr Revisited, Amer. Mathematical Monthly, 126(3) [March 2019], 217-225.

[AZ] Gert Almkvist and Doron Zeilberger, The method of differentiating under the integral sign J. Symbolic Computation 10 (1990), 571-591. Available from

http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/duis.html .

[MTWZ] Sean Meehan, Akalu Tefera, Michael Weselcouch, and Aklilu Zeleke, Proof os Ruehr’s identities, INTEGERS 14 (2014), #A10 (6 pages) .

[PWZ] Marko Petkovsek, Herbert S. Wilf, and Doron Zeilberger, “A=B”, A.K. Peters, 1996. Freely available from

https://www.math.upenn.edu/~wilf/AeqB.html .

[R] Otto G. Ruehr, Solution to Problem E2765 (proposed by Naoki Kimura), Amer. Mathematical Monthly, 87(4) [April 1980], 307-308.

[S] Neil Sloane, OEIS sequence A006256 http://oeis.org/A006256.

[Z] Doron Zeilberger, EKHAD.txt, a Maple package freely available from

http://sites.math.rutgers.edu/~zeilberg/tokhniot/EKHAD.txt .

Shalosh B. Ekhad, c/o D. Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: ShaloshBEkhad at gmail dot com .

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: DoronZeil at gmail dot com .

Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger and arxiv.org .

First Written: Purim 5779 (alias March 21, 2019). This version: March 23, 2019.