arxiv: 2605.04369 · v1 · submitted 2026-05-06 · 🧮 math.CO

Recognition: unknown

A short proof of Mathar's 2016 recurrence conjecture for OEIS A176677

Authors on Pith no claims yet

Pith reviewed 2026-05-08 16:15 UTC · model grok-4.3

classification 🧮 math.CO

keywords A176677ordinary generating functionalgebraic equationP-recursive recurrencepolynomial divisionMotzkin pathsquadratic convolutionlinear ODE

0 comments

The pith

The algebraic equation for the generating function of A176677 directly implies Mathar's order-4 recurrence through a linear ODE.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves Mathar's 2016 conjecture that the OEIS sequence A176677 obeys a specific order-4 P-recursive relation. The sequence begins with a(0) = a(1) = 1 and satisfies the quadratic convolution a(n+1) = sum a(p)a(n-p) - 1, which translates into the algebraic equation z(1-z)G(z)^2 - (1-z)G(z) + (1 - z - z^2) = 0 for its ordinary generating function. Differentiating or rearranging this relation and clearing denominators produces a candidate first-order linear ODE; the paper verifies that this ODE holds exactly by polynomial division modulo the algebraic equation, and the coefficients of the resulting ODE expand directly into Mathar's recurrence. The leading coefficient of the ODE factors to reveal the singularities of G, which coincide with those expected from the combinatorial model of two-coloured Motzkin paths.

Core claim

Mathar's recurrence drops out as the coefficient form of the first-order linear inhomogeneous ODE q0(z) G(z) + q1(z) G'(z) = R(z), verified by polynomial division modulo the algebraic equation z(1-z)G(z)^2 - (1-z)G(z) + (1 - z - z^2) = 0 that the convolution recurrence imposes on the ordinary generating function G(z).

What carries the argument

the algebraic equation for G(z) together with polynomial division modulo that equation to obtain the linear ODE

If this is right

The recurrence holds for every n greater than or equal to 4.
The singularities of G lie exactly at the roots of the factored polynomial q1(z) = -z(z-1)(2z-1)(2z^2 + 3z - 1).
Deutsch's combinatorial model of Motzkin paths of length n-1 with two-coloured level-zero steps remains compatible with the generating function.
The same division technique yields the inhomogeneous right-hand side R(z) whose series expansion encodes initial conditions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The explicit factorization of q1 supplies the radius of convergence and therefore the exponential growth rate of a(n) without separate asymptotic analysis.
The method of deriving minimal recurrences by division modulo an algebraic equation may extend routinely to other quadratic or algebraic generating functions that arise from convolutions.
Because the ODE is first-order, the sequence satisfies no lower-order linear recurrence with polynomial coefficients.

Load-bearing premise

The algebraic equation holds exactly for the generating function and the polynomial division produces an identity with no remainder terms that would alter the recurrence.

What would settle it

Execute the explicit polynomial division of the candidate ODE expression by the quadratic algebraic polynomial and inspect the remainder; a nonzero remainder would falsify the claimed identity.

read the original abstract

For the OEIS sequence A176677, defined by the quadratic convolution recurrence $a(0) = a(1) = 1$ and $a(n+1) = \sum_{p=0}^n a(p) a(n-p) - 1$ for $n \ge 1$, R.~J.~Mathar contributed in March 2016 the conjectured order-4 P-recursive recurrence \[ (n+1)\,a(n) + 2(-3n+1)\,a(n-1) + (9n-13)\,a(n-2) - 4\,a(n-3) + 4(-n+4)\,a(n-4) = 0. \] We give a short proof. The convolution recurrence translates directly into the algebraic equation $z(1-z) G(z)^2 - (1-z) G(z) + (1 - z - z^2) = 0$ for the ordinary generating function $G(z)$, and Mathar's recurrence then drops out as the coefficient form of a 1st-order linear inhomogeneous ODE $q_0(z) G(z) + q_1(z) G'(z) = R(z)$ that we verify by polynomial division modulo the algebraic equation. The polynomial $q_1(z)$ admits the factorization $q_1(z) = -z(z-1)(2z-1)(2z^2 + 3z - 1)$, whose roots are exactly the singularities of $G$. Deutsch's combinatorial interpretation (Motzkin paths of length $n-1$ with two-coloured level-zero horizontal steps) is preserved.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This note gives a short, direct generating-function proof that Mathar's recurrence follows from the quadratic equation for A176677 by verifying an auxiliary linear ODE.

read the letter

