Sums and products from lists

This file provides basic results about List.prod, List.sum, which calculate the product and sum of elements of a list and List.alternatingProd, List.alternatingSum, their alternating counterparts.

def List.sum {α : Type u_11} [Add α] [Zero α] : List α → α

Sum of a list.

List.sum [a, b, c] = ((0 + a) + b) + c

Equations

• List.sum = List.foldl (fun (x x_1 : α) => x + x_1) 0

def List.prod {α : Type u_11} [Mul α] [One α] : List α → α

Product of a list.

List.prod [a, b, c] = ((1 * a) * b) * c

Equations

• List.prod = List.foldl (fun (x x_1 : α) => x * x_1) 1

def List.alternatingSum {G : Type u_11} [Zero G] [Add G] [Neg G] : List G → G

The alternating sum of a list.

Equations

• List.alternatingSum [] = 0
• List.alternatingSum [g] = g
• List.alternatingSum (g :: h :: t) = g + -h + List.alternatingSum t

def List.alternatingProd {G : Type u_11} [One G] [Mul G] [Inv G] : List G → G

The alternating product of a list.

Equations

• List.alternatingProd [] = 1
• List.alternatingProd [g] = g
• List.alternatingProd (g :: h :: t) = g * h⁻¹ * List.alternatingProd t

@[simp]

theorem List.sum_nil {M : Type u_5} [AddZeroClass M] : List.sum [] = 0

@[simp]

theorem List.prod_nil {M : Type u_5} [MulOneClass M] : List.prod [] = 1

theorem List.sum_singleton {M : Type u_5} [AddZeroClass M] {a : M} : List.sum [a] = a

theorem List.prod_singleton {M : Type u_5} [MulOneClass M] {a : M} : List.prod [a] = a

@[simp]

theorem List.sum_zero_cons {M : Type u_5} [AddZeroClass M] {l : List M} : List.sum (0 :: l) = List.sum l

@[simp]

theorem List.prod_one_cons {M : Type u_5} [MulOneClass M] {l : List M} : List.prod (1 :: l) = List.prod l

theorem List.sum_map_zero {ι : Type u_1} {M : Type u_5} [AddZeroClass M] {l : List ι} : List.sum (List.map (fun (x : ι) => 0) l) = 0

theorem List.prod_map_one {ι : Type u_1} {M : Type u_5} [MulOneClass M] {l : List ι} : List.prod (List.map (fun (x : ι) => 1) l) = 1

@[simp]

theorem List.sum_cons {M : Type u_5} [AddMonoid M] {l : List M} {a : M} : List.sum (a :: l) = a + List.sum l

@[simp]

theorem List.prod_cons {M : Type u_5} [Monoid M] {l : List M} {a : M} : List.prod (a :: l) = a * List.prod l

theorem List.sum_induction {M : Type u_5} [AddMonoid M] {l : List M} (p : M → Prop) (hom : ∀ (a b : M), p a → p b → p (a + b)) (unit : p 0) (base : ∀ x ∈ l, p x) : p (List.sum l)

theorem List.prod_induction {M : Type u_5} [Monoid M] {l : List M} (p : M → Prop) (hom : ∀ (a b : M), p a → p b → p (a * b)) (unit : p 1) (base : ∀ x ∈ l, p x) : p (List.prod l)

@[simp]

theorem List.sum_append {M : Type u_5} [AddMonoid M] {l₁ : List M} {l₂ : List M} : List.sum (l₁ ++ l₂) = List.sum l₁ + List.sum l₂

@[simp]

theorem List.prod_append {M : Type u_5} [Monoid M] {l₁ : List M} {l₂ : List M} : List.prod (l₁ ++ l₂) = List.prod l₁ * List.prod l₂

theorem List.sum_concat {M : Type u_5} [AddMonoid M] {l : List M} {a : M} : List.sum (List.concat l a) = List.sum l + a

theorem List.prod_concat {M : Type u_5} [Monoid M] {l : List M} {a : M} : List.prod (List.concat l a) = List.prod l * a

@[simp]

theorem List.sum_join {M : Type u_5} [AddMonoid M] {l : List (List M)} : List.sum (List.join l) = List.sum (List.map List.sum l)

@[simp]

theorem List.prod_join {M : Type u_5} [Monoid M] {l : List (List M)} : List.prod (List.join l) = List.prod (List.map List.prod l)

theorem List.sum_eq_foldr {M : Type u_5} [AddMonoid M] {l : List M} : List.sum l = List.foldr (fun (x x_1 : M) => x + x_1) 0 l

abbrev List.sum_eq_foldr.match_1 {M : Type u_1} (motive : List M → Prop) : ∀ (x : List M), (Unit → motive []) → (∀ (a : M) (l : List M), motive (a :: l)) → motive x

Equations

• ⋯ = ⋯

theorem List.prod_eq_foldr {M : Type u_5} [Monoid M] {l : List M} : List.prod l = List.foldr (fun (x x_1 : M) => x * x_1) 1 l

@[simp]

theorem List.sum_replicate {M : Type u_5} [AddMonoid M] (n : ℕ) (a : M) : List.sum (List.replicate n a) = n • a

