Two requested recurrence proofs

The parity recurrence

Define T(n,0) = 1, set T(n,k) = 0 for k > n, and for 1 ≤ k ≤ n use T(n,k) = Σᵢ₌₀ⁿ⁻¹ T(n−1,i) T(i,k−1). 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(n,k) = Σᵢ₌₀ⁿ⁻ᵏ⁻¹ T(n−k,i) T(k+i,k−1) (1 + (−1)^(n+k+i+1)).

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

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². 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. The iterated identity Sᵃ(M) = M^(2ᵃ) is known background recorded with the sequence. Prior context.

Write Pₙ(z) = Σⱼ T(n,j)zʲ. The recurrence becomes Pₙ(z) = 1 + z Σᵢ₌₀ⁿ⁻¹ T(n−1,i)Pᵢ(z), with P₀(z) = 1. Induction gives Pₙ(−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₀. That alternating column is the first column of M⁻¹.

Put D = diag(1,−1,1,−1,…) and Q = DM⁻¹D. The first column of Q is all ones. Since S(D) = −D, we also have S(Q) = DM⁻²D = Q². Uniqueness forces Q = M. Consequently M⁻¹ = 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 = [[1,0],[𝟙,M²]], where 𝟙 is the column of ones. The first column of Mʳ below its initial entry is therefore v = (I + M² + ⋯ + M^(2r−2))𝟙 = (M + M³ + ⋯ + M^(2r−1))e₀.

The shifted-power identity identifies vᵢ = T(k+i,k−1). Multiplication by M−M⁻¹ telescopes exactly: (M−M⁻¹)v = (M^(2r)−I)e₀. Take coordinate d = n−k > 0. The right side is T(n,k). On the left, the alternating inverse gives Σᵢ₌₀ᵈ T(d,i)T(k+i,k−1)(1−(−1)^(d+i)).

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 related repository develops binary-partition and diagonal results for this matrix family. Its inspected August 2026 document still lists the June 2025 entry recurrence as open. Those related results and the matrix-power relation are prior work; this source check does not establish worldwide priority for the present argument. The inspected document.

The composition recurrence

For A382991, let a(n) be the coefficient of xⁿ in A(x) = 1 + Σₘ≥₁ ∏ⱼ₌₁ᵐ (jx + x²/(1−x)). 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(n,k) = binom(n+k,k) + Σⱼ₌₀ᵏ⁺¹ binom(k+1,j) R(n−1,j). 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.

Solve all columns at once

The useful general identity works over any commutative ring with identity. Choose h ∈ 1+xK[[x]], put B(n,k) = [xⁿ]h^(k+1), and define S(0,k) = 1 and S(n,k) = B(n,k) + Σⱼ₌₀ᵏ⁺¹ binom(k+1,j)S(n−1,j).

If z raised to an overlined i denotes the rising product z(z+1)⋯(z+i−1), with empty product one, then Cₖ(x) := Σₙ≥₀ S(n,k)xⁿ = h Σᵢ≥₀ xⁱ (h+1)^(overline i) (h+i)^k.

For each coefficient only finitely many i contribute. Applying the binomial theorem gives x Σⱼ₌₀ᵏ⁺¹ binom(k+1,j)Cⱼ = h Σᵢ≥₀ x^(i+1)(h+1)^(overline i)(h+i+1)^(k+1) = Cₖ−h^(k+1). 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) = binom(n+k,k), so Cₖ generates the kth R column. At k = 0, 1+xC₀ = 1+Σₘ≥₁ xᵐu^(overline m). Since x(u+j−1) = jx+x²/(1−x), 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β(x) = 1 + Σₘ≥₁ ∏ⱼ₌₁ᵐ (jx + βx²/(1−x)). 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β(n)/n! = 1 + βHₙ₋₁/n + Oβ((log n)²/n²), where Hₙ₋₁ = 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ₙ₋₁. 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. This is an analytic estimate proved in the paper, rather than an extrapolation from computed terms.

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.

Sulayman Bowles initiated and directed the work. OpenAI Codex developed the arguments, wrote this article and the paper, and wrote and ran the programs. Separately prompted Codex instances reviewed the proofs and wrote independent checks. These are automated reviews, without human peer review or formal proof-assistant verification. The original recurrences, sequence definitions and known matrix identities belong to the cited prior sources. Historical priority remains unconfirmed.

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.

Sources

1. user231922 — Equivalent recursion for A078121

   MathOverflow · 2025-06-01 · Original proof request

   Verified Oct 19, 2026

   Contains the parity recurrence proved here; its boundary domain is 0<k<n.

2. A078121 — The On-Line Encyclopedia of Integer Sequences

   The OEIS Foundation Inc. · Sequence and prior identities

   Verified Oct 19, 2026

   Credits Mikhail Kurkov for the conjectured recurrence; records the established shifted-power matrix relation.

3. user231922 — Recursion for A382991

   MathOverflow · 2025-04-18 · Original proof request

   Verified Oct 19, 2026

   The proposed binomial recurrence and composition-sequence identity.

4. A382991 — The On-Line Encyclopedia of Integer Sequences

   The OEIS Foundation Inc. · Sequence and prior generating function

   Verified Oct 19, 2026

   Sequence, composition interpretation and product generating function are prior work. No sequence-extension claim is made.

5. Andrew R. Epstein — A078121 diagonal proof and remaining questions

   GitHub, Eppie/oeis-proofs · Related prior research, immutable inspected revision

   Verified Oct 19, 2026

   Section 6(c) leaves the June 2025 entry recurrence open. The binary-partition and diagonal results in this document are distinct prior work; this comparison does not establish worldwide priority.

6. Written proof submitted for maintainer review

   GitHub, Eppie/oeis-proofs · 2026-10-19 · Open review submission

   Verified Oct 19, 2026

   A written proof and exact-check summary were submitted for review. An open issue is not acceptance, journal publication or proof-assistant verification.

Supporting material

• Two requested recurrence proofs

  Six-page paper with full proofs, weighted extension, asymptotic estimate, references and attribution. Retains its pre-publication status wording.

• Source, proofs and exact verification programs

  Editable LaTeX, standard-library Python verifiers, independent automated reviews, source checks and reproduction instructions.

• Further checked mathematical work: proofs and exact programs

  Partial results for harder A078121 diagonal questions and divisor-word growth, with source, exact programs and automated reviews. General unresolved cases are stated explicitly.

Read next