The main takeaway is that the paper converts the convolution definition of A176677 into its algebraic generating-function equation, differentiates to express G', and then confirms a first-order linear ODE whose coefficients produce the conjectured order-4 recurrence. The verification uses polynomial division in the quotient ring modulo the quadratic relation, and the leading coefficient factors into terms matching the singularities of G. The combinatorial Motzkin-path reading is noted but not central to the argument. This is a clean, self-contained derivation that avoids heavy machinery and stays within standard generating-function techniques. It is new in the sense that the explicit ODE route was not in the original conjecture or OEIS entry. The algebra is plausible and the steps are logically independent of any fitted parameters. The soft spot is the division step itself. The abstract states that q0 G + q1 G' - R reduces to zero after the division and substitution, but does not display the explicit polynomials q0 and R or the reduction work. If a nonzero remainder survives the algebraic reduction, the recurrence would not hold for all large n. In a short note the calculation may be routine, yet a reader still needs to see it or redo it to be confident. The paper is aimed at people who follow explicit recurrences for individual OEIS sequences or who apply generating functions to extract P-recursions from algebraic equations. It will not reorganize broader theory, but it resolves a concrete conjecture with transparent steps. The thinking is clear and the method engages the literature honestly, so the work deserves a serious referee who can verify the division in detail. I would recommend sending it to peer review; the claim is narrow but checkable and the presentation is direct.

Referee Report

2 major / 1 minor

Summary. The paper claims to give a short proof of Mathar's 2016 conjectured order-4 P-recursive recurrence for OEIS A176677. Starting from the quadratic convolution recurrence a(0)=a(1)=1 and a(n+1)=sum_{p=0}^n a(p)a(n-p)-1, it derives the algebraic equation z(1-z)G(z)^2 - (1-z)G(z) + (1-z-z^2)=0 for the OGF G(z). It then obtains Mathar's recurrence as the coefficient form of a first-order linear inhomogeneous ODE q0(z)G(z) + q1(z)G'(z)=R(z), verified by polynomial division modulo the algebraic equation. The factorization q1(z)=-z(z-1)(2z-1)(2z^2+3z-1) is given, whose roots match the singularities of G, and Deutsch's Motzkin-path interpretation is preserved.

Significance. If the ODE verification holds, the manuscript supplies a direct, non-computational proof of the recurrence conjecture via algebraic and differential relations on the generating function. This is significant for confirming the conjecture rigorously and for illustrating a general technique of extracting linear recurrences from algebraic generating functions by reducing a differentiated relation modulo the minimal polynomial. The explicit factorization of q1 and the preservation of the combinatorial model are additional strengths.

major comments (2)

[Abstract / ODE verification] Abstract and ODE verification section: the central claim is that q0(z)G(z) + q1(z)G'(z) - R(z) reduces to zero in the differential extension of Q(z)[G] modulo the quadratic algebraic equation after substituting the differentiated relation for G'. The manuscript states this is verified by polynomial division and gives the factorization of q1, but does not exhibit the explicit polynomials q0(z) and R(z) nor the division steps or remainder. This is load-bearing for the recurrence extraction, as any surviving non-zero remainder (from G-power reduction or the differentiated algebraic relation) would prevent the coefficient identity from holding for all sufficiently large n.
[Algebraic equation] Algebraic equation derivation: the translation from the convolution recurrence to z(1-z)G(z)^2 - (1-z)G(z) + (1-z-z^2)=0 is described as direct, but the manuscript should include the explicit generating-function manipulation (including handling of the -1 term and initial conditions) to allow independent verification that the equation holds exactly with no extra constant or lower-order terms.

minor comments (1)

The abstract is concise and well-structured, but the full manuscript should add a brief sentence specifying the range of n for which the extracted recurrence is guaranteed to hold (typically n larger than the degree of the denominator polynomials).

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation of the paper's significance and for the constructive major comments. We agree that both points identify areas where additional explicit details will make the proof more self-contained and easier to verify independently. We will revise the manuscript to address them fully.

read point-by-point responses

Referee: [Abstract / ODE verification] Abstract and ODE verification section: the central claim is that q0(z)G(z) + q1(z)G'(z) - R(z) reduces to zero in the differential extension of Q(z)[G] modulo the quadratic algebraic equation after substituting the differentiated relation for G'. The manuscript states this is verified by polynomial division and gives the factorization of q1, but does not exhibit the explicit polynomials q0(z) and R(z) nor the division steps or remainder.

Authors: We agree that the verification of the ODE is load-bearing and that exhibiting q0(z), R(z), and the division steps strengthens the argument. In the revised manuscript we will state the explicit polynomials q0(z) and R(z), describe the substitution of the differentiated algebraic relation, and carry out the polynomial division in Q(z)[G] to confirm that the remainder is identically zero. This will directly yield the coefficient identity for all sufficiently large n. revision: yes
Referee: [Algebraic equation] Algebraic equation derivation: the translation from the convolution recurrence to z(1-z)G(z)^2 - (1-z)G(z) + (1-z-z^2)=0 is described as direct, but the manuscript should include the explicit generating-function manipulation (including handling of the -1 term and initial conditions) to allow independent verification that the equation holds exactly with no extra constant or lower-order terms.

