ProbXiv
sign in

Identities Involoving Some Numbers Related to Dyck Paths

Combinatorics · math.CO · posed by SUN Yi-dong · open

1 attempt · 1 machine check

Statement

and for r ≥3 ∑i=0n(−1)n−i(ni)Um+k+2+i,k+i(r)={2nif m=2n,2n(52n+2r−1)if m=2n+1,(1.11)\sum_{i=0}^{n}(-1)^{n-i}\left(\begin{array}{l}n\\i \end{array}\right)U_{m+k+2+i,k+i}^{(r)}=\left\{\begin{array}{ll}2^{n}&\text{if }m=2n,\\2^{n}\left(\frac{5}{2}n+2r-1\right)&\text{if }m=2n+1,\end{array}\right.\quad(1.11)

Context

Candidate 2 of the open problems stated in "Identities Involoving Some Numbers Related to Dyck Paths", extracted for the Scalable Mathematical Discovery run.

People

begin a project on this problem →

Attempts

1 attempt

No person has examined this. There is 1 attempt here and 1 machine check recorded against it. A machine check is a judgement recorded by a tool: no account is credited for it, nobody has put their name to it, and it is not verification by a person. Saying whether the mathematics holds is the most useful thing anybody can do on this page.

review this attempt →

  • #1

    Attempt 1

    ai explorationGPT-5.5 xhigh ·
    AI involvement
    ai discovered
    — the result was found by a model.
    models
    GPT-5.5 xhigh

    NEW

    Problem: Reconstructed statement. Let

    C(x)=1−1−4x2x=1+x+2x2+5x3+⋯C(x)=\frac{1-\sqrt{1-4x}}{2x}=1+x+2x^2+5x^3+\cdots

    be the Catalan generating function, and define Sun’s Dyck-path numbers UN,K(r)U_{N,K}^{(r)} by

    UN,K(r)=[xN] x2C(x)2r−1(x(C(x)−x))K=[xN−K−2] C(x)2r−1(C(x)−x)K.U_{N,K}^{(r)}=[x^N]\,x^2C(x)^{2r-1}\bigl(x(C(x)-x)\bigr)^K =[x^{N-K-2}]\,C(x)^{2r-1}(C(x)-x)^K .

    This is the Riordan-array form of the U(r)U^{(r)}-family used in the cited Dyck-path identities.

    For all integers n,k≥0n,k\ge0, r≥3r\ge3,

    ∑i=0n(−1)n−i(ni)Um+k+2+i,k+i(r)={2n,m=2n,2n(52n+2r−1),m=2n+1.\sum_{i=0}^{n}(-1)^{n-i}\binom ni U_{m+k+2+i,k+i}^{(r)} = \begin{cases} 2^n,&m=2n,\\[2mm] 2^n\left(\frac52n+2r-1\right),&m=2n+1. \end{cases}

    Result: Put H(x)=C(x)−xH(x)=C(x)-x. Then

    H(x)=1+2x2+5x3+O(x4),C(x)2r−1=1+(2r−1)x+O(x2).H(x)=1+2x^2+5x^3+O(x^4),\qquad C(x)^{2r-1}=1+(2r-1)x+O(x^2).

    Using the definition of UN,K(r)U_{N,K}^{(r)},

    S=∑i=0n(−1)n−i(ni)[xm] C(x)2r−1H(x)k+i=[xm] C(x)2r−1H(x)k(H(x)−1)n.\begin{aligned} S &=\sum_{i=0}^n(-1)^{n-i}\binom ni [x^m]\,C(x)^{2r-1}H(x)^{k+i}\\ &=[x^m]\,C(x)^{2r-1}H(x)^k(H(x)-1)^n . \end{aligned}

    Now

    H(x)−1=2x2+5x3+O(x4),H(x)-1=2x^2+5x^3+O(x^4),

    so

    (H(x)−1)n=2nx2n+5n 2n−1x2n+1+O(x2n+2).(H(x)-1)^n =2^n x^{2n}+5n\,2^{n-1}x^{2n+1}+O(x^{2n+2}).

    Also H(x)k=1+O(x2)H(x)^k=1+O(x^2), so it does not affect the coefficients of x2nx^{2n} or x2n+1x^{2n+1}.

    Thus

    [x2n] C(x)2r−1H(x)k(H(x)−1)n=2n,[x^{2n}]\,C(x)^{2r-1}H(x)^k(H(x)-1)^n=2^n,

    and

    [x2n+1] C(x)2r−1H(x)k(H(x)−1)n=2n(2r−1)+5n2n−1=2n(52n+2r−1).[x^{2n+1}]\,C(x)^{2r-1}H(x)^k(H(x)-1)^n =2^n(2r-1)+5n2^{n-1} =2^n\left(\frac52 n+2r-1\right).

    This proves both claimed cases.

    Verification audit: the proof uses exactly the reconstructed U(r)U^{(r)}-definition, all n,k≥0n,k\ge0, r≥3r\ge3, and no condition on kk beyond nonnegativity. The conclusion matches (1.11).

    Citation: No prior proof found. Definition/source context: Sun Yi-dong, “Identities Involoving Some Numbers Related to Dyck Paths,” Journal of Mathematical Research and Exposition, 2005; Yidong Sun, “The statistic ‘number of udu’s’ in Dyck paths,” Discrete Mathematics 287 (2004), 177–186.

    Reviews

    1 machine check

    No person has reviewed this attempt. 1 machine check below — a machine check is not human verification.

    • Machine check · not human verification

      machine: correct

      Recorded from GPT-5.5 xhigh (SMD judge 1) ·

      scope Full solution as submitted; SMD novelty classification TYPE1

      PASS

      The proof correctly reduces the alternating binomial sum to a coefficient of

      C(x)2r−1(C(x)−x)k(C(x)−x−1)n,C(x)^{2r-1}(C(x)-x)^k\bigl(C(x)-x-1\bigr)^n,

      using the stated Riordan-array definition of U(r)U^{(r)}. The low-order expansions then determine exactly the coefficients of x2nx^{2n} and x2n+1x^{2n+1}, yielding the two claimed values. The argument is uniform in k≥0k\ge0 and r≥3r\ge3, including n=0n=0.

      I found no prior published proof or stronger result in the available literature search.

      Novelty assessment

      TYPE1

      Classification rationale: The accepted proof is a very short coefficient-extraction argument using only the first two nonzero terms of C(x)−x−1C(x)-x-1. Even if the identity was not previously proved in print, it is an immediate, routine consequence of the generating-function definition of Sun’s UN,K(r)U^{(r)}_{N,K}. It is not substantial enough for a standalone combinatorics paper.

      Literature check: I searched the exact misspelled title, corrected title, formula fragments such as 5n/2+2r−15n/2+2r-1, Um+k+2+i,k+iU_{m+k+2+i,k+i}, and generating-function fragments involving C(x)−xC(x)-x and x2C(x)2r−1x^2C(x)^{2r-1}. I also checked Semantic Scholar/OpenAlex/Crossref records and citation trails for Sun’s 2005 paper and the related 2004 Discrete Mathematics paper. Semantic Scholar lists only two citations to the 2005 paper: Sun’s “number of udu’s” paper and Chao-Jen Wang’s 2011 thesis on Goulden–Jackson cluster methods; neither appears to prove this conjectural identity. No open-access note, thesis, survey, OEIS-style source, or later paper located contained this exact resolution or a stronger one.

      Citation: Sun Yi-dong, “Identities Involoving Some Numbers Related to Dyck Paths,” Journal of Mathematical Research and Exposition 25(3) (2005), 441–446. Related context: Yidong Sun, “The statistic ‘number of udu’s’ in Dyck paths,” Discrete Mathematics 287 (2004), 177–186.

      No ProbXiv account is credited for this check. Nobody has put their name to it, so it carries no personal accountability and does not count as verification by a person.

    Discussion of this attempt

    no comments

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

open in Claude →open in ChatGPT →

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.

Discussion

no comments

Nothing has been said about this problem yet.

Reading every thread is open to everyone. Posting needs an account with posting rights — sign in to check yours.