Two recurrence proofs: a matrix inverse and a binomial transform

The parity recurrence

Define T(n, 0) = 1, set T(n, k) = 0 for k > n, and for 1 ≤ k ≤ n use $$T\left(n,k\right)=\sum _{i=0}^{n-1}T\left(n-1,i\right)T\left(i,k-1\right)\text{.}$$Scroll formula → The diagonal entries are one. The first five rows are 1; 1, 1; 1, 2, 1; 1, 4, 4, 1; and 1, 10, 16, 8, 1. The sequence.

Theorem. For 0 < k < n, $$T\left(n,k\right)=\sum _{i=0}^{n-k-1}T\left(n-k,i\right)T\left(k+i,k-1\right)\left(1+{\left(-1\right)}^{n+k+i+1}\right)\text{.}$$Scroll formula →

The factor in parentheses is either zero or two, so only one parity of indices can contribute. The boundary columns k = 0 and k = n retain their value one; they are not covered by this interior formula. For example, T(4, 2) = 2 T(2, 1) T(3, 1) = 16. The recurrence was conjectured in the original question and appears in OEIS with credit to Mikhail Kurkov.

Why the inverse alternates

The matrix and its inverse expose the cancellation together: once their alternating signs are known, subtracting the inverse from the matrix filters the unwanted parity, and a finite telescoping sum turns that filter into the interior-entry recurrence requested in the original question.

Let M be the lower triangular matrix with entries T(n, k), indexed from zero. If S deletes its first row and column, the defining recurrence says S(M) = $M^2$. Lower triangularity makes S multiplicative: each product entry is a finite sum and the omitted intermediate index contributes zero. The first column and this relation uniquely determine every row, a fact that will identify the inverse below. The iterated identity $S^a$(M) = $M^{2^a}$ is known background recorded with the sequence. Prior context.

Write $P_n$(z) = $\sum _j$ T(n, j)$z^j$. The recurrence becomes $$P_n\left(z\right)=1+z\sum _{i=0}^{n-1}T\left(n-1,i\right)P_i\left(z\right)\text{,}$$Scroll formula → with $P_0$(z) = 1. Induction gives $P_n$(−1) = 0 for n > 0, because only the i = 0 summand survives. Thus multiplying M by the column (1,−1, 1,−1,…) gives the first coordinate vector $e_0$. That alternating column is the first column of $M^{-1}$.

Put D = diag(1,−1, 1,−1,…) and Q = D$M^{-1}$D. The first column of Q is all ones. Since S(D) = −D, we also have S(Q) = D$M^{-2}$D = $Q^2$. Uniqueness forces Q = M. Consequently $M^{-1}$ = DMD. No convergence is involved: every entry of an inverse or product depends on finitely many entries.

A finite telescoping argument

Fix k ≥ 1 and put r = $2^{k-1}$. The block decomposition of M is $M=\left[\left[1,0\right],\left[𝟙,M^2\right]\right]$, where 𝟙 is the column of ones. The first column of $M^r$ below its initial entry is therefore $$\begin{array}{l}v=\left(I+M^2+\cdots +M^{2r-2}\right)𝟙\\ =\left(M+M^3+\cdots +M^{2r-1}\right)e_0\text{.}\end{array}$$Scroll formula →

The shifted-power identity identifies $v_i$ = T(k+i, k−1). Multiplication by M−$M^{-1}$ telescopes exactly: $\left(M-M^{-1}\right)v=\left(M^{2r}-I\right)e_0$. Take coordinate d = n−k > 0. The right side is T(n, k). On the left, the alternating inverse gives $$\sum _{i=0}^{d}T\left(d,i\right)T\left(k+i,k-1\right)\left(1-{\left(-1\right)}^{d+i}\right)\text{.}$$Scroll formula →

The i = d term vanishes. Replacing d by n−k gives the stated parity recurrence. This proves the identity for every interior entry, independently of the numerical tests.

Andrew R. Epstein’s August 2026 document develops binary-partition and diagonal results for this matrix family while leaving the June 2025 entry recurrence open. Those results and the matrix-power relation are prior work. The document comparison leaves worldwide priority unconfirmed.

The composition recurrence

For A382991, let a(n) be the coefficient of $x^n$ in $$A\left(x\right)=1+\sum _{m\ge 1}\prod _{j=1}^m\left(jx+x^2/\left(1-x\right)\right)\text{.}$$Scroll formula → This product counts compositions in which a singleton in position j has j colors and a longer part has one color. The sequence and product generating function predate this note. The sequence.

Define R(0, k) = 1 and, for n ≥ 1, $$R\left(n,k\right)=\left(\genfrac{}{}{0ex}{}{n+k}{k}\right)+\sum _{j=0}^{k+1}\left(\genfrac{}{}{0ex}{}{k+1}{j}\right)R\left(n-1,j\right)\text{.}$$Scroll formula → The second requested statement is a(n) = R(n−1, 0) for every n ≥ 1.

