Documentation

Mathlib.Algebra.GeomSum

Partial sums of geometric series #

This file determines the values of the geometric series $\sum_{i=0}^{n-1} x^i$ and $\sum_{i=0}^{n-1} x^i y^{n-1-i}$ and variants thereof. We also provide some bounds on the "geometric" sum of a/b^i where a b : ℕ.

Main statements #

Several variants are recorded, generalising in particular to the case of a noncommutative ring in which x and y commute. Even versions not using division or subtraction, valid in each semiring, are recorded.

theorem geom_sum_succ {α : Type u} [Semiring α] {x : α} {n : } :
iFinset.range (n + 1), x ^ i = x * iFinset.range n, x ^ i + 1
theorem geom_sum_succ' {α : Type u} [Semiring α] {x : α} {n : } :
iFinset.range (n + 1), x ^ i = x ^ n + iFinset.range n, x ^ i
theorem geom_sum_zero {α : Type u} [Semiring α] (x : α) :
iFinset.range 0, x ^ i = 0
theorem geom_sum_one {α : Type u} [Semiring α] (x : α) :
iFinset.range 1, x ^ i = 1
@[simp]
theorem geom_sum_two {α : Type u} [Semiring α] {x : α} :
iFinset.range 2, x ^ i = x + 1
@[simp]
theorem zero_geom_sum {α : Type u} [Semiring α] {n : } :
iFinset.range n, 0 ^ i = if n = 0 then 0 else 1
theorem one_geom_sum {α : Type u} [Semiring α] (n : ) :
iFinset.range n, 1 ^ i = n
theorem op_geom_sum {α : Type u} [Semiring α] (x : α) (n : ) :
MulOpposite.op (iFinset.range n, x ^ i) = iFinset.range n, MulOpposite.op x ^ i
@[simp]
theorem op_geom_sum₂ {α : Type u} [Semiring α] (x : α) (y : α) (n : ) :
iFinset.range n, MulOpposite.op y ^ (n - 1 - i) * MulOpposite.op x ^ i = iFinset.range n, MulOpposite.op y ^ i * MulOpposite.op x ^ (n - 1 - i)
theorem geom_sum₂_with_one {α : Type u} [Semiring α] (x : α) (n : ) :
iFinset.range n, x ^ i * 1 ^ (n - 1 - i) = iFinset.range n, x ^ i
theorem Commute.geom_sum₂_mul_add {α : Type u} [Semiring α] {x : α} {y : α} (h : Commute x y) (n : ) :
(iFinset.range n, (x + y) ^ i * y ^ (n - 1 - i)) * x + y ^ n = (x + y) ^ n

$x^n-y^n = (x-y) \sum x^ky^{n-1-k}$ reformulated without - signs.

@[simp]
theorem neg_one_geom_sum {α : Type u} [Ring α] {n : } :
iFinset.range n, (-1) ^ i = if Even n then 0 else 1
theorem geom_sum₂_self {α : Type u_1} [CommRing α] (x : α) (n : ) :
iFinset.range n, x ^ i * x ^ (n - 1 - i) = n * x ^ (n - 1)
theorem geom_sum₂_mul_add {α : Type u} [CommSemiring α] (x : α) (y : α) (n : ) :
(iFinset.range n, (x + y) ^ i * y ^ (n - 1 - i)) * x + y ^ n = (x + y) ^ n

$x^n-y^n = (x-y) \sum x^ky^{n-1-k}$ reformulated without - signs.

