krawtchouk_generating_function
theoremverifiedimported Lean
Generating function of the Krawtchouk polynomials. Let $n$ and $x$ be natural numbers with $x \le n$, and let $K_j^{(n)}(x)$ denote the binary Krawtchouk polynomial. Then for every real $z$, \[ \sum_{j=0}^{n} K_j^{(n)}(x)\, z^{j} \;=\; (1-z)^{x}\,(1+z)^{\,n-x}. \]
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open scoped BigOperators in set_option maxHeartbeats 800000 in theorem krawtchouk_generating_function (n x : ℕ) (hx : x ≤ n) (z : ℝ) : ∑ j ∈ Finset.range (n + 1), krawtchouk n j x * z ^ j = (1 - z) ^ x * (1 + z) ^ (n - x)
- Source
- TCSlib, `krawtchouk_generating_function`
- Lean proof
- By Frederick Dehmel, Hydroxyi (from the file's git history), from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.krawtchouk_generating_function← krawtchouk_generating_function (TCSlib/ErrorCorrectingCodes/MRRW.lean:150): adapted
What was changed in
krawtchouk_generating_function--- TCSlib/ErrorCorrectingCodes/MRRW.lean:150 (krawtchouk_generating_function) +++ as compiled here @@ -1 +1,5 @@ +set_option autoImplicit true in +set_option relaxedAutoImplicit true in +open scoped BigOperators in +set_option maxHeartbeats 800000 in theorem krawtchouk_generating_function (n x : ℕ) (hx : x ≤ n) (z : ℝ) : @@ -8,3 +12,3 @@ have hFubini : ∑ j ∈ Finset.range (n + 1), ∑ i ∈ Finset.range (j + 1), (-1 : ℝ) ^ i * Nat.choose x i * Nat.choose (n - x) (j - i) * z ^ j = ∑ i ∈ Finset.range (n + 1), ∑ j ∈ Finset.Ico i (n + 1), (-1 : ℝ) ^ i * Nat.choose x i * Nat.choose (n - x) (j - i) * z ^ j := by - rw [ Finset.range_eq_Ico, Finset.sum_Ico_Ico_comm ]; + simp only [Finset.range_eq_Ico]; rw [ Finset.sum_Ico_Ico_comm ]; rw [ hFubini, ← Finset.sum_subset ( Finset.range_mono ( Nat.succ_le_succ hx ) ) ]; - Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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…
- Used by 2
- krawtchouk_sum_evalTotal sum of Krawtchouk polynomials. Let n and x be natural numbers with x <= n. Then the sum of the binary Krawtchouk polynomials…
- krawtchouk_alternating_sum_evalAlternating sum of Krawtchouk polynomials. Let n and x be natural numbers with x <= n. Then the alternating sum sum_{j=0}^n (-1)^j…
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.
set_option autoImplicit true inset_option relaxedAutoImplicit true inopen scoped BigOperators inset_option maxHeartbeats 800000 intheorem krawtchouk_generating_function (n x : ℕ) (hx : x ≤ n) (z : ℝ) : ∑ j ∈ Finset.range (n + 1), krawtchouk n j x * z ^ j = (1 - z) ^ x * (1 + z) ^ (n - x) := by -- The key identity is: ∑_{j=0}^{n} (∑_{i=0}^{j} (-1)^i C(x,i) C(n-x, j-i)) z^j = (1-z)^x (1+z)^{n-x}. have hKey : ∑ j ∈ Finset.range (n + 1), ∑ i ∈ Finset.range (j + 1), (-1 : ℝ) ^ i * Nat.choose x i * Nat.choose (n - x) (j - i) * z ^ j = (1 - z) ^ x * (1 + z) ^ (n - x) := by -- By Fubini's theorem, we can interchange the order of summation. have hFubini : ∑ j ∈ Finset.range (n + 1), (∑ i ∈ Finset.range (j + 1), (-1 : ℝ) ^ i * Nat.choose x i * Nat.choose (n - x) (j - i) * z ^ j) = ∑ i ∈ Finset.range (x + 1), (-1 : ℝ) ^ i * Nat.choose x i * (∑ j ∈ Finset.Ico i (n + 1), Nat.choose (n - x) (j - i) * z ^ j) := by have hFubini : ∑ j ∈ Finset.range (n + 1), ∑ i ∈ Finset.range (j + 1), (-1 : ℝ) ^ i * Nat.choose x i * Nat.choose (n - x) (j - i) * z ^ j = ∑ i ∈ Finset.range (n + 1), ∑ j ∈ Finset.Ico i (n + 1), (-1 : ℝ) ^ i * Nat.choose x i * Nat.choose (n - x) (j - i) * z ^ j := by simp only [Finset.range_eq_Ico]; rw [ Finset.sum_Ico_Ico_comm ]; rw [ hFubini, ← Finset.sum_subset ( Finset.range_mono ( Nat.succ_le_succ hx ) ) ]; · simp +decide only [mul_assoc, Finset.mul_sum _ _ _]; · intro k hk hxk have hzero : x.choose k = 0 := Nat.choose_eq_zero_of_lt (Nat.not_le.mp (by simpa [Finset.mem_range, Nat.lt_succ_iff] using hxk)) simp [hzero]; -- Let's simplify the inner sum $\sum_{j=i}^{n} \binom{n-x}{j-i} z^j$. have hInner : ∀ i ∈ Finset.range (x + 1), ∑ j ∈ Finset.Ico i (n + 1), Nat.choose (n - x) (j - i) * z ^ j = z ^ i * (1 + z) ^ (n - x) := by intro i hi; rw [ add_comm 1 z, add_pow ] ; simp +decide [ mul_comm, Finset.mul_sum _ _ _, Finset.sum_Ico_eq_sum_range ] ; rw [ ← Finset.sum_subset ( Finset.range_mono ( show n - x + 1 ≤ n + 1 - i from by rw [ Nat.le_sub_iff_add_le ] <;> linarith [ Finset.mem_range.mp hi, Nat.sub_add_cancel hx ] ) ) ] <;> simp +decide [ pow_add, mul_assoc ]; exact fun j hj₁ hj₂ => Or.inr <| Or.inr <| Nat.choose_eq_zero_of_lt hj₂; rw [ hFubini, Finset.sum_congr rfl fun i hi => by rw [ hInner i hi ] ]; rw [ show ( 1 - z ) ^ x = ∑ i ∈ Finset.range ( x + 1 ), ( -1 : ℝ ) ^ i * Nat.choose x i * z ^ i by rw [ sub_eq_neg_add, add_pow ] ; congr ; ext ; ring ] ; simp +decide [ mul_assoc, mul_comm, mul_left_comm, Finset.mul_sum _ _ _ ]; simp_all +decide [ ← Finset.sum_mul, krawtchouk ]/-**Lemma 3 (orthogonality)** from the source file.For `0 ≤ r, s ≤ n`, `∑_{x=0}^{n} C(n,x) · K_r(x) · K_s(x) = 2^n · C(n,r) · δ_{r,s}`.-/