Kauers–Koutschan recurrence conjecture

What Lean checks

Written proof and exact symbolic verification of both recurrences for all lengths.

Let ana_n count the permutations of 1,…,n1,\ldots,n for which no entries two positions apart give a rise of exactly two. Kauers and Koutschan conjectured a specific order-eight recurrence for ana_n. We prove it for every n≥0n\ge0. The same argument verifies the order-thirteen recurrence that Spahn and Zeilberger also accept for their $100 OEIS donation challenge. Independent review and sponsor adjudication are pending. Original conjecture, §6 · Prize, Challenge 1 · Published operators

The proof cuts the position and value sets into their two parity chains. Inclusion–exclusion on matched adjacencies in the chains produces a matrix with a unitarily invariant distribution. Its two-variable Schur moments are divided differences of derangement numbers. These moments give a short recurrence for the sums occurring in the exact permutation count. Proof · Exact symbolic checker · Original operator, coefficients in ascending degree

The checker substitutes the counting formula directly into both published operators over a rational polynomial ring. It handles the four initial indices separately. As independent enumeration checks, exhaustive enumeration agrees through length eight, and the divided-difference formula agrees with all 301 entries of Matsuo’s published table. Enumeration table

Run from this directory with Python 3.10 or later and SymPy 1.14.

python -m pip install sympy==1.14.0
python verify.py

Prior work

Kauers and Koutschan guessed the recurrence from enumeration data. Matsuo computed through length 300. Spahn and Zeilberger gave inclusion–exclusion methods and posed the prize. Padhi subsequently proved the existence of a recurrence for the whole directed and undirected family. For this specific operator, §6 of Padhi’s paper proves part of the required reduction and records the remaining obstruction. The accompanying repository also lists Challenge 1 as partial. A search of the authors’ pages, the OEIS entry and references, arXiv, GitHub, and exact-operator searches on November 21, 2026 found no earlier full proof. Original authors · Sponsor’s updates · Padhi, §§5–6 · Padhi’s code and status · Research issue