catch_up_sum_icc_id
theoremverified
The sum of numbers in the interval {1, ..., N} equals the N-th triangular number N(N+1)/2.
Statement
theorem catch_up_sum_icc_id (N : ℕ) :
∑ x ∈ Finset.Icc 1 N, x = N * (N + 1) / 2- Source
- step towards the Catch-Up conjecture (Catch-Up: A Game in Which the Lead Alternates (Game & Puzzle Design 1(2), 2015), Sec. 3.1; formal-conjectures CatchUpConjecture.lean) (Catch-Up ladder step)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 2
- catch_up_sum_icc_erase_geIn {1, ..., N} with even triangular sum, removing any element x leaves a sum at least x.
- catch_up_value_icc_ne_draw_of_odd_triangularFor any natural number N such that N(N+1)/2 is odd, catch_up_value (Finset.Icc 1 N) ≠ CatchUpOutcome.draw.
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 catch_up_sum_icc_id_mul_two (N : ℕ) : 2 * ∑ x ∈ Finset.Icc 1 N, x = N * (N + 1) := by induction N with | zero => simp | succ n ih => rw [Finset.sum_Icc_succ_top (by omega)] linarith/-- The sum of numbers in the interval {1, ..., N} equals the N-th triangular number N(N+1)/2. -/theorem catch_up_sum_icc_id (N : ℕ) : ∑ x ∈ Finset.Icc 1 N, x = N * (N + 1) / 2 := by have h := catch_up_sum_icc_id_mul_two N omega