krawtchouk_one
theoremverifiedimported Lean
Value of the first Krawtchouk polynomial. Let $n$ and $x$ be natural numbers with $x \le n$. Then the first binary Krawtchouk polynomial at $x$ satisfies \[ K_1^{(n)}(x) = n - 2x. \]
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open scoped BigOperators in set_option maxHeartbeats 800000 in theorem krawtchouk_one (n x : ℕ) (hx : x ≤ n) : krawtchouk n 1 x = (n : ℝ) - 2 * (x : ℝ)
- Source
- TCSlib, `krawtchouk_one`
- 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_one← krawtchouk_one (TCSlib/ErrorCorrectingCodes/MRRW.lean:140): verbatim
- 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…
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_one (n x : ℕ) (hx : x ≤ n) : krawtchouk n 1 x = (n : ℝ) - 2 * (x : ℝ) := by unfold krawtchouk; norm_num [ Finset.sum_range_succ, hx ] ; ring/-**Lemma 1 (generating function)** from the source file.For every `x ∈ {0,...,n}`, `∑_{j=0}^{n} K_j(x) · z^j = (1 - z)^x · (1 + z)^{n-x}`.-/