AFTD Auto-Formalizing Theoretical Domains

cycle_power_sum_range_double

theoremverified

A sum over the first 2n indices equals the sum over n consecutive even-odd pairs.

Statement

theorem cycle_power_sum_range_double (n : ℕ) (f : ℕ → ℕ) :
    (range (2 * n)).sum f = (range n).sum (fun i => f (2 * i) + f (2 * i + 1))
Source
Uniform helper for the OP-205 / RT-1 campaign, following arXiv:2610.15635, Section 3. These conditional class-system and pruning lemmas do not establish the unresolved graph covering bound. The earlier fixed-radius helpers handle radii eight and sixteen; this session works with arbitrary dyadic radii. No research advance is claimed.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 7

The proof, explained

The proof proceeds by induction on n. The base case n = 0 is trivial as both sums are over empty ranges. For the inductive step, the upper bound 2(n + 1) is rewritten as (2n + 1) + 1, allowing the last two terms to be peeled off with `sum_range_succ`; substituting the induction hypothesis then reduces both sides to the same sum of pairs, up to associativity of addition.

  1. The base case holds: when n = 0, both sums are over the empty range and evaluate to 0.

    When n = 0, 2 * 0 = 0, so both the left-hand sum and the right-hand sum are over `Finset.range 0`. The sum over an empty set is 0 by definition, which `simp` confirms.

    lines 5–6

      induction n with
      | zero => simp
  2. 2 * (n + 1) = (2 * n + 1) + 1.

    In the successor case, we establish by linear arithmetic (`omega`) that 2 * (n + 1) = (2 * n + 1) + 1. This arithmetic decomposition into successor form is needed so that `sum_range_succ` can peel off the boundary terms one by one.

    lines 7–8

      | succ n ih =>
        have hn : 2 * (n + 1) = (2 * n + 1) + 1 := by omega
  3. The inductive step holds: the sum over the first 2(n + 1) indices equals the sum of the first n + 1 pairs.

    Rewriting the upper bound using `hn`, two applications of `sum_range_succ` peel off f (2 * n + 1) and f (2 * n) from the left-hand sum. Rewriting with the induction hypothesis `ih` replaces the remaining sum over 2n elements with the sum of the first n pairs. A final application of `sum_range_succ` to the right-hand sum peels off its last pair, f (2 * n) + f (2 * n + 1). Both sides now consist of the sum over n pairs plus f (2 * n) + f (2 * n + 1), and `omega` closes the goal by associativity and commutativity of addition in ℕ.

    lines 9–10

    uses sum_range_succ

        rw [hn, sum_range_succ, sum_range_succ, ih, sum_range_succ]
        omega
sum_range_succ
The sum of a function over the range {0, ..., n} equals the sum over {0, ..., n - 1} plus the term at index n: ∑ x ∈ range (n + 1), f x = (∑ x ∈ range n, f x) + f 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

open Finsettheorem cycle_power_sum_range_double (n : ℕ) (f : ℕ → ℕ) :    (range (2 * n)).sum f = (range n).sum (fun i => f (2 * i) + f (2 * i + 1)) := by  induction n with  | zero => simp  | succ n ih =>    have hn : 2 * (n + 1) = (2 * n + 1) + 1 := by omega    rw [hn, sum_range_succ, sum_range_succ, ih, sum_range_succ]    omega
See it in the graphDiscuss this resultChallenge it