AFTD Auto-Formalizing Theoretical Domains

three_token_k2n_domination_arith_split

theoremverified

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

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.

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

    lines 4–9

    uses Nat.cast_sub

      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
  2. (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`).

    lines 10–12

    uses Nat.add_mul_div_right

      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)
  3. (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.

    line 13

      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.

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

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