Definition D1
Sₙ denotes 1 + r + r² + ⋯ + rⁿ⁻¹, defined by S₁ = 1, Sₖ₊₁ = Sₖ + rᵏ.
Proof.
These two equations replace the ellipsis. They determine Sₙ uniquely for each natural number n.convention
∎
Definition D2
a − b denotes the x satisfying b + x = a.
Proof.
If b + x = b + y then x = y, so such an x, if it exists, is unique.convention, A8, A5
∎
Definition D3
a ÷ b denotes the x satisfying b × x = a.
Proof.
a ÷ b has a value only when such an x is unique.convention
∎
Lemma L1
For every natural number n, r Sₙ + 1 = Sₙ + rⁿ
Proof.
(1)Let P(n) be the statement 'rSₙ + 1 = Sₙ + rⁿ'.convention
(2)S₁ = 1, so rS₁ + 1 = r × 1 + 1 = r + 1D1, A6
(3)S₁ + r¹ = 1 + rD1, A7
(4)r + 1 = 1 + r, so P(1) holds.(2), (3), A5
(5)Suppose P(k). rSₖ + 1 = Sₖ + rᵏassumption
(6)Sₖ₊₁ = Sₖ + rᵏD1
(7)rSₖ₊₁ = r(Sₖ + rᵏ) = rSₖ + r·rᵏ(6), E, A2
(8)r·rᵏ = rᵏ·r = rᵏ⁺¹A3, A7
(9)rSₖ₊₁ + 1 = (rSₖ + rᵏ⁺¹) + 1 = (rSₖ + 1) + rᵏ⁺¹(7), (8), A4, A5
(10)(rSₖ + 1) + rᵏ⁺¹ = (Sₖ + rᵏ) + rᵏ⁺¹ = Sₖ₊₁ + rᵏ⁺¹(5), (6)
(11)Therefore P(k+1) holds.(9), (10)
(12)Therefore P(n) holds for every n.(4), (11), A1
∎
Theorem T1
For every natural number n, (r − 1) Sₙ = rⁿ − 1
Proof.
(1)rSₙ + 1 = Sₙ + rⁿL1
(2)r − 1 is the x satisfying 1 + x = r.D2
(3)((r−1) + 1)Sₙ = rSₙ(2), A5, E
(4)((r−1) + 1)Sₙ = (r−1)Sₙ + 1·Sₙ = (r−1)Sₙ + SₙA2, A3, A6
(5)(r−1)Sₙ + Sₙ = rSₙ(3), (4)
(6)((r−1)Sₙ + Sₙ) + 1 = Sₙ + rⁿ(1), (5)
(7)((r−1)Sₙ + 1) + Sₙ = rⁿ + Sₙ(6), A4, A5
(8)Cancelling Sₙ from both sides gives (r−1)Sₙ + 1 = rⁿ(7), A8
(9)1 + (r−1)Sₙ = rⁿ, so (r−1)Sₙ = rⁿ − 1(8), A5, D2
∎
Theorem T2
For every natural number n, Sₙ = (rⁿ − 1) / (r − 1)
Proof.
(1)r is a natural number and r ≠ 1.A10
(2)Every natural number is at least 1, so r ≥ 1, and since r ≠ 1, r ≥ 2.(1), O, N
(3)Therefore r − 1 ≥ 1 and r − 1 ≠ 0(2), D2, N
(4)(r−1)Sₙ = rⁿ − 1T1
(5)(rⁿ − 1) ÷ (r − 1) is the x with (r−1)x = rⁿ − 1.D3
(6)Sₙ is such an x.(4), (5)
(7)Since r − 1 ≠ 0, if (r−1)x = (r−1)y then x = y. Such an x is unique.(3), A9, A3
(8)Sₙ = (rⁿ − 1) / (r − 1)(6), (7), D3
∎
Corollary C
If r = 2 and n = 64, then S₆₄ = 2⁶⁴ − 1 = 18446744073709551615
Proof.
(1)Let r = 2, n = 64. 2 is a natural number and 2 ≠ 1.assumption, N
(2)S₆₄ = (2⁶⁴ − 1) / (2 − 1)(1), T2
(3)2 − 1 = 1D2, N
(4)(2⁶⁴ − 1) ÷ 1 is the x with 1 × x = 2⁶⁴ − 1, and 1 × x = x, so x = 2⁶⁴ − 1D3, A3, A6
(5)S₆₄ = 2⁶⁴ − 1 = 18446744073709551615(2), (3), (4), N
∎