HEXAGONbeta

Minimal recurrences for binomial power sums

A mix of human-written and AI-generated textHuman understanding: some partsmath.NT — Number Theorymath.GM — General Mathematics

Contributed by Khai-Hoan Nguyen-Dang ↗

Version 1 / Nov 02, 2026 / CC BY 4.0

Abstract

For every positive integer rr, we prove that the least order of a polynomial-coefficient recurrence for Fr(n)=∑k=0n(nk)rF_r(n)=\sum_{k=0}^n\binom nk^r is ⌊(r+1)/2⌋\lfloor(r+1)/2\rfloor. This establishes the unrestricted minimal-order assertion arising from Franel's work of 1894--1895. We also determine the least order ⌊r/2⌋\lfloor r/2\rfloor, for r≥2r\geq2, of the alternating sums (−1)n∑k=02n(−1)k(2nk)r(-1)^n\sum_{k=0}^{2n}(-1)^k\binom{2n}{k}^r. The lower bounds follow from real moment representations: every nonzero singularity of the representing measure forces a root of the leading characteristic polynomial of the recurrence. A common reflection argument gives telescoping recurrences attaining both bounds. For the ordinary sums, we combine the deformation of Straub and Zudilin with a shifted prime-power congruence to prove that the minimal shift operator is irreducible over $\C(n)$.

Provenance statement

During the development and preparation of this work, the author used ChatGPT (OpenAI), together with web-search to assist with mathematical exploration, refining proof strategies, checking mathematical arguments, and searching the literature.

Tools used

OpenAI
ChatGPTVersion Astra

References

  1. D. Batenkov, Moment inversion problem for piecewise D-finite functions, Inverse Problems 25 (2009), no. 10, 105001, 24 pp. doi:10.1088/0266-5611/25/10/105001 (https://doi.org/10.1088/0266-5611/25/10/105001).DOI
  2. A. Bostan, A. Elvey Price, A. J. Guttmann and J.-M. Maillard, Stieltjes moment sequences for pattern-avoiding permutations, Electronic Journal of Combinatorics 27 (2020), no. 4, Paper P4.20, 59 pp. doi:10.37236/9402 (https://doi.org/10.37236/9402).DOI
  3. A. Bostan, P. Lairez and B. Salvy, Multiple binomial sums, Journal of Symbolic Computation 80 (2017), 351--386. doi:10.1016/j.jsc.2016.04.002 (https://doi.org/10.1016/j.jsc.2016.04.002).DOI
  4. M. Chamberland and A. Straub, Apéry limits: Experiments and proofs, American Mathematical Monthly 128 (2021), no. 9, 811--824. doi:10.1080/00029890.2021.1962153 (https://doi.org/10.1080/00029890.2021.1962153).DOI
  5. T. W. Cusick, Recurrences for sums of powers of binomial coefficients, Journal of Combinatorial Theory, Series A 52 (1989), no. 1, 77--83. doi:10.1016/0097-3165(89)90063-0 (https://doi.org/10.1016/0097-3165(89)90063-0).DOI
  6. R. Dougherty-Bliss and D. Zeilberger, Exploring general Apéry limits via the Zudilin--Straub tt-transform, Journal of Difference Equations and Applications 29 (2023), no. 1, 32--42. doi:10.1080/ 10236198.2022.2159817 (https://doi.org/10.1080/10236198.2022.2159817).DOI
  7. J. W. Essam and A. J. Guttmann, Vicious walkers and directed polymer networks in general dimensions, Physical Review E 52 (1995), no. 6, 5849--5862. doi:10.1103/PhysRevE.52.5849 (https://doi.org/10.1103/PhysRevE.52.5849).DOI
  8. J. Franel, Question n o 42 (Laisant), L'Intermédiaire des Mathématiciens 1 (1894), 45--47.
  9. J. Franel, Question n o 170 (J. Franel), L'Intermédiaire des Mathématiciens 2 (1895), 33--35.
  10. R. J. McIntosh, Asymptotic and Arithmetic Properties of Recurrent Sequences , Ph.D. thesis, University of California, Los Angeles, 1989.
Show all 22 referencesShow fewer references
  1. R. J. McIntosh, Recurrences for alternating sums of powers of binomial coefficients, Journal of Combinatorial Theory, Series A 63 (1993), no. 2, 223--233. doi:10.1016/0097-3165(93)90058-G (https://doi.org/10.1016/0097-3165(93)90058-G).DOI
  2. O. Ore, Theory of non-commutative polynomials, Annals of Mathematics , Second Series, 34 (1933), no. 3, 480--508. doi:10.2307/1968173 (https://doi.org/10.2307/1968173).DOI
  3. M. A. Perlstadt, Some recurrences for sums of powers of binomial coefficients, Journal of Number Theory 27 (1987), no. 3, 304--309. doi:10.1016/0022-314X(87)90069-2 (https://doi.org/10.1016/0022-314X(87)90069-2).DOI
  4. O. Perron, Über einen Satz des Herrn Poincaré, Journal für die reine und angewandte Mathematik 136 (1909), 17--37. doi:10.1515/crll.1909.136.17 (https://doi.org/10.1515/crll.1909.136.17).DOI
  5. A. Schulte, S. VanSchalkwyk and A. Yang, On the divisibility and valuations of the Franel numbers, in 2014 MSRI-UP Research Reports , pp. 127--162.
  6. M. Stoll, Bounds for the length of recurrence relations for convolutions of P-recursive sequences, European Journal of Combinatorics 18 (1997), no. 6, 707--712. doi:10.1006/eujc.1996.0123 (https://doi.org/10.1006/eujc.1996.0123).DOI
  7. A. Straub and W. Zudilin, Sums of powers of binomials, their Apéry limits, and Franel's suspicions, International Mathematics Research Notices 2023 (2023), no. 11, 9861--9879. doi:10.1093/imrn/rnac125 (https://doi.org/10.1093/imrn/rnac125).DOI
  8. J. Tonien, Franel numbers and a continued fraction conjecture discovered by the Ramanujan Machine, The Mathematical Intelligencer 48 (2026), no. 3, 222--227; published online 24 February 2026. doi:10.1007/s00283-025-10497-9 (https://doi.org/10.1007/s00283-025-10497-9).DOI
  9. M. van Hoeij, Submodule approach to creative telescoping, Journal of Symbolic Computation 126 (2025), 102342. doi:10.1016/j.jsc.2024.102342 (https://doi.org/10.1016/j.jsc.2024.102342).DOI
  10. L. van Hove, The occurrence of singularities in the elastic frequency distribution of a crystal, Physical Review 89 (1953), no. 6, 1189--1193. doi:10.1103/PhysRev.89.1189 (https://doi.org/10.1103/PhysRev.89.1189).DOI
  11. Yuan Jin and H. Dickinson, Apéry sequences and Legendre transforms, Journal of the Australian Mathematical Society, Series A 68 (2000), no. 3, 349--356. doi:10.1017/S1446788700001440 (https://doi.org/10.1017/S1446788700001440).DOI
  12. J. Yuan, Z.-J. Lu and A. L. Schmidt, On recurrences for sums of powers of binomial coefficients, Journal of Number Theory 128 (2008), no. 10, 2784--2794. doi:10.1016/j.jnt.2008.03.011 (https://doi.org/10.1016/j.jnt.2008.03.011).DOI

Version history

  1. v1Submitted by Khai-Hoan Nguyen-DangInitial depositCurrentNov 01, 2026