AFTD Auto-Formalizing Theoretical Domains

three_token_k2n_domination_arith

theoremverified

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.

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.

  1. (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.

    lines 3–6

    uses Nat.choose_succ_succ, Nat.choose_one_right

      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
      omega
  2. 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.

    lines 10–16

    uses three_token_k2n_domination_arith_choose_two_succ

      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
        nlinarith
  3. 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.

    lines 20–30

    uses three_token_k2n_domination_arith_choose_two_succ, three_token_k2n_domination_arith_choose_two_add_succ

      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]
  4. 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.

    lines 35–44

    uses three_token_k2n_domination_arith_choose_two_add_succ

      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]
  5. (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`.

    lines 49–54

    uses Nat.mod_two_eq_zero_or_one, three_token_k2n_domination_arith_even, three_token_k2n_domination_arith_odd

      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
  6. 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.

    line 55

      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

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

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]
See it in the graphDiscuss this resultChallenge it