Authors: We concur that an expanded derivation will permit independent checking. The revised text will include the full ordinary generating-function translation of the recurrence a(n+1) = sum a(p)a(n-p) - 1, showing term-by-term how the -1 contributes to the constant term and how the initial conditions a(0)=a(1)=1 are incorporated so that the algebraic equation holds with no residual lower-order terms. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation is self-contained from the defining recurrence.

full rationale

The paper starts from the explicit convolution definition a(0)=a(1)=1 and a(n+1)=sum a(p)a(n-p)-1, translates it directly into the quadratic algebraic equation for G(z), constructs an auxiliary first-order ODE whose coefficients are chosen so that the identity holds in the differential extension modulo the algebraic relation (verified by explicit polynomial division), and extracts the target recurrence as the coefficient form of that verified ODE. No step presupposes the recurrence, fits parameters to data, renames a known result, or relies on load-bearing self-citations; the algebraic verification is independent of the final recurrence coefficients.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the algebraic equation being the exact translation of the quadratic convolution recurrence; no free parameters are introduced and no new entities are postulated.

axioms (1)

domain assumption The ordinary generating function G(z) satisfies the quadratic equation z(1-z)G(z)^2 - (1-z)G(z) + (1 - z - z^2) = 0 exactly.
This equation is obtained directly by translating the given convolution recurrence a(n+1) = sum a(p)a(n-p) - 1 into generating-function form.

pith-pipeline@v0.9.0 · 5603 in / 1294 out tokens · 34641 ms · 2026-05-08T16:15:58.255356+00:00 · methodology

discussion (0)

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

A short proof of Mathar's 2013 recurrence conjecture for the reversible-binary-string sequence A032123
math.CO 2026-05 accept novelty 6.0

The conjectured recurrence for a(n) holds because the order-5 operator annihilates both the central binomial coefficient and the even-n middle binomial term in the closed form derived from Burnside's lemma.
A short proof of Mathar's 2020 recurrence conjecture for the generalized-Stirling sequence A001711
math.CO 2026-05 accept novelty 5.0

The sequence A001711 satisfies a(n) - (2n+5)a(n-1) + (n+2)^2 a(n-2) = 0 for n >= 2, shown by substituting the closed form (1/4)(n+3)! (2 H_{n+3} - 3) and verifying that harmonic coefficients and constant terms both ca...
Motzkin paths with two variants of level steps on odd levels -- a kernel method approach
math.CO 2026-05 unverdicted novelty 5.0

Motzkin paths with two level-step variants restricted to odd levels are counted via kernel method, producing a holonomic recursion for A176677.

Reference graph

Works this paper leans on

9 extracted references · 1 canonical work pages · cited by 3 Pith papers

[1]

Choulet, OEIS sequences A176604–A177111 (Choulet quadratic convolution family), contributed April– May 2010.https://oeis.org/A176677

R. Choulet, OEIS sequences A176604–A177111 (Choulet quadratic convolution family), contributed April– May 2010.https://oeis.org/A176677

2010
[2]

Combinatorial interpretation of A176677 as2-coloured Motzkin paths,

E. Deutsch, “Combinatorial interpretation of A176677 as2-coloured Motzkin paths,” OEIS comment on A176677, contributed May 2, 2011.https://oeis.org/A176677

2011
[3]

Kauers and C

M. Kauers and C. Koutschan,Some D-Finite and Some Possibly D-Finite Sequences in the OEIS, arXiv:2303.02793, 2023

work page arXiv 2023
[4]

Kauers and P

M. Kauers and P. Paule,The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates, Springer Texts and Monographs in Symbolic Computation, 2011

2011
[5]

R. J. Mathar, conjectured order-4 P-recursive recurrence in OEIS sequence A176677, contributed March 1, 2016.https://oeis.org/A176677

2016
[6]

[anonymous],Three short proofs of Mathar’s 2014 conjecture for OEIS A002627, manuscript, 2026

2014
[7]

Salvy and P

B. Salvy and P. Zimmermann,gfun: a Maple package for the manipulation of generating and holonomic functions in one variable, ACM Trans. Math. Software20(1994), 163–177

1994
[8]

N. J. A. Sloane (founder),The On-Line Encyclopedia of Integer Sequences, sequence A176677, https: //oeis.org/A176677
[9]

"" 26 27from __future__ import annotations 28 29from fractions import Fraction 30 31 32def compute_a_via_convolution(n_max: int) -> list[int]: 33

R. P. Stanley,Enumerative Combinatorics, Volume 2, Cambridge University Press, 1999, Chapter 6. AppendixA.Verification script:verify_a176677.py The script computes a(0), . . . , a(250)both from (1) and from (2), cross-checks the first 28 against the OEIS data, and then verifies (R) for everyn∈ {4, . . . ,250}. Listing 1.verify_a176677.py: 250-term verific...

1999