krawtchouk_alternating_sum_eval
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.
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).
uses
krawtchouk_generating_function,Finset.sum_congrhave 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]
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).
have h1 : (1 - (-1 : ℝ)) = 2 := by ring have h2 : (1 + (-1 : ℝ)) = 0 := by ring rw [h1, h2]
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.
split_ifs with h
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.
uses
Nat.sub_self,pow_zero,mul_one· subst h rw [Nat.sub_self, pow_zero, mul_one]
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`.
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.
- In Lean, the power 0^0 is defined to be 1 in any monoid with zero, following the standard algebraic convention. This allows 0^(n - n) = 0^0 = 1 to hold without special cases.
- The nonzeroness condition n - x ≠ 0 in the x ≠ n branch is discharged inline by the linear arithmetic tactic `omega` from the strict positivity 0 < n - x.
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.
/-- 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]