three_token_k2n_domination_arith_split
For every integer n ≥ 4, (n + 1)^2 / 4 - 2 = (n - 1)^2 / 4 + n - 2 in natural number arithmetic.
Statement
theorem three_token_k2n_domination_arith_split (n : ℕ) (hn : 4 ≤ n) :
(n + 1)^2 / 4 - 2 = (n - 1)^2 / 4 + n - 2- Source
- step towards three_token_complete_bipartite_two_exact
- Verified
- 01 Nov 2026
- Axioms
Quot.soundpropext- Used by 1
- amply_regular_params_two_mu_ge_consistentSanity witness that the hypothesis ℓ + 2 ≤ k is not automatic: it can fail while ℓ + 2 ≤ 2μ holds, so the drift lemma's hypothesis…
The proof, explained
The proof decomposes (n + 1)^2 into (n - 1)^2 + 4n by lifting the computation to the integers to use polynomial ring arithmetic. Applying the division identity (x + 4y) / 4 = x / 4 + y in ℕ allows extracting n from the fraction. Subtracting 2 on both sides then yields the desired equality.
(n + 1)^2 = (n - 1)^2 + n * 4 in ℕ
Linear arithmetic (`omega`) deduces 1 ≤ n from the hypothesis 4 ≤ n. This ensures that the natural subtraction n - 1 casts faithfully to the integer difference n - 1 (`Nat.cast_sub`). Casting the goal into ℤ using `zify` and substituting this equality reduces the claim to the polynomial identity (n + 1)^2 = (n - 1)^2 + 4n, which holds in any commutative ring (`ring`).
uses
Nat.cast_subhave h_sq : (n + 1)^2 = (n - 1)^2 + n * 4 := by have h1 : 1 ≤ n := by omega have hcast : ((n - 1 : ℕ) : ℤ) = (n : ℤ) - 1 := Nat.cast_sub h1 zify rw [hcast] ring
(n + 1)^2 / 4 = (n - 1)^2 / 4 + n in natural number division
Rewriting (n + 1)^2 as (n - 1)^2 + n * 4 using the previous identity, `Nat.add_mul_div_right` extracts the term n from the division by 4, with 0 < 4 verified by computation (`decide`).
uses
Nat.add_mul_div_righthave h_div : (n + 1)^2 / 4 = (n - 1)^2 / 4 + n := by rw [h_sq] exact Nat.add_mul_div_right ((n - 1)^2) n (by decide)
(n + 1)^2 / 4 - 2 = (n - 1)^2 / 4 + n - 2
Substituting the simplified quotient (n + 1)^2 / 4 into the left-hand side produces the right-hand side, closing the goal.
rw [h_div]
Nat.cast_sub- For natural numbers m ≤ n, the subtraction n - m cast into a ring equals the difference of the individual casts: ↑(n - m) = ↑n - ↑m.
Nat.add_mul_div_right- For natural numbers x, y and positive z, integer division satisfies (x + y * z) / z = x / z + y.
- Natural number subtraction `n - 1` truncates at zero in Lean; the proof casts to the integers (`zify`) to allow using standard commutative ring arithmetic (`ring`).
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.
/-- The arithmetic expression (n + 1)^2 / 4 - 2 splits as (n - 1)^2 / 4 + n - 2 in Nat integer division. -/theorem three_token_k2n_domination_arith_split (n : ℕ) (hn : 4 ≤ n) : (n + 1)^2 / 4 - 2 = (n - 1)^2 / 4 + n - 2 := by have h_sq : (n + 1)^2 = (n - 1)^2 + n * 4 := by have h1 : 1 ≤ n := by omega have hcast : ((n - 1 : ℕ) : ℤ) = (n : ℤ) - 1 := Nat.cast_sub h1 zify rw [hcast] ring have h_div : (n + 1)^2 / 4 = (n - 1)^2 / 4 + n := by rw [h_sq] exact Nat.add_mul_div_right ((n - 1)^2) n (by decide) rw [h_div]