AFTD Auto-Formalizing Theoretical Domains

alternating_word_insertion_multiplicity_count_sum

theoremverifiedformalization

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.

  1. 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.

    lines 1–7

    uses Polynomial.coe_pow, Polynomial.coeff_coe, Polynomial.coeff_one_add_X_pow

    open 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]
    
  2. 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 Ψ.

    lines 8–14

    uses PowerSeries.coeff_subst_X_pow, PowerSeries.coeff_mk

    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]
    
  3. 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).

    lines 15–36

    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_pow

    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
  4. 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.

    lines 37–52

    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]
    
  5. 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.

    lines 53–63

    uses Finset.mem_filter, Finset.mem_range

    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
  6. 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.

    lines 64–85

    uses Finset.sum_bij, Finset.mem_filter, Finset.mem_range, Nat.mul_div_cancel_left, Nat.choose_symm_add

      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]
    
  7. 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.

    lines 86–107

    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_reindex

    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
    
  8. 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.

    lines 108–115

    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.

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

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
See it in the graphDiscuss this resultChallenge it