/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import FormalConjecturesUtilA differential generating function
The generating function satisfies $A(x)=x+(xA(x)^2)'$. Its constant term is zero. Seiichi Manyama's recurrence is $a(1)=1$ and $a(n)=(n+1)\sum_{k=1}^{n-1}a(k)a(n-k)$ for $n>1$.
References:
[Li26] Wentao Li, Parity and divisibility for A397588, 2026.
@[expose] public sectionnamespace OeisA397588Manyama's coefficient recurrence, extended by $a(0)=0$.
def a : ℕ → ℕ
| 0 => 0
| 1 => 1
| n + 2 =>
(n + 3) * ∑ k ∈ (Finset.Icc 1 (n + 1)).attach, a k.1 * a (n + 2 - k.1)
termination_by n => n
decreasing_by
n:ℕk:↥(Finset.Icc 1 (n + 1))⊢ ↑k < n.succ.succ All goals completed! 🐙
n:ℕk:↥(Finset.Icc 1 (n + 1))⊢ n + 2 - ↑k < n.succ.succ All goals completed! 🐙The recurrence without attached membership proofs.
@[category API, AMS 11]
theorem a_succ_succ (n : ℕ) :
a (n + 2) = (n + 3) * ∑ k ∈ Finset.Icc 1 (n + 1), a k * a (n + 2 - k) := n:ℕ⊢ a (n + 2) = (n + 3) * ∑ k ∈ Finset.Icc 1 (n + 1), a k * a (n + 2 - k)
n:ℕ⊢ (n + 3) * ∑ k ∈ (Finset.Icc 1 (n + 1)).attach, a ↑k * a (n + 2 - ↑k) =
(n + 3) * ∑ k ∈ Finset.Icc 1 (n + 1), a k * a (n + 2 - k)
All goals completed! 🐙Manyama's recurrence for every index greater than one.
@[category API, AMS 11]
theorem a_of_gt_one {n : ℕ} (hn : 1 < n) :
a n = (n + 1) * ∑ k ∈ Finset.Icc 1 (n - 1), a k * a (n - k) := n:ℕhn:1 < n⊢ a n = (n + 1) * ∑ k ∈ Finset.Icc 1 (n - 1), a k * a (n - k)
cases n with
hn:1 < 0⊢ a 0 = (0 + 1) * ∑ k ∈ Finset.Icc 1 (0 - 1), a k * a (0 - k) All goals completed! 🐙
n:ℕhn:1 < n + 1⊢ a (n + 1) = (n + 1 + 1) * ∑ k ∈ Finset.Icc 1 (n + 1 - 1), a k * a (n + 1 - k)
cases n with
hn:1 < 0 + 1⊢ a (0 + 1) = (0 + 1 + 1) * ∑ k ∈ Finset.Icc 1 (0 + 1 - 1), a k * a (0 + 1 - k) All goals completed! 🐙
n:ℕhn:1 < n + 1 + 1⊢ a (n + 1 + 1) = (n + 1 + 1 + 1) * ∑ k ∈ Finset.Icc 1 (n + 1 + 1 - 1), a k * a (n + 1 + 1 - k) All goals completed! 🐙@[category test, AMS 11]
theorem a_0 : a 0 = 0 := ⊢ a 0 = 0
All goals completed! 🐙@[category test, AMS 11]
theorem a_1 : a 1 = 1 := ⊢ a 1 = 1
All goals completed! 🐙hI:Finset.Icc 1 (2 - 1) = {1}⊢ (2 + 1) * ∑ k ∈ {1}, a k * a (2 - k) = 3
norm_num [a_1] All goals completed! 🐙
@[category test, AMS 11]
theorem a_3 : a 3 = 24 := by ⊢ a 3 = 24
have hI : Finset.Icc (1 : ℕ) (3 - 1) = {1, 2} := by decide hI:Finset.Icc 1 (3 - 1) = {1, 2}⊢ a 3 = 24 hI:Finset.Icc 1 (3 - 1) = {1, 2}⊢ a 3 = 24
rw [a_of_gt_one (by hI:Finset.Icc 1 (3 - 1) = {1, 2}⊢ 1 < 3 hI:Finset.Icc 1 (3 - 1) = {1, 2}⊢ (3 + 1) * ∑ k ∈ {1, 2}, a k * a (3 - k) = 24 decide All goals completed! 🐙 hI:Finset.Icc 1 (3 - 1) = {1, 2}⊢ (3 + 1) * ∑ k ∈ {1, 2}, a k * a (3 - k) = 24 : 1 < 3), hI hI:Finset.Icc 1 (3 - 1) = {1, 2}⊢ (3 + 1) * ∑ k ∈ {1, 2}, a k * a (3 - k) = 24 hI:Finset.Icc 1 (3 - 1) = {1, 2}⊢ (3 + 1) * ∑ k ∈ {1, 2}, a k * a (3 - k) = 24] hI:Finset.Icc 1 (3 - 1) = {1, 2}⊢ (3 + 1) * ∑ k ∈ {1, 2}, a k * a (3 - k) = 24
norm_num [a_1, a_2] All goals completed! 🐙
@[category test, AMS 11]
theorem a_4 : a 4 = 285 := by ⊢ a 4 = 285
have hI : Finset.Icc (1 : ℕ) (4 - 1) = {1, 2, 3} := by decide hI:Finset.Icc 1 (4 - 1) = {1, 2, 3}⊢ a 4 = 285 hI:Finset.Icc 1 (4 - 1) = {1, 2, 3}⊢ a 4 = 285
rw [a_of_gt_one (by hI:Finset.Icc 1 (4 - 1) = {1, 2, 3}⊢ 1 < 4 hI:Finset.Icc 1 (4 - 1) = {1, 2, 3}⊢ (4 + 1) * ∑ k ∈ {1, 2, 3}, a k * a (4 - k) = 285 decide All goals completed! 🐙 hI:Finset.Icc 1 (4 - 1) = {1, 2, 3}⊢ (4 + 1) * ∑ k ∈ {1, 2, 3}, a k * a (4 - k) = 285 : 1 < 4), hI hI:Finset.Icc 1 (4 - 1) = {1, 2, 3}⊢ (4 + 1) * ∑ k ∈ {1, 2, 3}, a k * a (4 - k) = 285 hI:Finset.Icc 1 (4 - 1) = {1, 2, 3}⊢ (4 + 1) * ∑ k ∈ {1, 2, 3}, a k * a (4 - k) = 285] hI:Finset.Icc 1 (4 - 1) = {1, 2, 3}⊢ (4 + 1) * ∑ k ∈ {1, 2, 3}, a k * a (4 - k) = 285
norm_num [a_1, a_2, a_3] All goals completed! 🐙
@[category test, AMS 11]
theorem a_5 : a 5 = 4284 := by ⊢ a 5 = 4284
have hI : Finset.Icc (1 : ℕ) (5 - 1) = {1, 2, 3, 4} := by decide hI:Finset.Icc 1 (5 - 1) = {1, 2, 3, 4}⊢ a 5 = 4284 hI:Finset.Icc 1 (5 - 1) = {1, 2, 3, 4}⊢ a 5 = 4284
rw [a_of_gt_one (by hI:Finset.Icc 1 (5 - 1) = {1, 2, 3, 4}⊢ 1 < 5 hI:Finset.Icc 1 (5 - 1) = {1, 2, 3, 4}⊢ (5 + 1) * ∑ k ∈ {1, 2, 3, 4}, a k * a (5 - k) = 4284 decide All goals completed! 🐙 hI:Finset.Icc 1 (5 - 1) = {1, 2, 3, 4}⊢ (5 + 1) * ∑ k ∈ {1, 2, 3, 4}, a k * a (5 - k) = 4284 : 1 < 5), hI hI:Finset.Icc 1 (5 - 1) = {1, 2, 3, 4}⊢ (5 + 1) * ∑ k ∈ {1, 2, 3, 4}, a k * a (5 - k) = 4284 hI:Finset.Icc 1 (5 - 1) = {1, 2, 3, 4}⊢ (5 + 1) * ∑ k ∈ {1, 2, 3, 4}, a k * a (5 - k) = 4284] hI:Finset.Icc 1 (5 - 1) = {1, 2, 3, 4}⊢ (5 + 1) * ∑ k ∈ {1, 2, 3, 4}, a k * a (5 - k) = 4284
norm_num [a_1, a_2, a_3, a_4] All goals completed! 🐙"Conjecture: $a(n)$ is odd iff $n$ is a power of $2$ for $n \ge 1$."
Paul D. Hanna, Jul 03 2026.
Lean formalization by Wentao Li, with AI assistance; see [Li26].
@[category research solved, AMS 11,
formal_proof using lean4 at "https://github.com/VictorLiwentao/lean-oeis-proofs/blob/0a23974e54b90afd1453ef02c27cf8f617bad940/LeanOeisProofs/NewFormalization/A397588.lean#L211"]
theorem conjecture_parity (n : ℕ) (hn : 1 ≤ n) :
Odd (a n) ↔ ∃ k : ℕ, n = 2 ^ k := by n:ℕhn:1 ≤ n⊢ Odd (a n) ↔ ∃ k, n = 2 ^ k
sorry All goals completed! 🐙"$a(n)$ divisible by $3$ for $n > 1$."
Paul D. Hanna, Jul 03 2026.
Lean formalization by Wentao Li, with AI assistance; see [Li26].
@[category research solved, AMS 11,
formal_proof using lean4 at "https://github.com/VictorLiwentao/lean-oeis-proofs/blob/0a23974e54b90afd1453ef02c27cf8f617bad940/LeanOeisProofs/NewFormalization/A397588.lean#L325"]
theorem three_dvd_a (n : ℕ) (hn : 1 < n) : 3 ∣ a n := by n:ℕhn:1 < n⊢ 3 ∣ a n
sorry All goals completed! 🐙end OeisA397588