finset_sum_eq_three_of_off
A finite sum of an ℕ-valued function that vanishes off three distinct points equals the sum of the three values f a + f b + f c.
Statement
theorem finset_sum_eq_three_of_off {ι : Type*} [Fintype ι] [DecidableEq ι] (f : ι → ℕ) {a b c : ι} (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) (h : ∀ x, x ≠ a → x ≠ b → x ≠ c → f x = 0) : ∑ x, f x = f a + f b + f c
- Source
- step towards pell_prefix_block_step
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- pell_prefix_first_letter_vectorAfter appending only the letter c_(i+1) to the prefix, the run counts are P(i+1)-P(i) at q_i, 2P(i) at q_(i+1), (P(i+1)-P(i))+2P(i) at…
The proof, explained
The proof restricts the sum over all elements of the type to the three-element set {a, b, c} using Finset.sum_subset, which requires showing that f vanishes on all other elements. Because a, b, and c are pairwise distinct, the sum over {a, b, c} expands into f a + f b + f c term by term. Finally, any element outside {a, b, c} differs from all three points, so f vanishes on it by assumption.
The total sum ∑ x, f x reduces to the sum over {a, b, c}, provided f vanishes on every element outside {a, b, c}.
Since {a, b, c} is trivially a subset of the universal finset (by Finset.subset_univ), Finset.sum_subset reduces the sum over the entire type to the sum over {a, b, c}. This leaves two obligations: evaluating the restricted sum, and showing f vanishes outside {a, b, c}.
uses
Finset.subset_univ,Finset.sum_subsethave hs : ({a, b, c} : Finset ι) ⊆ Finset.univ := Finset.subset_univ _ rw [← Finset.sum_subset hs]
∑ x ∈ {a, b, c}, f x = f a + f b + f c
We expand the sum over {a, b, c} = insert a (insert b {c}). Since a ≠ b and a ≠ c, a ∉ {b, c}, so Finset.sum_insert peels off f a. Next, since b ≠ c, b ∉ {c}, so a second application of Finset.sum_insert peels off f b. Finally, the sum over the singleton {c} evaluates to f c by Finset.sum_singleton, and reassociating addition with add_assoc completes the calculation.
uses
Finset.sum_insert,Finset.sum_singleton,add_assoc· rw [Finset.sum_insert] · rw [Finset.sum_insert] · rw [Finset.sum_singleton, add_assoc] · simp [hbc] · simp [hab, hac]
For every element x ∉ {a, b, c}, f x = 0.
Let x be an element outside {a, b, c}. Rewriting the non-membership condition using Finset.mem_insert, Finset.mem_singleton, and not_or unpacks x ∉ {a, b, c} into x ≠ a ∧ x ≠ b ∧ x ≠ c. The hypothesis h then directly yields f x = 0.
uses
Finset.mem_insert,Finset.mem_singleton,not_or· intro x _ hx simp only [Finset.mem_insert, Finset.mem_singleton, not_or] at hx exact h x hx.1 hx.2.1 hx.2.2
Finset.subset_univ- Every finite set in a finite type is a subset of the universal set Finset.univ.
Finset.sum_subset- If s₁ ⊆ s₂ and f vanishes on s₂ \ s₁, then the sum of f over s₁ equals the sum of f over s₂.
Finset.sum_insert- If a ∉ s, then the sum of f over {a} ∪ s equals f(a) plus the sum of f over s.
Finset.sum_singleton- The sum of f over a singleton {a} is f(a).
add_assoc- Addition is associative: (a + b) + c = a + (b + c).
Finset.mem_insert- An element x belongs to {a} ∪ s if and only if x = a or x ∈ s.
Finset.mem_singleton- An element x belongs to {a} if and only if x = a.
not_or- De Morgan's law for disjunction: ¬(p ∨ q) ↔ ¬p ∧ ¬q.
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.
/-- If `f : ι → ℕ` vanishes off `{a,b,c}` (distinct), then `∑ x, f x = f a + f b + f c`. -/theorem finset_sum_eq_three_of_off {ι : Type*} [Fintype ι] [DecidableEq ι] (f : ι → ℕ) {a b c : ι} (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) (h : ∀ x, x ≠ a → x ≠ b → x ≠ c → f x = 0) : ∑ x, f x = f a + f b + f c := by have hs : ({a, b, c} : Finset ι) ⊆ Finset.univ := Finset.subset_univ _ rw [← Finset.sum_subset hs] · rw [Finset.sum_insert] · rw [Finset.sum_insert] · rw [Finset.sum_singleton, add_assoc] · simp [hbc] · simp [hab, hac] · intro x _ hx simp only [Finset.mem_insert, Finset.mem_singleton, not_or] at hx exact h x hx.1 hx.2.1 hx.2.2