theorem geom_sum_mul_add {α : Type u} [Semiring α] (x : α) (n : ) :
(iFinset.range n, (x + 1) ^ i) * x + 1 = (x + 1) ^ n
theorem Commute.geom_sum₂_mul {α : Type u} [Ring α] {x : α} {y : α} (h : Commute x y) (n : ) :
(iFinset.range n, x ^ i * y ^ (n - 1 - i)) * (x - y) = x ^ n - y ^ n
theorem Commute.mul_neg_geom_sum₂ {α : Type u} [Ring α] {x : α} {y : α} (h : Commute x y) (n : ) :
(y - x) * iFinset.range n, x ^ i * y ^ (n - 1 - i) = y ^ n - x ^ n
theorem Commute.mul_geom_sum₂ {α : Type u} [Ring α] {x : α} {y : α} (h : Commute x y) (n : ) :
(x - y) * iFinset.range n, x ^ i * y ^ (n - 1 - i) = x ^ n - y ^ n
theorem geom_sum₂_mul {α : Type u} [CommRing α] (x : α) (y : α) (n : ) :
(iFinset.range n, x ^ i * y ^ (n - 1 - i)) * (x - y) = x ^ n - y ^ n
theorem Commute.sub_dvd_pow_sub_pow {α : Type u} [Ring α] {x : α} {y : α} (h : Commute x y) (n : ) :
x - y x ^ n - y ^ n
theorem sub_dvd_pow_sub_pow {α : Type u} [CommRing α] (x : α) (y : α) (n : ) :
x - y x ^ n - y ^ n
theorem one_sub_dvd_one_sub_pow {α : Type u} [Ring α] (x : α) (n : ) :
1 - x 1 - x ^ n
theorem sub_one_dvd_pow_sub_one {α : Type u} [Ring α] (x : α) (n : ) :
x - 1 x ^ n - 1
theorem nat_sub_dvd_pow_sub_pow (x : ) (y : ) (n : ) :
x - y x ^ n - y ^ n
theorem Odd.add_dvd_pow_add_pow {α : Type u} [CommRing α] (x : α) (y : α) {n : } (h : Odd n) :
x + y x ^ n + y ^ n
theorem Odd.nat_add_dvd_pow_add_pow (x : ) (y : ) {n : } (h : Odd n) :
x + y x ^ n + y ^ n
theorem geom_sum_mul {α : Type u} [Ring α] (x : α) (n : ) :
(iFinset.range n, x ^ i) * (x - 1) = x ^ n - 1
theorem mul_geom_sum {α : Type u} [Ring α] (x : α) (n : ) :
(x - 1) * iFinset.range n, x ^ i = x ^ n - 1
theorem geom_sum_mul_neg {α : Type u} [Ring α] (x : α) (n : ) :
(iFinset.range n, x ^ i) * (1 - x) = 1 - x ^ n
theorem mul_neg_geom_sum {α : Type u} [Ring α] (x : α) (n : ) :
(1 - x) * iFinset.range n, x ^ i = 1 - x ^ n
theorem Commute.geom_sum₂_comm {α : Type u} [Semiring α] {x : α} {y : α} (n : ) (h : Commute x y) :
iFinset.range n, x ^ i * y ^ (n - 1 - i) = iFinset.range n, y ^ i * x ^ (n - 1 - i)
theorem geom_sum₂_comm {α : Type u} [CommSemiring α] (x : α) (y : α) (n : ) :
iFinset.range n, x ^ i * y ^ (n - 1 - i) = iFinset.range n, y ^ i * x ^ (n - 1 - i)
theorem Commute.geom_sum₂ {α : Type u} [DivisionRing α] {x : α} {y : α} (h' : Commute x y) (h : x y) (n : ) :
iFinset.range n, x ^ i * y ^ (n - 1 - i) = (x ^ n - y ^ n) / (x - y)
theorem geom₂_sum {α : Type u} [Field α] {x : α} {y : α} (h : x y) (n : ) :
iFinset.range n, x ^ i * y ^ (n - 1 - i) = (x ^ n - y ^ n) / (x - y)
theorem geom_sum_eq {α : Type u} [DivisionRing α] {x : α} (h : x 1) (n : ) :
iFinset.range n, x ^ i = (x ^ n - 1) / (x - 1)
theorem Commute.mul_geom_sum₂_Ico {α : Type u} [Ring α] {x : α} {y : α} (h : Commute x y) {m : } {n : } (hmn : m n) :
(x - y) * iFinset.Ico m n, x ^ i * y ^ (n - 1 - i) = x ^ n - x ^ m * y ^ (n - m)
theorem Commute.geom_sum₂_succ_eq {α : Type u} [Ring α] {x : α} {y : α} (h : Commute x y) {n : } :
iFinset.range (n + 1), x ^ i * y ^ (n - i) = x ^ n + y * iFinset.range n, x ^ i * y ^ (n - 1 - i)
theorem geom_sum₂_succ_eq {α : Type u} [CommRing α] (x : α) (y : α) {n : } :
iFinset.range (n + 1), x ^ i * y ^ (n - i) = x ^ n + y * iFinset.range n, x ^ i * y ^ (n - 1 - i)
theorem mul_geom_sum₂_Ico {α : Type u} [CommRing α] (x : α) (y : α) {m : } {n : } (hmn : m n) :
(x - y) * iFinset.Ico m n, x ^ i * y ^ (n - 1 - i) = x ^ n - x ^ m * y ^ (n - m)
theorem Commute.geom_sum₂_Ico_mul {α : Type u} [Ring α] {x : α} {y : α} (h : Commute x y) {m : } {n : } (hmn : m n) :
(iFinset.Ico m n, x ^ i * y ^ (n - 1 - i)) * (x - y) = x ^ n - y ^ (n - m) * x ^ m
theorem geom_sum_Ico_mul {α : Type u} [Ring α] (x : α) {m : } {n : } (hmn : m n) :
(iFinset.Ico m n, x ^ i) * (x - 1) = x ^ n - x ^ m
theorem geom_sum_Ico_mul_neg {α : Type u} [Ring α] (x : α) {m : } {n : } (hmn : m n) :
(iFinset.Ico m n, x ^ i) * (1 - x) = x ^ m - x ^ n
theorem Commute.geom_sum₂_Ico {α : Type u} [DivisionRing α] {x : α} {y : α} (h : Commute x y) (hxy : x y) {m : } {n : } (hmn : m n) :
iFinset.Ico m n, x ^ i * y ^ (n - 1 - i) = (x ^ n - y ^ (n - m) * x ^ m) / (x - y)
theorem geom_sum₂_Ico {α : Type u} [Field α] {x : α} {y : α} (hxy : x y) {m : } {n : } (hmn : m n) :
iFinset.Ico m n, x ^ i * y ^ (n - 1 - i) = (x ^ n - y ^ (n - m) * x ^ m) / (x - y)
theorem geom_sum_Ico {α : Type u} [DivisionRing α] {x : α} (hx : x 1) {m : } {n : } (hmn : m n) :
iFinset.Ico m n, x ^ i = (x ^ n - x ^ m) / (x - 1)
theorem geom_sum_Ico' {α : Type u} [DivisionRing α] {x : α} (hx : x 1) {m : } {n : } (hmn : m n) :
iFinset.Ico m n, x ^ i = (x ^ m - x ^ n) / (1 - x)
theorem geom_sum_Ico_le_of_lt_one {α : Type u} [LinearOrderedField α] {x : α} (hx : 0 x) (h'x : x < 1) {m : } {n : } :
iFinset.Ico m n, x ^ i x ^ m / (1 - x)
theorem geom_sum_inv {α : Type u} [DivisionRing α] {x : α} (hx1 : x 1) (hx0 : x 0) (n : ) :
iFinset.range n, x⁻¹ ^ i = (x - 1)⁻¹ * (x - x⁻¹ ^ n * x)
theorem RingHom.map_geom_sum {α : Type u} {β : Type u_1} [Semiring α] [Semiring β] (x : α) (n : ) (f : α →+* β) :
f (iFinset.range n, x ^ i) = iFinset.range n, f x ^ i
theorem RingHom.map_geom_sum₂ {α : Type u} {β : Type u_1} [Semiring α] [Semiring β] (x : α) (y : α) (n : ) (f : α →+* β) :
f (iFinset.range n, x ^ i * y ^ (n - 1 - i)) = iFinset.range n, f x ^ i * f y ^ (n - 1 - i)

Geometric sum with -division #

theorem Nat.pred_mul_geom_sum_le (a : ) (b : ) (n : ) :
(b - 1) * iFinset.range n.succ, a / b ^ i a * b - a / b ^ n
theorem Nat.geom_sum_le {b : } (hb : 2 b) (a : ) (n : ) :
iFinset.range n, a / b ^ i a * b / (b - 1)
theorem Nat.geom_sum_Ico_le {b : } (hb : 2 b) (a : ) (n : ) :
iFinset.Ico 1 n, a / b ^ i a / (b - 1)
theorem geom_sum_pos {α : Type u} {n : } {x : α} [StrictOrderedSemiring α] (hx : 0 x) (hn : n 0) :
0 < iFinset.range n, x ^ i
theorem geom_sum_pos_and_lt_one {α : Type u} {n : } {x : α} [StrictOrderedRing α] (hx : x < 0) (hx' : 0 < x + 1) (hn : 1 < n) :
0 < iFinset.range n, x ^ i iFinset.range n, x ^ i < 1
theorem geom_sum_alternating_of_le_neg_one {α : Type u} {x : α} [StrictOrderedRing α] (hx : x + 1 0) (n : ) :
if Even n then iFinset.range n, x ^ i 0 else 1 iFinset.range n, x ^ i
theorem geom_sum_alternating_of_lt_neg_one {α : Type u} {n : } {x : α} [StrictOrderedRing α] (hx : x + 1 < 0) (hn : 1 < n) :
if Even n then iFinset.range n, x ^ i < 0 else 1 < iFinset.range n, x ^ i
theorem geom_sum_pos' {α : Type u} {n : } {x : α} [LinearOrderedRing α] (hx : 0 < x + 1) (hn : n 0) :
0 < iFinset.range n, x ^ i
theorem Odd.geom_sum_pos {α : Type u} {n : } {x : α} [LinearOrderedRing α] (h : Odd n) :
0 < iFinset.range n, x ^ i
theorem geom_sum_pos_iff {α : Type u} {n : } {x : α} [LinearOrderedRing α] (hn : n 0) :
0 < iFinset.range n, x ^ i Odd n 0 < x + 1
theorem geom_sum_ne_zero {α : Type u} {n : } {x : α} [LinearOrderedRing α] (hx : x -1) (hn : n 0) :
iFinset.range n, x ^ i 0
theorem geom_sum_eq_zero_iff_neg_one {α : Type u} {n : } {x : α} [LinearOrderedRing α] (hn : n 0) :
iFinset.range n, x ^ i = 0 x = -1 Even n
theorem geom_sum_neg_iff {α : Type u} {n : } {x : α} [LinearOrderedRing α] (hn : n 0) :
iFinset.range n, x ^ i < 0 Even n x + 1 < 0
theorem Nat.geomSum_eq {m : } (hm : 2 m) (n : ) :
kFinset.range n, m ^ k = (m ^ n - 1) / (m - 1)

Value of a geometric sum over the naturals. Note: see geom_sum_mul_add for a formulation that avoids division and subtraction.

theorem Nat.geomSum_lt {m : } {n : } {s : Finset } (hm : 2 m) (hs : ks, k < n) :
ks, m ^ k < m ^ n

If all the elements of a finset of naturals are less than n, then the sum of their powers of m ≥ 2 is less than m ^ n.