three_token_k2n_domination_arith
For every integer n ≥ 4, (n / 2).choose 2 + (n - n / 2).choose 2 + n - 2 ≤ (n + 1)^2 / 4 - 2.
Statement
theorem three_token_k2n_domination_arith (n : ℕ) (hn : 4 ≤ n) :
(n / 2).choose 2 + (n - n / 2).choose 2 + n - 2 ≤ (n + 1)^2 / 4 - 2- Source
- step towards three_token_k2n_domination_number_le
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- TotalPreorderA total preorder: a preorder where
The proof, explained
The proof establishes that the desired inequality is in fact an exact equality: (n / 2).choose 2 + (n - n / 2).choose 2 + n = (n + 1)^2 / 4 for all n. This equality is verified by case split on the parity of n, using two key identities: (m + 1).choose 2 = m.choose 2 + m (from Pascal's identity) and k.choose 2 + (k + 1).choose 2 = k^2 (proved by induction). Rewriting the main goal with this equality reduces the inequality to a reflexive identity on natural numbers, completing the proof without needing the hypothesis n ≥ 4.
(m + 1).choose 2 = m.choose 2 + m for every natural number m
Specialise Pascal's recurrence (`Nat.choose_succ_succ`) with second parameter 1, giving (m + 1).choose 2 = m.choose 1 + m.choose 2. Rewriting m.choose 1 to m via `Nat.choose_one_right` and commuting the terms completes the proof.
uses
Nat.choose_succ_succ,Nat.choose_one_righthave := Nat.choose_succ_succ m 1 change (m + 1).choose 2 = m.choose 1 + m.choose 2 at this rw [Nat.choose_one_right] at this omega
k.choose 2 + (k + 1).choose 2 = k^2 for every natural number k
By induction on k. The base case k = 0 holds definitionally (0 + 0 = 0). For the inductive step, apply the recurrence `three_token_k2n_domination_arith_choose_two_succ` to rewrite (k + 2).choose 2 as (k + 1).choose 2 + (k + 1) and (k + 1).choose 2 as k.choose 2 + k; combining these expansions with the induction hypothesis via nonlinear arithmetic yields (k + 1)^2.
uses
three_token_k2n_domination_arith_choose_two_succinduction k with | zero => rfl | succ k ih => rw [three_token_k2n_domination_arith_choose_two_succ (k + 1)] have h : (k + 1).choose 2 = k.choose 2 + k := three_token_k2n_domination_arith_choose_two_succ k nlinarith
The main identity holds for even integers: (2k / 2).choose 2 + (2k - 2k / 2).choose 2 + 2k = (2k + 1)^2 / 4
Since 2k / 2 = k and 2k - k = k, the left-hand side reduces to 2 * k.choose 2 + 2k. Using the recurrence `three_token_k2n_domination_arith_choose_two_succ` and the square identity `three_token_k2n_domination_arith_choose_two_add_succ`, this simplifies to k^2 + k. On the right-hand side, (2k + 1)^2 = 4(k^2 + k) + 1, so integer division by 4 also yields k^2 + k. Substituting these intermediate values equates both sides.
uses
three_token_k2n_domination_arith_choose_two_succ,three_token_k2n_domination_arith_choose_two_add_succhave h1 : 2 * k / 2 = k := by omega have h2 : 2 * k - k = k := by omega have h3 : k.choose 2 + k.choose 2 + 2 * k = k^2 + k := by have hs := three_token_k2n_domination_arith_choose_two_succ k have ha := three_token_k2n_domination_arith_choose_two_add_succ k omega have h4 : (2 * k + 1)^2 / 4 = k^2 + k := by have hr : (2 * k + 1)^2 = 4 * (k^2 + k) + 1 := by ring rw [hr] omega rw [h1, h2, h3, h4]
The main identity holds for odd integers: ((2k + 1) / 2).choose 2 + ((2k + 1) - (2k + 1) / 2).choose 2 + (2k + 1) = (2k + 2)^2 / 4
By integer division, (2k + 1) / 2 = k and (2k + 1) - k = k + 1. The left-hand side simplifies to k.choose 2 + (k + 1).choose 2 + 2k + 1, which equals k^2 + 2k + 1 = (k + 1)^2 by `three_token_k2n_domination_arith_choose_two_add_succ`. On the right-hand side, (2k + 2)^2 = 4(k + 1)^2, which divides by 4 to give (k + 1)^2. Substituting these evaluations closes the goal.
uses
three_token_k2n_domination_arith_choose_two_add_succhave h1 : (2 * k + 1) / 2 = k := by omega have h2 : (2 * k + 1) - k = k + 1 := by omega have h3 : k.choose 2 + (k + 1).choose 2 + (2 * k + 1) = (k + 1)^2 := by have ha := three_token_k2n_domination_arith_choose_two_add_succ k nlinarith have h4 : (2 * k + 1 + 1)^2 / 4 = (k + 1)^2 := by have hr : (2 * k + 1 + 1)^2 = 4 * (k + 1)^2 := by ring rw [hr] omega rw [h1, h2, h3, h4]
(n / 2).choose 2 + (n - n / 2).choose 2 + n = (n + 1)^2 / 4 for all n ∈ ℕ
Split into cases depending on n % 2 via `Nat.mod_two_eq_zero_or_one`. When n is even, write n = 2k and apply `three_token_k2n_domination_arith_even`. When n is odd, write n = 2k + 1 and apply `three_token_k2n_domination_arith_odd`.
uses
Nat.mod_two_eq_zero_or_one,three_token_k2n_domination_arith_even,three_token_k2n_domination_arith_oddhave h_eq : (n / 2).choose 2 + (n - n / 2).choose 2 + n = (n + 1)^2 / 4 := by rcases Nat.mod_two_eq_zero_or_one n with hmod | hmod · obtain ⟨k, rfl⟩ : ∃ k, n = 2 * k := ⟨n / 2, by omega⟩ exact three_token_k2n_domination_arith_even k · obtain ⟨k, rfl⟩ : ∃ k, n = 2 * k + 1 := ⟨n / 2, by omega⟩ exact three_token_k2n_domination_arith_odd k
The inequality goal reduces to an identity between equal quantities
Rewriting with the equality established in the previous step replaces the left-hand side with (n + 1)^2 / 4 - 2, leaving identical expressions on both sides of ≤, which Lean closes by reflexivity.
rw [h_eq]
Nat.choose_succ_succ- Pascal's recurrence for binomial coefficients: (n + 1).choose (k + 1) = n.choose k + n.choose (k + 1)
Nat.choose_one_right- Choosing 1 out of n gives n: n.choose 1 = n
three_token_k2n_domination_arith_choose_two_succ- Recurrence for pairs: (m + 1).choose 2 = m.choose 2 + m
three_token_k2n_domination_arith_choose_two_add_succ- The sum of consecutive binomial coefficients with 2 is a perfect square: k.choose 2 + (k + 1).choose 2 = k^2
three_token_k2n_domination_arith_even- The main identity holds when n is an even integer 2k
three_token_k2n_domination_arith_odd- The main identity holds when n is an odd integer 2k + 1
Nat.mod_two_eq_zero_or_one- Every natural number modulo 2 is either 0 or 1
- The theorem is formulated as an inequality (≤), but the proof establishes that both sides are in fact strictly equal before and after subtracting 2.
- All divisions (/ 2 and / 4) in the statement represent Lean's natural number integer division (floor division).
- The assumption hn : 4 ≤ n is unused; the algebraic identity holds for all n ∈ ℕ.
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.
lemma three_token_k2n_domination_arith_choose_two_succ (m : ℕ) : (m + 1).choose 2 = m.choose 2 + m := by have := Nat.choose_succ_succ m 1 change (m + 1).choose 2 = m.choose 1 + m.choose 2 at this rw [Nat.choose_one_right] at this omegalemma three_token_k2n_domination_arith_choose_two_add_succ (k : ℕ) : k.choose 2 + (k + 1).choose 2 = k^2 := by induction k with | zero => rfl | succ k ih => rw [three_token_k2n_domination_arith_choose_two_succ (k + 1)] have h : (k + 1).choose 2 = k.choose 2 + k := three_token_k2n_domination_arith_choose_two_succ k nlinarithlemma three_token_k2n_domination_arith_even (k : ℕ) : (2 * k / 2).choose 2 + (2 * k - 2 * k / 2).choose 2 + 2 * k = (2 * k + 1)^2 / 4 := by have h1 : 2 * k / 2 = k := by omega have h2 : 2 * k - k = k := by omega have h3 : k.choose 2 + k.choose 2 + 2 * k = k^2 + k := by have hs := three_token_k2n_domination_arith_choose_two_succ k have ha := three_token_k2n_domination_arith_choose_two_add_succ k omega have h4 : (2 * k + 1)^2 / 4 = k^2 + k := by have hr : (2 * k + 1)^2 = 4 * (k^2 + k) + 1 := by ring rw [hr] omega rw [h1, h2, h3, h4]lemma three_token_k2n_domination_arith_odd (k : ℕ) : ((2 * k + 1) / 2).choose 2 + ((2 * k + 1) - (2 * k + 1) / 2).choose 2 + (2 * k + 1) = (2 * k + 1 + 1)^2 / 4 := by have h1 : (2 * k + 1) / 2 = k := by omega have h2 : (2 * k + 1) - k = k + 1 := by omega have h3 : k.choose 2 + (k + 1).choose 2 + (2 * k + 1) = (k + 1)^2 := by have ha := three_token_k2n_domination_arith_choose_two_add_succ k nlinarith have h4 : (2 * k + 1 + 1)^2 / 4 = (k + 1)^2 := by have hr : (2 * k + 1 + 1)^2 = 4 * (k + 1)^2 := by ring rw [hr] omega rw [h1, h2, h3, h4]/-- For any natural number n >= 4, the sum (n/2).choose 2 + (n - n/2).choose 2 + n - 2 is at most (n + 1)^2 / 4 - 2 in integer division. -/theorem three_token_k2n_domination_arith (n : ℕ) (hn : 4 ≤ n) : (n / 2).choose 2 + (n - n / 2).choose 2 + n - 2 ≤ (n + 1)^2 / 4 - 2 := by have h_eq : (n / 2).choose 2 + (n - n / 2).choose 2 + n = (n + 1)^2 / 4 := by rcases Nat.mod_two_eq_zero_or_one n with hmod | hmod · obtain ⟨k, rfl⟩ : ∃ k, n = 2 * k := ⟨n / 2, by omega⟩ exact three_token_k2n_domination_arith_even k · obtain ⟨k, rfl⟩ : ∃ k, n = 2 * k + 1 := ⟨n / 2, by omega⟩ exact three_token_k2n_domination_arith_odd k rw [h_eq]