A Maple One-Line Proof of George Andrews’s Theorem that the Number of Triangles with Integer Sides Whose Perimeter is n Equals \{\frac{n^{2}}{12} \} − ⌊\frac{n}{4}⌋⌊\frac{n+2}{4}⌋

Shalosh B. EKHAD ^{1}

evalb(seq(coeff(taylor(q^3/(1-q^2)/(1-q^3)/(1-q^4),q=0,37),q,i),i=0..36)
=seq(round(n^2/12)-trunc(n/4)*trunc((n+2)/4),n=0..36));

Comments by Doron Zeilberger

1. The succinct formula of the title was discovered and first proved by George Andrews[A1], in a less-than-one-page cute note, improving a four-page note by Jordan et. al. [JWW]. Andrews’s note, while short and sweet, is not self-contained, and refers to results from his classic [A2].

2. Here is a justification of the Maple one-line. Arrange the lengths of the sides of a typical integerside triangle in non-increasing order, and write them as [a + b + c + 1, b + c + 1, c + 1] for a, b, c ≥ 0. By [E] I.20, (b+c+1)+(c+1) > a+b+c+1, so c ≥ a, so c = a+t for t ≥ 0. So a generic integer-side triangle can be written as [a+b+(a+t)+1, b+(a+t)+1, a+t+1] = [2a+b+t+1, a+b+t+1, a+t+1], and hence the number of triangles with integer sides whose perimeter equals n is the coefficient of q^{n} in

∑_{a,b,t≥0} q^{(2a+b+t+1)+(a+b+t+1)+(a+t+1)} = ∑_{a,b,t≥0} q^{4a+3t+2b+3} = q^{3} (∑_{a≥0} q^{4a}) (∑_{t≥0} q^{3t}) (∑_{b≥0} q^{2b}) =

\frac{q^{3}}{(1 − q^{4})(1 − q^{3})(1 − q^{2})} .

The coefficient of q^{n} is obviously a quasi-polynomial of degree 2 and “period” lcm(2, 3, 4) = 12, but so is \{\frac{n^{2}}{12} \} − ⌊\frac{n}{4}⌋⌊\frac{n+2}{4}⌋, hence it suffices to check that the first (2 + 1) · 12 + 1 = 37 values match.

3. This is yet another example, where “physical” (as opposed to “mathematical”) induction, i.e. checking finitely (and not that many!) special cases constitutes a perfectly rigorous proof! No need for the “simple” argument by “mathematical” induction alluded to by Andrews in his note. In this case we were in the quasi-polynomial ansatz. See [Z1][Z2], as well as the future classic [KP].

References

[A1] A note on partitions and triangles with integer sides, Amer. Math. Monthly 86 (1979),477-478.

[A2] G. E. Andrews, “The Theory of Partitions, Addison-Welsley, 1976. Reprinted by Cam- bridge University Press, 1984. First paperback edition, 1998.

1 ShaloshBEkhad@gmail.com .

Exclusively published in: http://www.math.rutgers.edu/~zeilberg/pj.html and http://arxiv.org/ .

Feb. 4 2012.

[E] Euclid, “The Elements”, Alexandria University Press, ca. 300 BC.

[JWW] J.H. Jordan, R. Walch, and R.J. Wisner, Triangles with integer sides, Amer. Math. Monthly 86 (1979), 686-689.

[KP] M. Kauers and P. Paule, “The Concrete Tetrahedron”, Springer, 2011

http://www.springer.com/mathematics/analysis/book/978-3-7091-0444-6 .

[Z1] D. Zeilberger, Enumerative and Algebraic Combinatorics, in: “Princeton Companion to Mathematics” , (Timothy Gowers, ed.), Princeton University Press, pp. 550-561, 2008.

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/enu.pdf

[Z2] D. Zeilberger, An Enquiry Concerning Human (and Computer!) [Mathematical] Understanding, in: C.S. Calude, ed., “Randomness & Complexity, from Leibniz to Chaitin” World Scientific, Singapore, 2007.

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/enquiry.pdf