@[simp]

theorem List.prod_replicate {M : Type u_5} [Monoid M] (n : ℕ) (a : M) : List.prod (List.replicate n a) = a ^ n

theorem List.sum_eq_card_nsmul {M : Type u_5} [AddMonoid M] (l : List M) (m : M) (h : ∀ x ∈ l, x = m) : List.sum l = List.length l • m

theorem List.prod_eq_pow_card {M : Type u_5} [Monoid M] (l : List M) (m : M) (h : ∀ x ∈ l, x = m) : List.prod l = m ^ List.length l

theorem List.sum_hom_rel {ι : Type u_1} {M : Type u_5} {N : Type u_6} [AddMonoid M] [AddMonoid N] (l : List ι) {r : M → N → Prop} {f : ι → M} {g : ι → N} (h₁ : r 0 0) (h₂ : ∀ ⦃i : ι⦄ ⦃a : M⦄ ⦃b : N⦄, r a b → r (f i + a) (g i + b)) : r (List.sum (List.map f l)) (List.sum (List.map g l))

theorem List.prod_hom_rel {ι : Type u_1} {M : Type u_5} {N : Type u_6} [Monoid M] [Monoid N] (l : List ι) {r : M → N → Prop} {f : ι → M} {g : ι → N} (h₁ : r 1 1) (h₂ : ∀ ⦃i : ι⦄ ⦃a : M⦄ ⦃b : N⦄, r a b → r (f i * a) (g i * b)) : r (List.prod (List.map f l)) (List.prod (List.map g l))

theorem List.rel_sum {M : Type u_5} {N : Type u_6} [AddMonoid M] [AddMonoid N] {R : M → N → Prop} (h : R 0 0) (hf : (R ⇒ R ⇒ R) (fun (x x_1 : M) => x + x_1) fun (x x_1 : N) => x + x_1) : (List.Forall₂ R ⇒ R) List.sum List.sum

theorem List.rel_prod {M : Type u_5} {N : Type u_6} [Monoid M] [Monoid N] {R : M → N → Prop} (h : R 1 1) (hf : (R ⇒ R ⇒ R) (fun (x x_1 : M) => x * x_1) fun (x x_1 : N) => x * x_1) : (List.Forall₂ R ⇒ R) List.prod List.prod

theorem List.sum_hom {M : Type u_5} {N : Type u_6} [AddMonoid M] [AddMonoid N] (l : List M) {F : Type u_11} [FunLike F M N] [AddMonoidHomClass F M N] (f : F) : List.sum (List.map (⇑f) l) = f (List.sum l)

theorem List.prod_hom {M : Type u_5} {N : Type u_6} [Monoid M] [Monoid N] (l : List M) {F : Type u_11} [FunLike F M N] [MonoidHomClass F M N] (f : F) : List.prod (List.map (⇑f) l) = f (List.prod l)

