AFTD Auto-Formalizing Theoretical Domains

finset_sum_eq_three_of_off

theoremverified

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.

  1. 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}.

    lines 6–7

    uses Finset.subset_univ, Finset.sum_subset

      have hs : ({a, b, c} : Finset ι) ⊆ Finset.univ := Finset.subset_univ _
      rw [← Finset.sum_subset hs]
  2. ∑ 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.

    lines 8–12

    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]
  3. 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.

    lines 13–15

    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

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