AFTD Auto-Formalizing Theoretical Domains

krawtchouk_alternating_sum_eval

theoremverifiedformalization

Alternating sum of Krawtchouk polynomials. Let n and x be natural numbers with x <= n. Then the alternating sum sum_{j=0}^n (-1)^j K_j^{(n)}(x) equals 2^n if x = n, and equals 0 if x < n.

Statement

theorem krawtchouk_alternating_sum_eval (n x : ℕ) (hx : x ≤ n) :
    ∑ j ∈ Finset.range (n + 1), (-1 : ℝ) ^ j * krawtchouk n j x = if x = n then (2 : ℝ) ^ n else 0
Formalizes
MacWilliams & Sloane, The Theory of Error-Correcting Codes (1977), Ch. 5
Verified
11 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • krawtchouk_generating_functionGenerating function of the Krawtchouk polynomials. Let $n$ and $x$ be natural numbers with $x \le n$, and let $K_j^{(n)}(x)$ denote the…
  • krawtchoukFor naturals $n$, $j$, $x$, \[ K_j^{(n)}(x) \;=\; \sum_{i=0}^{j} (-1)^i \binom{x}{i}\binom{n-x}{j-i}, \] where the subtraction $n-x$ is…

Read back from the Lean

For all natural numbers $n$ and $x$ satisfying $x \le n$, the alternating sum over $j \in \{0, \dots, n\}$ of $(-1)^j \cdot \operatorname{krawtchouk}(n, j, x)$ equals $2^n$ if $x = n$, and $0$ otherwise (with all calculations in the real numbers).

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 alternating sum is evaluated by specializing the generating function identity ∑_{j=0}^n K_j^{(n)}(x) z^j = (1 - z)^x (1 + z)^{n-x} to z = -1. Commuting the factors in each summand and simplifying the bases 1 - (-1) = 2 and 1 + (-1) = 0 reduces the sum to 2^x * 0^(n - x). The argument then splits on whether x = n: if x = n, the exponent n - x is 0, yielding 2^n * 0^0 = 2^n; if x < n, the exponent n - x is strictly positive, yielding 2^x * 0 = 0.

  1. The alternating sum equals (1 - (-1))^x * (1 + (-1))^(n - x).

    Specializing the generating function identity for Krawtchouk polynomials to z = -1 expresses ∑_{j=0}^n K_j^{(n)}(x) (-1)^j as (1 - (-1))^x (1 + (-1))^(n - x). Since multiplication in ℝ is commutative, each term (-1)^j K_j^{(n)}(x) in the alternating sum equals K_j^{(n)}(x) (-1)^j (proved term-by-term using `Finset.sum_congr`), so the sum rewrites to (1 - (-1))^x (1 + (-1))^(n - x).

    lines 4–10

    uses krawtchouk_generating_function, Finset.sum_congr

      have hgen := krawtchouk_generating_function n x hx (-1 : ℝ)
      have h_comm : (∑ j ∈ Finset.range (n + 1), (-1 : ℝ) ^ j * krawtchouk n j x) =
                    ∑ j ∈ Finset.range (n + 1), krawtchouk n j x * (-1 : ℝ) ^ j := by
        apply Finset.sum_congr rfl
        intro j _
        ring
      rw [h_comm, hgen]
  2. The expression simplifies to 2^x * 0^(n - x) = (if x = n then 2^n else 0).

    By elementary ring arithmetic, 1 - (-1) = 2 and 1 + (-1) = 0. Rewriting with these two facts simplifies (1 - (-1))^x (1 + (-1))^(n - x) to 2^x * 0^(n - x).

    lines 11–13

      have h1 : (1 - (-1 : ℝ)) = 2 := by ring
      have h2 : (1 + (-1 : ℝ)) = 0 := by ring
      rw [h1, h2]
  3. It suffices to evaluate 2^x * 0^(n - x) in the two cases x = n and x ≠ n.

    We split into cases based on the conditional expression depending on whether x = n.

    line 14

      split_ifs with h
  4. When x = n, the expression 2^x * 0^(n - x) evaluates to 2^n.

    Substituting x = n into 2^x * 0^(n - x), the exponent of 0 becomes n - n = 0 by `Nat.sub_self`. Since 0^0 = 1 by `pow_zero` and 2^n * 1 = 2^n by `mul_one`, the expression evaluates to 2^n.

    lines 15–16

    uses Nat.sub_self, pow_zero, mul_one

      · subst h
        rw [Nat.sub_self, pow_zero, mul_one]
  5. When x ≠ n, the expression 2^x * 0^(n - x) evaluates to 0.

    From x ≤ n and x ≠ n, we obtain x < n by `Nat.lt_of_le_of_ne`, which gives 0 < n - x by `Nat.sub_pos_of_lt`. Because the exponent n - x is strictly positive and therefore nonzero, 0^(n - x) = 0 by `zero_pow`. Multiplying by 2^x gives 2^x * 0 = 0 by `mul_zero`.

    lines 17–18

    uses Nat.sub_pos_of_lt, Nat.lt_of_le_of_ne, zero_pow, mul_zero

      · have hpos : 0 < n - x := Nat.sub_pos_of_lt (Nat.lt_of_le_of_ne hx h)
        rw [zero_pow (by omega), mul_zero]
krawtchouk_generating_function
For x ≤ n and any real z, the generating function identity ∑_{j=0}^n K_j^{(n)}(x) z^j = (1 - z)^x (1 + z)^{n-x} holds.
Finset.sum_congr
Two sums over finite sets are equal if their index sets are equal and their summands agree on each element.
Nat.sub_self
For any natural number n, n - n = 0.
pow_zero
Any element raised to the power 0 equals 1.
mul_one
Multiplying any element by 1 leaves it unchanged.
Nat.sub_pos_of_lt
If m < n for natural numbers, then 0 < n - m.
Nat.lt_of_le_of_ne
If n ≤ m and n ≠ m, then n < m.
zero_pow
Zero raised to any nonzero natural power equals 0.
mul_zero
Multiplying any element by 0 yields 0.

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

/-- Alternating sum of binary Krawtchouk polynomials: evaluates to 2^n when x = n and to 0 when x < n. -/theorem krawtchouk_alternating_sum_eval (n x : ℕ) (hx : x ≤ n) :    ∑ j ∈ Finset.range (n + 1), (-1 : ℝ) ^ j * krawtchouk n j x = if x = n then (2 : ℝ) ^ n else 0 := by  have hgen := krawtchouk_generating_function n x hx (-1 : ℝ)  have h_comm : (∑ j ∈ Finset.range (n + 1), (-1 : ℝ) ^ j * krawtchouk n j x) =                ∑ j ∈ Finset.range (n + 1), krawtchouk n j x * (-1 : ℝ) ^ j := by    apply Finset.sum_congr rfl    intro j _    ring  rw [h_comm, hgen]  have h1 : (1 - (-1 : ℝ)) = 2 := by ring  have h2 : (1 + (-1 : ℝ)) = 0 := by ring  rw [h1, h2]  split_ifs with h  · subst h    rw [Nat.sub_self, pow_zero, mul_one]  · have hpos : 0 < n - x := Nat.sub_pos_of_lt (Nat.lt_of_le_of_ne hx h)    rw [zero_pow (by omega), mul_zero]
See it in the graphDiscuss this resultChallenge it