cycle_power_sum_range_double
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
- cycle_power_dyadic_no_island_of_alternating_pairedUniform induction step for the no-island class shape. Let m ≥ 1 and suppose every tight, exactly dyadically covered, fully ordinarily…
- cycle_power_dyadic_class_weight_dilateDuplicating each membership bit of a dyadic class doubles its dyadic class weight, when the original radius is at least two.
- cycle_power_dyadic_class_weight_parity_splitFor any Boolean class b and m >= 1, with D = 2^(m+1): the dyadic class weight of b at exponent m+1, plus [b_0 and b_(D-2)] plus [b_1 and…
- cycle_power_alternating_paired_compression_exact_sumFor a positive distance d and s+d at most h, the original sum over 2s possible witnesses for distance 2d at an odd vertex equals the…
- cycle_power_dyadic_alternating_half_modelHalf models. In a tight, exactly dyadically covered, fully covered integer Boolean class model at exponent m+1 (m ≥ 2) with m+2 active…
- cycle_power_alternating_paired_compression_countAt every odd vertex, when all even-start classes consist exactly of their two endpoints, the original active count is one plus the count…
- cycle_power_dyadic_alternating_half_tightIn a tight, exactly dyadically covered model at exponent m+1 (m >= 1) with alternating bit 1, for every class with bit 1 both its even…
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.
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.
induction n with | zero => simp
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.
| succ n ih => have hn : 2 * (n + 1) = (2 * n + 1) + 1 := by omegaThe 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 ℕ.
uses
sum_range_succrw [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.
- The identity `hn : 2 * (n + 1) = (2 * n + 1) + 1` is a formal requirement for Lean: `sum_range_succ` pattern-matches on `range (m + 1)`, so the bound must be expressed explicitly as a successor to extract terms from the sum. On paper, this index manipulation is typically left implicit.
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.
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