Here all generating series are formal. Their coefficients grow factorially; analytic convergence is neither assumed nor needed.

The binomial transform solves all columns at once

The desired column depends on the other columns. Solving their generating series together keeps the auxiliary index available until the binomial theorem closes the calculation.

The general identity works over any commutative ring with identity. Choose h ∈ 1+xK[[x]], put B(n, k) = [$x^n$]$h^{k+1}$, and define S(0, k) = 1 and $$S\left(n,k\right)=B\left(n,k\right)+\sum _{j=0}^{k+1}\left(\genfrac{}{}{0ex}{}{k+1}{j}\right)S\left(n-1,j\right)\text{.}$$Scroll formula →

If z raised to an overlined i denotes the rising product z(z+1)⋯(z+i−1), with empty product one, then $$\begin{array}{l}{C}_k\left(x\right):=\sum _{n\ge 0}S\left(n,k\right)x^n\\ =h\sum _{i\ge 0}{x}^i{\left(h+1\right)}^{\overline{i}}{\left(h+i\right)}^k\text{.}\end{array}$$Scroll formula →

The infinite expression defines a formal series because only finitely many i contribute to each coefficient. Applying the binomial theorem gives $$\begin{array}{l}x\sum _{j=0}^{k+1}\left(\genfrac{}{}{0ex}{}{k+1}{j}\right)C_j=h\sum _{i\ge 0}{x}^{i+1}{\left(h+1\right)}^{\overline{i}}{\left(h+i+1\right)}^{k+1}\\ =C_k-h^{k+1}\text{.}\end{array}$$Scroll formula → The extra factor h+i+1 extends the rising product by one term. Coefficient comparison proves the recurrence and initial row, hence the identity.

Now set h = u = 1/(1−x). Then B(n, k) = $\left(\genfrac{}{}{0ex}{}{n+k}{k}\right)$, so $C_k$ generates the kth R column. At k = 0, $1+x{C}_0=1+\sum _{m\ge 1}{x}^m{u}^{\overline{m}}$. Since $x\left(u+j-1\right)=jx+x^2/\left(1-x\right)$, this is exactly A(x). Comparing coefficients proves the requested equality.

A weighted extension and its size

Give every part of size at least two β colors, while keeping j colors for a singleton in position j. The product becomes $$A\beta \left(x\right)=1+\sum _{m\ge 1}\prod _{j=1}^m\left(jx+\beta x^2/\left(1-x\right)\right)\text{.}$$Scroll formula → The same formal identity applies with h = 1+βx/(1−x), giving a recurrence for every weighted column.

For fixed real β ≥ 0, the paper also proves $$a\beta \left(n\right)/n!=1+\beta H_{n-1}/n+O\beta \left({\left(\log n\right)}^2/n^2\right)\text{,}$$Scroll formula → where $H_{n-1}$ = 1 + 1/2 + ⋯ + 1/(n−1). In particular, the original sequence satisfies a(n) ∼ n!.

The proof sorts compositions by the deficit r = n minus their number of parts. The all-singleton composition contributes n!. Deficit one contributes β(n−1)!$H_{n-1}$. Elementary symmetric sums bound deficits 2 through n/2 by the stated error; a factorial ratio makes the remaining tail smaller than any fixed inverse power. The paper proves this analytic estimate using the deficit bounds above, rather than extrapolating from computed terms.

The formal identity also accepts signed weights, which can check the algebra without treating a negative weight as a number of colors. A direct combinatorial proof remains a question: which decomposition of a colored composition yields the binomial recurrence? The operator identity proves equality before supplying that interpretation.

Checks and attribution

The primary A078121 program checked 4,950 interior identities through n = 100 and reconstructed 5,151 entries using the parity formula. A separately written exact program checked 7,140 identities through n = 120, a 31-by-31 inverse in both orders, 5,872 shifted-power entries and 212 telescoping entries.

For A382991, exact programs compare the recurrence, product generating function, independent composition counts, closed-column formula and deficit decomposition. The independent audit checked 17,947 array/operator pairs across its parameter ranges and 2,256 closed-column coefficients. Negative weights test the formal algebra only. The original parameter case includes n+k ≤ 120.

The downloadable files preserve the note as written before external publication, including its statement that no answer had yet been posted. This page publishes that note as author-hosted work; it does not represent journal acceptance.

The A078121 proof has also been submitted to the related proof repository for maintainer review. The issue is open; this records a review submission, not acceptance or Lean formalization. Review submission.

The two arguments make an apparently local recurrence easier by retaining more of its structure. The matrix reveals a sign symmetry that individual entries conceal; the full auxiliary array reveals a transformation that the desired column alone conceals. That is the useful lesson of the proofs: extra structure can simplify the question before any terms are discarded.