A double-binomial recurrence and its continued fraction

The recurrence behind A302285

On April 10, 2025, MathOverflow user231922 asked for a proof connecting a double-binomial recurrence with OEIS A302285. The continued fraction and its combinatorial context predate the request. The claim here concerns the displayed recurrence. The request, the sequence.

For integers n, k ≥ 0, set $R\left(0,k\right)=1$. For n ≥ 1, define $$R\left(n,k\right)=R\left(n-1,k+1\right)+\sum _{i=0}^{n-1}\sum _{j=0}^k\left(\genfrac{}{}{0ex}{}{k}{j}\right)R\left(n-i-1,j\right)R\left(i,k-j\right)\text{.}$$Scroll formula →

The claim is $R\left(n,0\right)=a\left(n\right)$, where $$\sum _{n\ge 0}a\left(n\right)x^n=1/\left(1-x-x/\left(1-2x-x/\left(1-3x-\dots \right)\right)\right)\text{.}$$Scroll formula → The proof below follows the complete argument in the complete paper.

The formal tails determine every coefficient

Proof. Introduce a second variable t. For h ≥ 0, define $F_h=t/\left(1-\left(h+1\right)x-x{F}_{h+1}\right)$, with $F_h=t+O\left(x\right)$. These are formal power series in x whose coefficients are polynomials in t, each divisible by t.

Only finitely many further tails are needed to determine a coefficient of $x^n$. Changing a tail introduces another factor of x at each preceding level. This makes the infinite continued fraction well defined coefficient by coefficient.

Set $$E_h=xt\text{∂}{F}_h/\text{∂}t-\left(1-hx\right)F_h+t+x{F}_h^2\text{.}$$Scroll formula → Differentiating the tail equation and substituting it again gives $$\begin{array}{l}{E}_h=x{F}_h\left(F_h-F_{h+1}\right)+x^2{F}_h^2\text{∂}{F}_{h+1}/\text{∂}t\\ =\left(x{F}_h^2/t\right)E_{h+1}\text{.}\end{array}$$Scroll formula →

Because every $F_h$ is divisible by t, the quotient $F_h^2$/t still has polynomial coefficients. The calculation stays in that ring. Each application of the identity adds a factor of x. Iterating shows that $E_h$ is divisible by every power of x, so $E_h$ = 0.

The derivation produces the binomial rule

Write $F_0=\sum _{n\ge 0}{P}_n\left(t\right)x^n$. Taking coefficients in $E_0$ = 0 gives $P_0=t$ and $P_n=t{\mathrm{P\prime }}_{n-1}+\sum _{i=0}^{n-1}{P}_{n-i-1}{P}_i$ for n ≥ 1.

Let D be the derivation t d/dt and put $S\left(n,k\right)=\left(D^k{P}_n\right)\left(1\right)$. Applying $D^k$ to the coefficient identity uses the binomial Leibniz rule: $$D^k\left(fg\right)=\sum _{j=0}^k\left(\genfrac{}{}{0ex}{}{k}{j}\right)\left(D^{j}f\right)\left(D^{k-j}g\right)\text{.}$$Scroll formula → It yields exactly the displayed recurrence for S.

Also S(0, k) = 1, since $P_0$ = t. Induction on n now gives S(n, k) = R(n, k). Finally $F_0$(x, 1) is the required continued fraction, so $R\left(n,0\right)=P_n\left(1\right)=a\left(n\right)$ for every n ≥ 0.

The exact checks and prior work

Independent exact checks agreed on 2,556 recurrence pairs with n + k ≤ 70. The full formal-series argument and executable checks are in the downloads. Alexander Burstein’s comment on the question provides the colored Schröder-path interpretation; the surrounding T-fraction theory is prior work of Bitonti, Deb and Sokal, whose Table 1 includes A302285. No new general theory of continued fractions is claimed. Prior research.

Why this representation helps

The ordering proof uses powers to encode signed coefficients; this one keeps formal tails until differentiation exposes the binomial rule, a choice of representation that turns the requested identity into a coefficient calculation. The wider T-fraction family and colored-path interpretation are prior work. The recurrence is the payoff for keeping that structure in view.