alternating_word_insertion_multiplicity_count_sum
For all natural numbers m and k, the sum over t from 0 to k / 2 of Nat.choose (m + 1) (k - 2 * t) * Nat.choose (m + t) t equals Nat.choose (m + k) k.
Statement
theorem alternating_word_insertion_multiplicity_count_sum (m k : ℕ) :
∑ t ∈ Finset.range (k / 2 + 1), (m + 1).choose (k - 2 * t) * (m + t).choose t = (m + k).choose k- Formalizes
- arXiv:2611.01064 Section 5.1
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
For all natural numbers $m$ and $k$, the sum over $t$ from $0$ to $\lfloor k / 2 \rfloor$ of $\binom{m + 1}{k - 2t} \binom{m + t}{t}$ equals $\binom{m + k}{k}$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The identity is proved using generating functions in formal power series over ℤ. Letting Ψ(X) = ∑_{n ≥ 0} Nat.choose (m + n) m * X^n = (1 - X)^(-(m + 1)), the core relation is (1 + X)^(m + 1) * Ψ(X^2) = Ψ(X), which holds because multiplying both sides by (1 - X)^(m + 1) reduces to (1 - X^2)^(m + 1) * Ψ(X^2) = 1. Extracting the coefficient of X^k yields the Cauchy product of (1 + X)^(m + 1) and Ψ(X^2), which by the change of variables t = (k - i) / 2 becomes the target sum. Since the k-th coefficient of Ψ(X) is Nat.choose (m + k) m = Nat.choose (m + k) k, the identity holds in ℤ and transfers to ℕ by injectivity of the natural cast.
The i-th coefficient of (1 + X)^n in formal power series over ℤ is Nat.choose n i.
The formal power series (1 + X)^n is identified with the corresponding polynomial, where taking the i-th coefficient agrees with the polynomial coefficient. The standard polynomial binomial expansion then yields the integer cast of Nat.choose n i.
uses
Polynomial.coe_pow,Polynomial.coeff_coe,Polynomial.coeff_one_add_X_powopen PowerSeries in private lemma zz_coeff_one_add_X_pow_ps (n i : ℕ) : PowerSeries.coeff i ((1 + PowerSeries.X : PowerSeries ℤ) ^ n) = ((n.choose i : ℕ) : ℤ) := by have h2 : ((1 + Polynomial.X : Polynomial ℤ) : PowerSeries ℤ) = (1 + PowerSeries.X : PowerSeries ℤ) := by simp rw [← h2, ← Polynomial.coe_pow, Polynomial.coeff_coe, Polynomial.coeff_one_add_X_pow]
For the power series Ψ(X) with k-th coefficient Nat.choose (m + k) m, the n-th coefficient of Ψ(X^2) is Nat.choose (m + n/2) m when n is even, and 0 when n is odd.
Applying the coefficient formula for substitution of X^2 into a power series, only even powers survive, with X^(2k) receiving the coefficient of X^k from Ψ.
uses
PowerSeries.coeff_subst_X_pow,PowerSeries.coeff_mkprivate lemma zz_coeff_subst_sq_ps (m n : ℕ) : PowerSeries.coeff n (PowerSeries.subst (PowerSeries.X ^ 2 : PowerSeries ℤ) (PowerSeries.mk fun k => ((m + k).choose m : ℤ))) = if 2 ∣ n then ((m + n / 2).choose m : ℤ) else 0 := by rw [PowerSeries.coeff_subst_X_pow (by norm_num : (2 : ℕ) ≠ 0)] simp [PowerSeries.coeff_mk]
Setting Ψ(X) = ∑_n Nat.choose (m + n) m * X^n and S(X) = Ψ(X^2), we have S(X) * (1 - X^2)^(m + 1) = 1 and (1 + X)^(m + 1) * (1 - X)^(m + 1) = (1 - X^2)^(m + 1).
The negative binomial series satisfies Ψ(X) * (1 - X)^(m + 1) = 1. Substituting X^2 for X commutes with algebra operations and transforms this relation into S(X) * (1 - X^2)^(m + 1) = 1. Factoring (1 + X)^(m + 1) * (1 - X)^(m + 1) as ((1 + X)(1 - X))^(m + 1) gives (1 - X^2)^(m + 1).
uses
PowerSeries.HasSubst.X_pow,PowerSeries.mk_add_choose_mul_one_sub_pow_eq_one,PowerSeries.subst_pow,PowerSeries.subst_sub,PowerSeries.subst_X,PowerSeries.coe_substAlgHom,map_one,PowerSeries.subst_mul,mul_powprivate lemma zz_ps_gf (m : ℕ) : (1 + PowerSeries.X : PowerSeries ℤ) ^ (m + 1) * PowerSeries.subst (PowerSeries.X ^ 2 : PowerSeries ℤ) (PowerSeries.mk fun n => ((m + n).choose m : ℤ)) = PowerSeries.mk fun n => ((m + n).choose m : ℤ) := by have hh : PowerSeries.HasSubst (PowerSeries.X ^ 2 : PowerSeries ℤ) := PowerSeries.HasSubst.X_pow (by norm_num : (2 : ℕ) ≠ 0) set Ψ : PowerSeries ℤ := PowerSeries.mk fun n => ((m + n).choose m : ℤ) with hΨ set S : PowerSeries ℤ := PowerSeries.subst (PowerSeries.X ^ 2) Ψ with hS have hΨD : Ψ * (1 - PowerSeries.X : PowerSeries ℤ) ^ (m + 1) = 1 := PowerSeries.mk_add_choose_mul_one_sub_pow_eq_one ℤ m have hsub : PowerSeries.subst (PowerSeries.X ^ 2 : PowerSeries ℤ) ((1 - PowerSeries.X : PowerSeries ℤ) ^ (m + 1)) = (1 - PowerSeries.X ^ 2 : PowerSeries ℤ) ^ (m + 1) := by rw [PowerSeries.subst_pow hh, PowerSeries.subst_sub hh, PowerSeries.subst_X hh, ← PowerSeries.coe_substAlgHom hh, map_one] have hSD : S * (1 - PowerSeries.X ^ 2 : PowerSeries ℤ) ^ (m + 1) = 1 := by rw [hS, ← hsub, ← PowerSeries.subst_mul hh, hΨD, ← PowerSeries.coe_substAlgHom hh, map_one] have hΦD : (1 + PowerSeries.X : PowerSeries ℤ) ^ (m + 1) * (1 - PowerSeries.X : PowerSeries ℤ) ^ (m + 1) = (1 - PowerSeries.X ^ 2 : PowerSeries ℤ) ^ (m + 1) := by rw [← mul_pow]; ring
The formal power series identity (1 + X)^(m + 1) * Ψ(X^2) = Ψ(X) holds.
Multiplying (1 + X)^(m + 1) * S(X) by (1 - X)^(m + 1) rearranges to S(X) * (1 - X^2)^(m + 1) = 1. Since Ψ(X) * (1 - X)^(m + 1) = 1 as well, both sides equal 1 when multiplied by (1 - X)^(m + 1). Because 1 - X has constant term 1 ≠ 0, the power (1 - X)^(m + 1) is non-zero, allowing it to be cancelled from the right.
uses
congrArg,pow_ne_zero,mul_right_cancel₀have h1 : (1 + PowerSeries.X : PowerSeries ℤ) ^ (m + 1) * S * (1 - PowerSeries.X : PowerSeries ℤ) ^ (m + 1) = 1 := by have hrw : (1 + PowerSeries.X : PowerSeries ℤ) ^ (m + 1) * S * (1 - PowerSeries.X : PowerSeries ℤ) ^ (m + 1) = S * ((1 + PowerSeries.X : PowerSeries ℤ) ^ (m + 1) * (1 - PowerSeries.X : PowerSeries ℤ) ^ (m + 1)) := by ring rw [hrw, hΦD, hSD] have hne : (1 - PowerSeries.X : PowerSeries ℤ) ^ (m + 1) ≠ 0 := by have h1X : (1 - PowerSeries.X : PowerSeries ℤ) ≠ 0 := by intro h have hc := congrArg PowerSeries.constantCoeff h simp at hc exact pow_ne_zero _ h1X refine mul_right_cancel₀ hne ?_ rw [h1, hΨD]
For every i ≤ k such that 2 divides k - i, we have k - 2 * ((k - i) / 2) = i.
Since 2 divides k - i, the natural division (k - i) / 2 is exact, so doubling it gives k - i. Subtracting this from k leaves i.
uses
Finset.mem_filter,Finset.mem_rangeprivate lemma zz_reindex (m k : ℕ) : (∑ i ∈ (Finset.range (k + 1)).filter (fun i => 2 ∣ (k - i)), ((m + 1).choose i : ℤ) * ((m + (k - i) / 2).choose m : ℤ)) = ∑ t ∈ Finset.range (k / 2 + 1), ((m + 1).choose (k - 2 * t) : ℤ) * ((m + t).choose t : ℤ) := by have hdvd : ∀ i, i ∈ (Finset.range (k + 1)).filter (fun i => 2 ∣ (k - i)) → k - 2 * ((k - i) / 2) = i := by intro i hi simp only [Finset.mem_filter, Finset.mem_range] at hi obtain ⟨hik, c, hc⟩ := hi omega
The filtered sum ∑_{i ≤ k, 2 ∣ (k - i)} Nat.choose (m + 1) i * Nat.choose (m + (k - i) / 2) m equals the sum ∑_{t = 0}^{k / 2} Nat.choose (m + 1) (k - 2 * t) * Nat.choose (m + t) t.
We define a bijection between indices i ∈ {0, ..., k} with 2 ∣ (k - i) and t ∈ {0, ..., k / 2} given by t = (k - i) / 2, with inverse i = k - 2 * t. Under this bijection, the summand Nat.choose (m + 1) i * Nat.choose (m + (k - i) / 2) m matches Nat.choose (m + 1) (k - 2 * t) * Nat.choose (m + t) t by binomial symmetry Nat.choose (m + t) m = Nat.choose (m + t) t.
uses
Finset.sum_bij,Finset.mem_filter,Finset.mem_range,Nat.mul_div_cancel_left,Nat.choose_symm_addrefine Finset.sum_bij (fun i _ => (k - i) / 2) ?_ ?_ ?_ ?_ · intro i hi simp only [Finset.mem_filter, Finset.mem_range] at hi simp only [Finset.mem_range]; omega · intro i1 h1 i2 h2 he have e1 := hdvd i1 h1 have e2 := hdvd i2 h2 rw [← e1, ← e2, he] · intro t ht simp only [Finset.mem_range] at ht refine ⟨k - 2 * t, ?_, ?_⟩ · simp only [Finset.mem_filter, Finset.mem_range] exact ⟨by omega, ⟨t, by omega⟩⟩ · show (k - (k - 2 * t)) / 2 = t rw [show k - (k - 2 * t) = 2 * t by omega, Nat.mul_div_cancel_left t (by norm_num)] · intro i hi have e := hdvd i hi show ((m + 1).choose i : ℤ) * ((m + (k - i) / 2).choose m : ℤ) = ((m + 1).choose (k - 2 * ((k - i) / 2)) : ℤ) * ((m + (k - i) / 2).choose ((k - i) / 2) : ℤ) rw [e, Nat.choose_symm_add]
The identity ∑_{t = 0}^{k / 2} Nat.choose (m + 1) (k - 2 * t) * Nat.choose (m + t) t = Nat.choose (m + k) k holds over the integers.
Extracting the coefficient of X^k from both sides of (1 + X)^(m + 1) * Ψ(X^2) = Ψ(X) expresses the left side as a Cauchy product, which simplifies to the sum over even differences k - x. Reindexing this sum transforms it into the desired sum over t. On the right side, the k-th coefficient of Ψ(X) is Nat.choose (m + k) m, which equals Nat.choose (m + k) k by symmetry.
uses
congrArg,zz_ps_gf,PowerSeries.coeff_mul,Finset.Nat.sum_antidiagonal_eq_sum_range_succ_mk,zz_coeff_one_add_X_pow_ps,zz_coeff_subst_sq_ps,PowerSeries.coeff_mk,Finset.sum_congr,Finset.sum_filter,Nat.choose_symm_add,zz_reindexprivate lemma zz_main_sum (m k : ℕ) : ∑ t ∈ Finset.range (k / 2 + 1), (((m + 1).choose (k - 2 * t) : ℕ) : ℤ) * (((m + t).choose t : ℕ) : ℤ) = (((m + k).choose k : ℕ) : ℤ) := by have hcoeff := congrArg (PowerSeries.coeff k) (zz_ps_gf m) rw [PowerSeries.coeff_mul, Finset.Nat.sum_antidiagonal_eq_sum_range_succ_mk] at hcoeff simp only [zz_coeff_one_add_X_pow_ps, zz_coeff_subst_sq_ps, PowerSeries.coeff_mk] at hcoeff have hA : (∑ x ∈ Finset.range (k + 1), (if 2 ∣ (k - x) then ((m + 1).choose x : ℤ) * ((m + (k - x) / 2).choose m : ℤ) else 0)) = ((m + k).choose m : ℤ) := by rw [← hcoeff] refine Finset.sum_congr rfl (fun x _ => ?_) split_ifs <;> simp have hB : (∑ x ∈ (Finset.range (k + 1)).filter (fun i => 2 ∣ (k - i)), ((m + 1).choose x : ℤ) * ((m + (k - x) / 2).choose m : ℤ)) = ((m + k).choose m : ℤ) := by rw [Finset.sum_filter] exact hA have hsym : ((m + k).choose k : ℤ) = ((m + k).choose m : ℤ) := by rw [Nat.choose_symm_add] rw [hsym, ← zz_reindex m k] exact hB
For all natural numbers m and k, the sum ∑_{t = 0}^{k / 2} Nat.choose (m + 1) (k - 2 * t) * Nat.choose (m + t) t equals Nat.choose (m + k) k.
The identity established over the integers transfers to the natural numbers because the canonical cast from ℕ to ℤ is injective.
uses
zz_main_sum,Nat.cast_injective/-- Consistency identity summing multiplicity times count for the alternating word insertion histogram. -/ theorem alternating_word_insertion_multiplicity_count_sum (m k : ℕ) : ∑ t ∈ Finset.range (k / 2 + 1), (m + 1).choose (k - 2 * t) * (m + t).choose t = (m + k).choose k := by have h2 : ((∑ t ∈ Finset.range (k / 2 + 1), (m + 1).choose (k - 2 * t) * (m + t).choose t : ℕ) : ℤ) = (((m + k).choose k : ℕ) : ℤ) := by push_cast exact zz_main_sum m k exact Nat.cast_injective h2
Polynomial.coe_pow- The canonical coercion of a power of a polynomial into power series equals the power of the coercion.
Polynomial.coeff_coe- The n-th coefficient of a coerced polynomial in power series equals its n-th polynomial coefficient.
Polynomial.coeff_one_add_X_pow- The k-th coefficient of (1 + X)^n in a polynomial ring equals Nat.choose n k.
PowerSeries.coeff_subst_X_pow- For k ≠ 0, the n-th coefficient of f(X^k) is the (n/k)-th coefficient of f if k divides n, and 0 otherwise.
PowerSeries.coeff_mk- The n-th coefficient of a power series constructed by PowerSeries.mk f is f(n).
PowerSeries.HasSubst.X_pow- X^n is a valid substitution argument into power series whenever n ≠ 0.
PowerSeries.mk_add_choose_mul_one_sub_pow_eq_one- The power series with coefficients Nat.choose (d + n) d multiplied by (1 - X)^(d + 1) equals 1.
PowerSeries.subst_pow- Power series substitution distributes over powers: (f^n)(g) = (f(g))^n.
PowerSeries.subst_sub- Power series substitution distributes over subtraction: (f - g)(h) = f(h) - g(h).
PowerSeries.subst_X- Substituting g into the indeterminate X yields g.
PowerSeries.coe_substAlgHom- Substitution of a power series is given by evaluating the substitution algebra homomorphism.
map_one- A homomorphism of unital structures maps 1 to 1.
PowerSeries.subst_mul- Power series substitution distributes over multiplication: (f * g)(h) = f(h) * g(h).
mul_pow- In a commutative monoid, (a * b)^n = a^n * b^n.
congrArg- Functions preserve equality: if a = b then f(a) = f(b).
pow_ne_zero- In a reduced monoid with zero, if a ≠ 0 then a^n ≠ 0.
mul_right_cancel₀- If b ≠ 0 and a * b = c * b, then a = c.
Finset.mem_filter- An element belongs to a filtered set {x ∈ s | p x} if and only if it belongs to s and satisfies p.
Finset.mem_range- A natural number m belongs to Finset.range n if and only if m < n.
Finset.sum_bij- A sum over a finite set equals a sum over another if there is a bijection between their index sets that preserves the summands.
Nat.mul_div_cancel_left- For positive n, (n * m) / n = m in natural numbers.
Nat.choose_symm_add- Symmetry of binomial coefficients: Nat.choose (a + b) a = Nat.choose (a + b) b.
PowerSeries.coeff_mul- The n-th coefficient of a product of power series is the sum of products of coefficients over the antidiagonal pairs summing to n.
Finset.Nat.sum_antidiagonal_eq_sum_range_succ_mk- Summing over antidiagonal pairs summing to n is equivalent to summing over k from 0 to n with pairs (k, n - k).
zz_coeff_one_add_X_pow_ps- The i-th coefficient of (1 + X)^n in formal power series over ℤ equals Nat.choose n i.
zz_coeff_subst_sq_ps- The n-th coefficient of Ψ(X^2) equals Nat.choose (m + n/2) m if 2 divides n, and 0 otherwise.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree on each element.
Finset.sum_filter- Summing over elements satisfying a predicate equals summing with an if-then-else condition over the entire set.
zz_reindex- Reindexing lemma showing the filtered sum over even differences k - i equals the sum over t from 0 to k / 2.
zz_ps_gf- The generating function identity (1 + X)^(m + 1) * Ψ(X^2) = Ψ(X) holds in formal power series over ℤ.
zz_main_sum- The alternating word insertion sum identity holds when evaluated in the integers.
Nat.cast_injective- The canonical injection from ℕ into a characteristic-zero ring is injective.
- The proof is carried out in the formal power series ring ℤ[[X]] rather than analytic generating functions over ℝ or ℂ, so convergence is not an issue and coefficients are well-defined purely algebraically.
- The identity is proved first over ℤ in order to allow full algebraic manipulations (such as ring and field-like cancellations) before transferring the result back to ℕ via injectivity of the cast.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open PowerSeries inprivate lemma zz_coeff_one_add_X_pow_ps (n i : ℕ) : PowerSeries.coeff i ((1 + PowerSeries.X : PowerSeries ℤ) ^ n) = ((n.choose i : ℕ) : ℤ) := by have h2 : ((1 + Polynomial.X : Polynomial ℤ) : PowerSeries ℤ) = (1 + PowerSeries.X : PowerSeries ℤ) := by simp rw [← h2, ← Polynomial.coe_pow, Polynomial.coeff_coe, Polynomial.coeff_one_add_X_pow]private lemma zz_coeff_subst_sq_ps (m n : ℕ) : PowerSeries.coeff n (PowerSeries.subst (PowerSeries.X ^ 2 : PowerSeries ℤ) (PowerSeries.mk fun k => ((m + k).choose m : ℤ))) = if 2 ∣ n then ((m + n / 2).choose m : ℤ) else 0 := by rw [PowerSeries.coeff_subst_X_pow (by norm_num : (2 : ℕ) ≠ 0)] simp [PowerSeries.coeff_mk]private lemma zz_ps_gf (m : ℕ) : (1 + PowerSeries.X : PowerSeries ℤ) ^ (m + 1) * PowerSeries.subst (PowerSeries.X ^ 2 : PowerSeries ℤ) (PowerSeries.mk fun n => ((m + n).choose m : ℤ)) = PowerSeries.mk fun n => ((m + n).choose m : ℤ) := by have hh : PowerSeries.HasSubst (PowerSeries.X ^ 2 : PowerSeries ℤ) := PowerSeries.HasSubst.X_pow (by norm_num : (2 : ℕ) ≠ 0) set Ψ : PowerSeries ℤ := PowerSeries.mk fun n => ((m + n).choose m : ℤ) with hΨ set S : PowerSeries ℤ := PowerSeries.subst (PowerSeries.X ^ 2) Ψ with hS have hΨD : Ψ * (1 - PowerSeries.X : PowerSeries ℤ) ^ (m + 1) = 1 := PowerSeries.mk_add_choose_mul_one_sub_pow_eq_one ℤ m have hsub : PowerSeries.subst (PowerSeries.X ^ 2 : PowerSeries ℤ) ((1 - PowerSeries.X : PowerSeries ℤ) ^ (m + 1)) = (1 - PowerSeries.X ^ 2 : PowerSeries ℤ) ^ (m + 1) := by rw [PowerSeries.subst_pow hh, PowerSeries.subst_sub hh, PowerSeries.subst_X hh, ← PowerSeries.coe_substAlgHom hh, map_one] have hSD : S * (1 - PowerSeries.X ^ 2 : PowerSeries ℤ) ^ (m + 1) = 1 := by rw [hS, ← hsub, ← PowerSeries.subst_mul hh, hΨD, ← PowerSeries.coe_substAlgHom hh, map_one] have hΦD : (1 + PowerSeries.X : PowerSeries ℤ) ^ (m + 1) * (1 - PowerSeries.X : PowerSeries ℤ) ^ (m + 1) = (1 - PowerSeries.X ^ 2 : PowerSeries ℤ) ^ (m + 1) := by rw [← mul_pow]; ring have h1 : (1 + PowerSeries.X : PowerSeries ℤ) ^ (m + 1) * S * (1 - PowerSeries.X : PowerSeries ℤ) ^ (m + 1) = 1 := by have hrw : (1 + PowerSeries.X : PowerSeries ℤ) ^ (m + 1) * S * (1 - PowerSeries.X : PowerSeries ℤ) ^ (m + 1) = S * ((1 + PowerSeries.X : PowerSeries ℤ) ^ (m + 1) * (1 - PowerSeries.X : PowerSeries ℤ) ^ (m + 1)) := by ring rw [hrw, hΦD, hSD] have hne : (1 - PowerSeries.X : PowerSeries ℤ) ^ (m + 1) ≠ 0 := by have h1X : (1 - PowerSeries.X : PowerSeries ℤ) ≠ 0 := by intro h have hc := congrArg PowerSeries.constantCoeff h simp at hc exact pow_ne_zero _ h1X refine mul_right_cancel₀ hne ?_ rw [h1, hΨD]private lemma zz_reindex (m k : ℕ) : (∑ i ∈ (Finset.range (k + 1)).filter (fun i => 2 ∣ (k - i)), ((m + 1).choose i : ℤ) * ((m + (k - i) / 2).choose m : ℤ)) = ∑ t ∈ Finset.range (k / 2 + 1), ((m + 1).choose (k - 2 * t) : ℤ) * ((m + t).choose t : ℤ) := by have hdvd : ∀ i, i ∈ (Finset.range (k + 1)).filter (fun i => 2 ∣ (k - i)) → k - 2 * ((k - i) / 2) = i := by intro i hi simp only [Finset.mem_filter, Finset.mem_range] at hi obtain ⟨hik, c, hc⟩ := hi omega refine Finset.sum_bij (fun i _ => (k - i) / 2) ?_ ?_ ?_ ?_ · intro i hi simp only [Finset.mem_filter, Finset.mem_range] at hi simp only [Finset.mem_range]; omega · intro i1 h1 i2 h2 he have e1 := hdvd i1 h1 have e2 := hdvd i2 h2 rw [← e1, ← e2, he] · intro t ht simp only [Finset.mem_range] at ht refine ⟨k - 2 * t, ?_, ?_⟩ · simp only [Finset.mem_filter, Finset.mem_range] exact ⟨by omega, ⟨t, by omega⟩⟩ · show (k - (k - 2 * t)) / 2 = t rw [show k - (k - 2 * t) = 2 * t by omega, Nat.mul_div_cancel_left t (by norm_num)] · intro i hi have e := hdvd i hi show ((m + 1).choose i : ℤ) * ((m + (k - i) / 2).choose m : ℤ) = ((m + 1).choose (k - 2 * ((k - i) / 2)) : ℤ) * ((m + (k - i) / 2).choose ((k - i) / 2) : ℤ) rw [e, Nat.choose_symm_add]private lemma zz_main_sum (m k : ℕ) : ∑ t ∈ Finset.range (k / 2 + 1), (((m + 1).choose (k - 2 * t) : ℕ) : ℤ) * (((m + t).choose t : ℕ) : ℤ) = (((m + k).choose k : ℕ) : ℤ) := by have hcoeff := congrArg (PowerSeries.coeff k) (zz_ps_gf m) rw [PowerSeries.coeff_mul, Finset.Nat.sum_antidiagonal_eq_sum_range_succ_mk] at hcoeff simp only [zz_coeff_one_add_X_pow_ps, zz_coeff_subst_sq_ps, PowerSeries.coeff_mk] at hcoeff have hA : (∑ x ∈ Finset.range (k + 1), (if 2 ∣ (k - x) then ((m + 1).choose x : ℤ) * ((m + (k - x) / 2).choose m : ℤ) else 0)) = ((m + k).choose m : ℤ) := by rw [← hcoeff] refine Finset.sum_congr rfl (fun x _ => ?_) split_ifs <;> simp have hB : (∑ x ∈ (Finset.range (k + 1)).filter (fun i => 2 ∣ (k - i)), ((m + 1).choose x : ℤ) * ((m + (k - x) / 2).choose m : ℤ)) = ((m + k).choose m : ℤ) := by rw [Finset.sum_filter] exact hA have hsym : ((m + k).choose k : ℤ) = ((m + k).choose m : ℤ) := by rw [Nat.choose_symm_add] rw [hsym, ← zz_reindex m k] exact hB/-- Consistency identity summing multiplicity times count for the alternating word insertion histogram. -/theorem alternating_word_insertion_multiplicity_count_sum (m k : ℕ) : ∑ t ∈ Finset.range (k / 2 + 1), (m + 1).choose (k - 2 * t) * (m + t).choose t = (m + k).choose k := by have h2 : ((∑ t ∈ Finset.range (k / 2 + 1), (m + 1).choose (k - 2 * t) * (m + t).choose t : ℕ) : ℤ) = (((m + k).choose k : ℕ) : ℤ) := by push_cast exact zz_main_sum m k exact Nat.cast_injective h2