theorem List.sum_hom₂ {ι : Type u_1} {M : Type u_5} {N : Type u_6} {P : Type u_7} [AddMonoid M] [AddMonoid N] [AddMonoid P] (l : List ι) (f : M → N → P) (hf : ∀ (a b : M) (c d : N), f (a + b) (c + d) = f a c + f b d) (hf' : f 0 0 = 0) (f₁ : ι → M) (f₂ : ι → N) : List.sum (List.map (fun (i : ι) => f (f₁ i) (f₂ i)) l) = f (List.sum (List.map f₁ l)) (List.sum (List.map f₂ l))

theorem List.prod_hom₂ {ι : Type u_1} {M : Type u_5} {N : Type u_6} {P : Type u_7} [Monoid M] [Monoid N] [Monoid P] (l : List ι) (f : M → N → P) (hf : ∀ (a b : M) (c d : N), f (a * b) (c * d) = f a c * f b d) (hf' : f 1 1 = 1) (f₁ : ι → M) (f₂ : ι → N) : List.prod (List.map (fun (i : ι) => f (f₁ i) (f₂ i)) l) = f (List.prod (List.map f₁ l)) (List.prod (List.map f₂ l))

@[simp]

theorem List.sum_map_add {ι : Type u_1} {α : Type u_11} [AddCommMonoid α] {l : List ι} {f : ι → α} {g : ι → α} : List.sum (List.map (fun (i : ι) => f i + g i) l) = List.sum (List.map f l) + List.sum (List.map g l)

@[simp]

theorem List.prod_map_mul {ι : Type u_1} {α : Type u_11} [CommMonoid α] {l : List ι} {f : ι → α} {g : ι → α} : List.prod (List.map (fun (i : ι) => f i * g i) l) = List.prod (List.map f l) * List.prod (List.map g l)

@[simp]

theorem List.prod_map_neg {M : Type u_5} [Monoid M] [HasDistribNeg M] (l : List M) : List.prod (List.map Neg.neg l) = (-1) ^ List.length l * List.prod l

theorem List.sum_map_hom {ι : Type u_1} {M : Type u_5} {N : Type u_6} [AddMonoid M] [AddMonoid N] (L : List ι) (f : ι → M) {G : Type u_11} [FunLike G M N] [AddMonoidHomClass G M N] (g : G) : List.sum (List.map (⇑g ∘ f) L) = g (List.sum (List.map f L))

theorem List.prod_map_hom {ι : Type u_1} {M : Type u_5} {N : Type u_6} [Monoid M] [Monoid N] (L : List ι) (f : ι → M) {G : Type u_11} [FunLike G M N] [MonoidHomClass G M N] (g : G) : List.prod (List.map (⇑g ∘ f) L) = g (List.prod (List.map f L))

theorem List.sum_isAddUnit {M : Type u_5} [AddMonoid M] {L : List M} : (∀ m ∈ L, IsAddUnit m) → IsAddUnit (List.sum L)

abbrev List.sum_isAddUnit.match_1 {M : Type u_1} [AddMonoid M] (motive : (x : List M) → (∀ m ∈ x, IsAddUnit m) → Prop) : ∀ (x : List M) (x_1 : ∀ m ∈ x, IsAddUnit m), (∀ (x : ∀ m ∈ [], IsAddUnit m), motive [] x) → (∀ (h : M) (t : List M) (u : ∀ m ∈ h :: t, IsAddUnit m), motive (h :: t) u) → motive x x_1

Equations

• ⋯ = ⋯

theorem List.prod_isUnit {M : Type u_5} [Monoid M] {L : List M} : (∀ m ∈ L, IsUnit m) → IsUnit (List.prod L)

theorem List.sum_isAddUnit_iff {α : Type u_11} [AddCommMonoid α] {L : List α} : IsAddUnit (List.sum L) ↔ ∀ m ∈ L, IsAddUnit m

theorem List.prod_isUnit_iff {α : Type u_11} [CommMonoid α] {L : List α} : IsUnit (List.prod L) ↔ ∀ m ∈ L, IsUnit m

abbrev List.sum_take_add_sum_drop.match_1 {M : Type u_1} (motive : List M → ℕ → Prop) : ∀ (x : List M) (x_1 : ℕ), (∀ (i : ℕ), motive [] i) → (∀ (L : List M), motive L 0) → (∀ (h : M) (t : List M) (n : ℕ), motive (h :: t) (Nat.succ n)) → motive x x_1

Equations

• ⋯ = ⋯

@[simp]

theorem List.sum_take_add_sum_drop {M : Type u_5} [AddMonoid M] (L : List M) (i : ℕ) : List.sum (List.take i L) + List.sum (List.drop i L) = List.sum L

@[simp]

theorem List.prod_take_mul_prod_drop {M : Type u_5} [Monoid M] (L : List M) (i : ℕ) : List.prod (List.take i L) * List.prod (List.drop i L) = List.prod L

@[simp]

theorem List.sum_take_succ {M : Type u_5} [AddMonoid M] (L : List M) (i : ℕ) (p : i < List.length L) : List.sum (List.take (i + 1) L) = List.sum (List.take i L) + List.get L { val := i, isLt := p }

abbrev List.sum_take_succ.match_1 {M : Type u_1} (motive : (x : List M) → (x_1 : ℕ) → x_1 < List.length x → Prop) : ∀ (x : List M) (x_1 : ℕ) (x_2 : x_1 < List.length x), (∀ (i : ℕ) (p : i < List.length []), motive [] i p) → (∀ (h : M) (t : List M) (x : 0 < List.length (h :: t)), motive (h :: t) 0 x) → (∀ (h : M) (t : List M) (n : ℕ) (p : n + 1 < List.length (h :: t)), motive (h :: t) (Nat.succ n) p) → motive x x_1 x_2

Equations

• ⋯ = ⋯

@[simp]

theorem List.prod_take_succ {M : Type u_5} [Monoid M] (L : List M) (i : ℕ) (p : i < List.length L) : List.prod (List.take (i + 1) L) = List.prod (List.take i L) * List.get L { val := i, isLt := p }

theorem List.length_pos_of_sum_ne_zero {M : Type u_5} [AddMonoid M] (L : List M) (h : List.sum L ≠ 0) : 0 < List.length L

A list with sum not zero must have positive length.

theorem List.length_pos_of_prod_ne_one {M : Type u_5} [Monoid M] (L : List M) (h : List.prod L ≠ 1) : 0 < List.length L

A list with product not one must have positive length.

theorem List.length_pos_of_sum_pos {M : Type u_5} [AddMonoid M] [Preorder M] (L : List M) (h : 0 < List.sum L) : 0 < List.length L

A list with positive sum must have positive length.

theorem List.length_pos_of_one_lt_prod {M : Type u_5} [Monoid M] [Preorder M] (L : List M) (h : 1 < List.prod L) : 0 < List.length L

A list with product greater than one must have positive length.

theorem List.length_pos_of_sum_neg {M : Type u_5} [AddMonoid M] [Preorder M] (L : List M) (h : List.sum L < 0) : 0 < List.length L

A list with negative sum must have positive length.

theorem List.length_pos_of_prod_lt_one {M : Type u_5} [Monoid M] [Preorder M] (L : List M) (h : List.prod L < 1) : 0 < List.length L

A list with product less than one must have positive length.

abbrev List.sum_set.match_1 {M : Type u_1} (motive : List M → ℕ → M → Prop) : ∀ (x : List M) (x_1 : ℕ) (x_2 : M), (∀ (x : M) (xs : List M) (a : M), motive (x :: xs) 0 a) → (∀ (x : M) (xs : List M) (i : ℕ) (a : M), motive (x :: xs) (Nat.succ i) a) → (∀ (x : ℕ) (x_3 : M), motive [] x x_3) → motive x x_1 x_2

Equations

• ⋯ = ⋯

theorem List.sum_set {M : Type u_5} [AddMonoid M] (L : List M) (n : ℕ) (a : M) : List.sum (List.set L n a) = (List.sum (List.take n L) + if n < List.length L then a else 0) + List.sum (List.drop (n + 1) L)

theorem List.prod_set {M : Type u_5} [Monoid M] (L : List M) (n : ℕ) (a : M) : List.prod (List.set L n a) = (List.prod (List.take n L) * if n < List.length L then a else 1) * List.prod (List.drop (n + 1) L)

theorem List.get?_zero_add_tail_sum {M : Type u_5} [AddMonoid M] (l : List M) : Option.getD (List.get? l 0) 0 + List.sum (List.tail l) = List.sum l

We'd like to state this as L.headI + L.tail.sum = L.sum, but because L.headI relies on an inhabited instance to return a garbage value on the empty list, this is not possible. Instead, we write the statement in terms of (L.get? 0).getD 0.

theorem List.get?_zero_mul_tail_prod {M : Type u_5} [Monoid M] (l : List M) : Option.getD (List.get? l 0) 1 * List.prod (List.tail l) = List.prod l

We'd like to state this as L.headI * L.tail.prod = L.prod, but because L.headI relies on an inhabited instance to return a garbage value on the empty list, this is not possible. Instead, we write the statement in terms of (L.get? 0).getD 1.

theorem List.headI_add_tail_sum_of_ne_nil {M : Type u_5} [AddMonoid M] [Inhabited M] (l : List M) (h : l ≠ []) : List.headI l + List.sum (List.tail l) = List.sum l

Same as get?_zero_add_tail_sum, but avoiding the List.headI garbage complication by requiring the list to be nonempty.

theorem List.headI_mul_tail_prod_of_ne_nil {M : Type u_5} [Monoid M] [Inhabited M] (l : List M) (h : l ≠ []) : List.headI l * List.prod (List.tail l) = List.prod l

Same as get?_zero_mul_tail_prod, but avoiding the List.headI garbage complication by requiring the list to be nonempty.

theorem AddCommute.list_sum_right {M : Type u_5} [AddMonoid M] (l : List M) (y : M) (h : ∀ x ∈ l, AddCommute y x) : AddCommute y (List.sum l)

theorem Commute.list_prod_right {M : Type u_5} [Monoid M] (l : List M) (y : M) (h : ∀ x ∈ l, Commute y x) : Commute y (List.prod l)

theorem AddCommute.list_sum_left {M : Type u_5} [AddMonoid M] (l : List M) (y : M) (h : ∀ x ∈ l, AddCommute x y) : AddCommute (List.sum l) y

theorem Commute.list_prod_left {M : Type u_5} [Monoid M] (l : List M) (y : M) (h : ∀ x ∈ l, Commute x y) : Commute (List.prod l) y

theorem List.sum_range_succ {M : Type u_5} [AddMonoid M] (f : ℕ → M) (n : ℕ) : List.sum (List.map f (List.range (Nat.succ n))) = List.sum (List.map f (List.range n)) + f n

theorem List.prod_range_succ {M : Type u_5} [Monoid M] (f : ℕ → M) (n : ℕ) : List.prod (List.map f (List.range (Nat.succ n))) = List.prod (List.map f (List.range n)) * f n

theorem List.sum_range_succ' {M : Type u_5} [AddMonoid M] (f : ℕ → M) (n : ℕ) : List.sum (List.map f (List.range (Nat.succ n))) = f 0 + List.sum (List.map (fun (i : ℕ) => f (Nat.succ i)) (List.range n))

A variant of sum_range_succ which pulls off the first term in the sum rather than the last.

theorem List.prod_range_succ' {M : Type u_5} [Monoid M] (f : ℕ → M) (n : ℕ) : List.prod (List.map f (List.range (Nat.succ n))) = f 0 * List.prod (List.map (fun (i : ℕ) => f (Nat.succ i)) (List.range n))

A variant of prod_range_succ which pulls off the first term in the product rather than the last.

theorem List.sum_eq_zero {M : Type u_5} [AddMonoid M] {l : List M} (hl : ∀ x ∈ l, x = 0) : List.sum l = 0

theorem List.prod_eq_one {M : Type u_5} [Monoid M] {l : List M} (hl : ∀ x ∈ l, x = 1) : List.prod l = 1

theorem List.exists_mem_ne_zero_of_sum_ne_zero {M : Type u_5} [AddMonoid M] {l : List M} (h : List.sum l ≠ 0) : ∃ x ∈ l, x ≠ 0

theorem List.exists_mem_ne_one_of_prod_ne_one {M : Type u_5} [Monoid M] {l : List M} (h : List.prod l ≠ 1) : ∃ x ∈ l, x ≠ 1

theorem List.sum_erase_of_comm {M : Type u_5} [AddMonoid M] {l : List M} {a : M} [DecidableEq M] (ha : a ∈ l) (comm : ∀ x ∈ l, ∀ y ∈ l, x + y = y + x) : a + List.sum (List.erase l a) = List.sum l

theorem List.prod_erase_of_comm {M : Type u_5} [Monoid M] {l : List M} {a : M} [DecidableEq M] (ha : a ∈ l) (comm : ∀ x ∈ l, ∀ y ∈ l, x * y = y * x) : a * List.prod (List.erase l a) = List.prod l

theorem List.sum_map_eq_nsmul_single {α : Type u_2} {M : Type u_5} [AddMonoid M] [DecidableEq α] {l : List α} (a : α) (f : α → M) (hf : ∀ (a' : α), a' ≠ a → a' ∈ l → f a' = 0) : List.sum (List.map f l) = List.count a l • f a

theorem List.prod_map_eq_pow_single {α : Type u_2} {M : Type u_5} [Monoid M] [DecidableEq α] {l : List α} (a : α) (f : α → M) (hf : ∀ (a' : α), a' ≠ a → a' ∈ l → f a' = 1) : List.prod (List.map f l) = f a ^ List.count a l

theorem List.sum_eq_nsmul_single {M : Type u_5} [AddMonoid M] {l : List M} [DecidableEq M] (a : M) (h : ∀ (a' : M), a' ≠ a → a' ∈ l → a' = 0) : List.sum l = List.count a l • a

theorem List.prod_eq_pow_single {M : Type u_5} [Monoid M] {l : List M} [DecidableEq M] (a : M) (h : ∀ (a' : M), a' ≠ a → a' ∈ l → a' = 1) : List.prod l = a ^ List.count a l

theorem List.Perm.sum_eq' {M : Type u_5} [AddMonoid M] {l₁ : List M} {l₂ : List M} (h : List.Perm l₁ l₂) (hc : List.Pairwise AddCommute l₁) : List.sum l₁ = List.sum l₂

If elements of a list additively commute with each other, then their sum does not depend on the order of elements.

theorem List.Perm.prod_eq' {M : Type u_5} [Monoid M] {l₁ : List M} {l₂ : List M} (h : List.Perm l₁ l₂) (hc : List.Pairwise Commute l₁) : List.prod l₁ = List.prod l₂

If elements of a list commute with each other, then their product does not depend on the order of elements.

@[simp]

theorem List.sum_erase {M : Type u_5} [AddCommMonoid M] {a : M} {l : List M} [DecidableEq M] (ha : a ∈ l) : a + List.sum (List.erase l a) = List.sum l

@[simp]

theorem List.prod_erase {M : Type u_5} [CommMonoid M] {a : M} {l : List M} [DecidableEq M] (ha : a ∈ l) : a * List.prod (List.erase l a) = List.prod l

abbrev List.sum_map_erase.match_1 {α : Type u_1} {a : α} (motive : (x : List α) → a ∈ x → Prop) : ∀ (x : List α) (x_1 : a ∈ x), (∀ (b : α) (l : List α) (h : a ∈ b :: l), motive (b :: l) h) → motive x x_1

Equations

• ⋯ = ⋯

@[simp]

theorem List.sum_map_erase {α : Type u_2} {M : Type u_5} [AddCommMonoid M] [DecidableEq α] (f : α → M) {a : α} {l : List α} : a ∈ l → f a + List.sum (List.map f (List.erase l a)) = List.sum (List.map f l)

@[simp]

theorem List.prod_map_erase {α : Type u_2} {M : Type u_5} [CommMonoid M] [DecidableEq α] (f : α → M) {a : α} {l : List α} : a ∈ l → f a * List.prod (List.map f (List.erase l a)) = List.prod (List.map f l)

theorem List.Perm.sum_eq {M : Type u_5} [AddCommMonoid M] {l₁ : List M} {l₂ : List M} (h : List.Perm l₁ l₂) : List.sum l₁ = List.sum l₂

theorem List.Perm.prod_eq {M : Type u_5} [CommMonoid M] {l₁ : List M} {l₂ : List M} (h : List.Perm l₁ l₂) : List.prod l₁ = List.prod l₂

theorem List.sum_reverse {M : Type u_5} [AddCommMonoid M] (l : List M) : List.sum (List.reverse l) = List.sum l

theorem List.prod_reverse {M : Type u_5} [CommMonoid M] (l : List M) : List.prod (List.reverse l) = List.prod l

abbrev List.sum_add_sum_eq_sum_zipWith_add_sum_drop.match_1 {M : Type u_1} (motive : List M → List M → Prop) : ∀ (x x_1 : List M), (∀ (ys : List M), motive [] ys) → (∀ (xs : List M), motive xs []) → (∀ (x : M) (xs : List M) (y : M) (ys : List M), motive (x :: xs) (y :: ys)) → motive x x_1

Equations

• ⋯ = ⋯

theorem List.sum_add_sum_eq_sum_zipWith_add_sum_drop {M : Type u_5} [AddCommMonoid M] (l : List M) (l' : List M) : List.sum l + List.sum l' = List.sum (List.zipWith (fun (x x_1 : M) => x + x_1) l l') + List.sum (List.drop (List.length l') l) + List.sum (List.drop (List.length l) l')

theorem List.prod_mul_prod_eq_prod_zipWith_mul_prod_drop {M : Type u_5} [CommMonoid M] (l : List M) (l' : List M) : List.prod l * List.prod l' = List.prod (List.zipWith (fun (x x_1 : M) => x * x_1) l l') * List.prod (List.drop (List.length l') l) * List.prod (List.drop (List.length l) l')

theorem List.sum_add_sum_eq_sum_zipWith_of_length_eq {M : Type u_5} [AddCommMonoid M] (l : List M) (l' : List M) (h : List.length l = List.length l') : List.sum l + List.sum l' = List.sum (List.zipWith (fun (x x_1 : M) => x + x_1) l l')

theorem List.prod_mul_prod_eq_prod_zipWith_of_length_eq {M : Type u_5} [CommMonoid M] (l : List M) (l' : List M) (h : List.length l = List.length l') : List.prod l * List.prod l' = List.prod (List.zipWith (fun (x x_1 : M) => x * x_1) l l')

theorem List.eq_of_sum_take_eq {M : Type u_5} [AddLeftCancelMonoid M] {L : List M} {L' : List M} (h : List.length L = List.length L') (h' : ∀ i ≤ List.length L, List.sum (List.take i L) = List.sum (List.take i L')) : L = L'

theorem List.eq_of_prod_take_eq {M : Type u_5} [LeftCancelMonoid M] {L : List M} {L' : List M} (h : List.length L = List.length L') (h' : ∀ i ≤ List.length L, List.prod (List.take i L) = List.prod (List.take i L')) : L = L'

theorem List.sum_neg_reverse {G : Type u_9} [AddGroup G] (L : List G) : -List.sum L = List.sum (List.reverse (List.map (fun (x : G) => -x) L))

This is the List.sum version of add_neg_rev

theorem List.prod_inv_reverse {G : Type u_9} [Group G] (L : List G) : (List.prod L)⁻¹ = List.prod (List.reverse (List.map (fun (x : G) => x⁻¹) L))

This is the List.prod version of mul_inv_rev

theorem List.sum_reverse_noncomm {G : Type u_9} [AddGroup G] (L : List G) : List.sum (List.reverse L) = -List.sum (List.map (fun (x : G) => -x) L)

A non-commutative variant of List.sum_reverse

theorem List.prod_reverse_noncomm {G : Type u_9} [Group G] (L : List G) : List.prod (List.reverse L) = (List.prod (List.map (fun (x : G) => x⁻¹) L))⁻¹

A non-commutative variant of List.prod_reverse

@[simp]

theorem List.sum_drop_succ {G : Type u_9} [AddGroup G] (L : List G) (i : ℕ) (p : i < List.length L) : List.sum (List.drop (i + 1) L) = -List.get L { val := i, isLt := p } + List.sum (List.drop i L)

Counterpart to List.sum_take_succ when we have a negation operation

@[simp]

theorem List.prod_drop_succ {G : Type u_9} [Group G] (L : List G) (i : ℕ) (p : i < List.length L) : List.prod (List.drop (i + 1) L) = (List.get L { val := i, isLt := p })⁻¹ * List.prod (List.drop i L)

Counterpart to List.prod_take_succ when we have an inverse operation

theorem List.sum_range_sub' {G : Type u_9} [AddGroup G] (n : ℕ) (f : ℕ → G) : List.sum (List.map (fun (k : ℕ) => f k - f (k + 1)) (List.range n)) = f 0 - f n

Cancellation of a telescoping sum.

theorem List.prod_range_div' {G : Type u_9} [Group G] (n : ℕ) (f : ℕ → G) : List.prod (List.map (fun (k : ℕ) => f k / f (k + 1)) (List.range n)) = f 0 / f n

Cancellation of a telescoping product.

theorem List.prod_rotate_eq_one_of_prod_eq_one {G : Type u_9} [Group G] {l : List G} : List.prod l = 1 → ∀ (n : ℕ), List.prod (List.rotate l n) = 1

theorem List.sum_neg {G : Type u_9} [AddCommGroup G] (L : List G) : -List.sum L = List.sum (List.map (fun (x : G) => -x) L)

This is the List.sum version of add_neg

theorem List.prod_inv {G : Type u_9} [CommGroup G] (L : List G) : (List.prod L)⁻¹ = List.prod (List.map (fun (x : G) => x⁻¹) L)

This is the List.prod version of mul_inv

theorem List.sum_range_sub {G : Type u_9} [AddCommGroup G] (n : ℕ) (f : ℕ → G) : List.sum (List.map (fun (k : ℕ) => f (k + 1) - f k) (List.range n)) = f n - f 0

Cancellation of a telescoping sum.

theorem List.prod_range_div {G : Type u_9} [CommGroup G] (n : ℕ) (f : ℕ → G) : List.prod (List.map (fun (k : ℕ) => f (k + 1) / f k) (List.range n)) = f n / f 0

Cancellation of a telescoping product.

theorem List.sum_set' {G : Type u_9} [AddCommGroup G] (L : List G) (n : ℕ) (a : G) : List.sum (List.set L n a) = List.sum L + if hn : n < List.length L then -List.get L { val := n, isLt := hn } + a else 0

Alternative version of List.sum_set when the list is over a group

theorem List.prod_set' {G : Type u_9} [CommGroup G] (L : List G) (n : ℕ) (a : G) : List.prod (List.set L n a) = List.prod L * if hn : n < List.length L then (List.get L { val := n, isLt := hn })⁻¹ * a else 1

Alternative version of List.prod_set when the list is over a group

@[simp]

theorem List.sum_zipWith_distrib_left {α : Type u_2} {β : Type u_3} {γ : Type u_4} [Semiring γ] (f : α → β → γ) (n : γ) (l : List α) (l' : List β) : List.sum (List.zipWith (fun (x : α) (y : β) => n * f x y) l l') = n * List.sum (List.zipWith f l l')

theorem List.sum_const_nat (m : ℕ) (n : ℕ) : List.sum (List.replicate m n) = m * n

Several lemmas about sum/head/tail for List ℕ. These are hard to generalize well, as they rely on the fact that default ℕ = 0. If desired, we could add a class stating that default = 0.

theorem List.headI_add_tail_sum (L : List ℕ) : List.headI L + List.sum (List.tail L) = List.sum L

This relies on default ℕ = 0.

theorem List.headI_le_sum (L : List ℕ) : List.headI L ≤ List.sum L

This relies on default ℕ = 0.

theorem List.tail_sum (L : List ℕ) : List.sum (List.tail L) = List.sum L - List.headI L

This relies on default ℕ = 0.

@[simp]

theorem List.alternatingSum_nil {α : Type u_2} [Zero α] [Add α] [Neg α] : List.alternatingSum [] = 0

@[simp]

theorem List.alternatingProd_nil {α : Type u_2} [One α] [Mul α] [Inv α] : List.alternatingProd [] = 1

@[simp]

theorem List.alternatingSum_singleton {α : Type u_2} [Zero α] [Add α] [Neg α] (a : α) : List.alternatingSum [a] = a

@[simp]

theorem List.alternatingProd_singleton {α : Type u_2} [One α] [Mul α] [Inv α] (a : α) : List.alternatingProd [a] = a

theorem List.alternatingSum_cons_cons' {α : Type u_2} [Zero α] [Add α] [Neg α] (a : α) (b : α) (l : List α) : List.alternatingSum (a :: b :: l) = a + -b + List.alternatingSum l

theorem List.alternatingProd_cons_cons' {α : Type u_2} [One α] [Mul α] [Inv α] (a : α) (b : α) (l : List α) : List.alternatingProd (a :: b :: l) = a * b⁻¹ * List.alternatingProd l

theorem List.alternatingSum_cons_cons {α : Type u_2} [SubNegMonoid α] (a : α) (b : α) (l : List α) : List.alternatingSum (a :: b :: l) = a - b + List.alternatingSum l

theorem List.alternatingProd_cons_cons {α : Type u_2} [DivInvMonoid α] (a : α) (b : α) (l : List α) : List.alternatingProd (a :: b :: l) = a / b * List.alternatingProd l

abbrev List.alternatingSum_cons'.match_1 {α : Type u_1} (motive : α → List α → Prop) : ∀ (x : α) (x_1 : List α), (∀ (a : α), motive a []) → (∀ (a b : α) (l : List α), motive a (b :: l)) → motive x x_1

Equations

• ⋯ = ⋯

theorem List.alternatingSum_cons' {α : Type u_2} [AddCommGroup α] (a : α) (l : List α) : List.alternatingSum (a :: l) = a + -List.alternatingSum l

theorem List.alternatingProd_cons' {α : Type u_2} [CommGroup α] (a : α) (l : List α) : List.alternatingProd (a :: l) = a * (List.alternatingProd l)⁻¹

@[simp]

theorem List.alternatingSum_cons {α : Type u_2} [AddCommGroup α] (a : α) (l : List α) : List.alternatingSum (a :: l) = a - List.alternatingSum l

@[simp]

theorem List.alternatingProd_cons {α : Type u_2} [CommGroup α] (a : α) (l : List α) : List.alternatingProd (a :: l) = a / List.alternatingProd l

theorem List.sum_nat_mod (l : List ℕ) (n : ℕ) : List.sum l % n = List.sum (List.map (fun (x : ℕ) => x % n) l) % n

theorem List.prod_nat_mod (l : List ℕ) (n : ℕ) : List.prod l % n = List.prod (List.map (fun (x : ℕ) => x % n) l) % n

theorem List.sum_int_mod (l : List ℤ) (n : ℤ) : List.sum l % n = List.sum (List.map (fun (x : ℤ) => x % n) l) % n

theorem List.prod_int_mod (l : List ℤ) (n : ℤ) : List.prod l % n = List.prod (List.map (fun (x : ℤ) => x % n) l) % n

theorem List.sum_map_count_dedup_filter_eq_countP {α : Type u_2} [DecidableEq α] (p : α → Bool) (l : List α) : List.sum (List.map (fun (x : α) => List.count x l) (List.filter p (List.dedup l))) = List.countP p l

Summing the count of x over a list filtered by some p is just countP applied to p

theorem List.sum_map_count_dedup_eq_length {α : Type u_2} [DecidableEq α] (l : List α) : List.sum (List.map (fun (x : α) => List.count x l) (List.dedup l)) = List.length l

theorem map_list_sum {M : Type u_5} {N : Type u_6} [AddMonoid M] [AddMonoid N] {F : Type u_11} [FunLike F M N] [AddMonoidHomClass F M N] (f : F) (l : List M) : f (List.sum l) = List.sum (List.map (⇑f) l)

theorem map_list_prod {M : Type u_5} {N : Type u_6} [Monoid M] [Monoid N] {F : Type u_11} [FunLike F M N] [MonoidHomClass F M N] (f : F) (l : List M) : f (List.prod l) = List.prod (List.map (⇑f) l)

theorem AddMonoidHom.map_list_sum {M : Type u_5} {N : Type u_6} [AddMonoid M] [AddMonoid N] (f : M →+ N) (l : List M) : f (List.sum l) = List.sum (List.map (⇑f) l)

Deprecated, use _root_.map_list_sum instead.

theorem MonoidHom.map_list_prod {M : Type u_5} {N : Type u_6} [Monoid M] [Monoid N] (f : M →* N) (l : List M) : f (List.prod l) = List.prod (List.map (⇑f) l)

Deprecated, use _root_.map_list_prod instead.

@[simp]

theorem Nat.sum_eq_listSum (l : List ℕ) : Nat.sum l = List.sum l

theorem List.length_sigma {α : Type u_2} {σ : α → Type u_11} (l₁ : List α) (l₂ : (a : α) → List (σ a)) : List.length (List.sigma l₁ l₂) = List.sum (List.map (fun (a : α) => List.length (l₂ a)) l₁)

theorem List.ranges_join (l : List ℕ) : List.join (List.ranges l) = List.range (List.sum l)

theorem List.mem_mem_ranges_iff_lt_sum (l : List ℕ) {n : ℕ} : (∃ s ∈ List.ranges l, n ∈ s) ↔ n < List.sum l

Any entry of any member of l.ranges is strictly smaller than l.sum.

@[simp]

theorem List.length_join {α : Type u_2} (L : List (List α)) : List.length (List.join L) = List.sum (List.map List.length L)

theorem List.countP_join {α : Type u_2} (p : α → Bool) (L : List (List α)) : List.countP p (List.join L) = List.sum (List.map (List.countP p) L)

theorem List.count_join {α : Type u_2} [BEq α] (L : List (List α)) (a : α) : List.count a (List.join L) = List.sum (List.map (List.count a) L)

@[simp]

theorem List.length_bind {α : Type u_2} {β : Type u_3} (l : List α) (f : α → List β) : List.length (List.bind l f) = List.sum (List.map (List.length ∘ f) l)

theorem List.countP_bind {α : Type u_2} {β : Type u_3} (p : β → Bool) (l : List α) (f : α → List β) : List.countP p (List.bind l f) = List.sum (List.map (List.countP p ∘ f) l)

theorem List.count_bind {α : Type u_2} {β : Type u_3} [BEq β] (l : List α) (f : α → List β) (x : β) : List.count x (List.bind l f) = List.sum (List.map (List.count x ∘ f) l)

theorem List.take_sum_join {α : Type u_2} (L : List (List α)) (i : ℕ) : List.take (List.sum (List.take i (List.map List.length L))) (List.join L) = List.join (List.take i L)

In a join, taking the first elements up to an index which is the sum of the lengths of the first i sublists, is the same as taking the join of the first i sublists.

theorem List.drop_sum_join {α : Type u_2} (L : List (List α)) (i : ℕ) : List.drop (List.sum (List.take i (List.map List.length L))) (List.join L) = List.join (List.drop i L)

In a join, dropping all the elements up to an index which is the sum of the lengths of the first i sublists, is the same as taking the join after dropping the first i sublists.

theorem List.drop_take_succ_join_eq_get {α : Type u_2} (L : List (List α)) (i : Fin (List.length L)) : List.drop (List.sum (List.take (↑i) (List.map List.length L))) (List.take (List.sum (List.take (↑i + 1) (List.map List.length L))) (List.join L)) = List.get L i

In a join of sublists, taking the slice between the indices A and B - 1 gives back the original sublist of index i if A is the sum of the lengths of sublists of index < i, and B is the sum of the lengths of sublists of index ≤ i.