PROOF 183
증명하라.
체스판의 쌀알은 등비수열의 합이다
자연수 ℕ 위에서.
한 줄씩, 이유를 따라가 봅시다
먼저 이미 주어진 것과 앞으로 보여야 할 것을 나누어 읽어 보세요. 다음 줄로 넘어갈 때마다 어떤 정의나 앞의 결과를 사용했는지 묻습니다. 연결이 보이지 않으면 결론을 외우기보다 그 전제로 잠시 돌아가도 좋습니다.
정의 D1
Sₙ 은 1 + r + r² + ⋯ + rⁿ⁻¹ 을 뜻하며, S₁ = 1, Sₖ₊₁ = Sₖ + rᵏ 으로 정한다.
증명.
줄임표 대신 이 두 식을 쓴다. 이 두 식은 각 자연수 n 에 대하여 Sₙ 을 하나로 정한다.약속
∎
정의 D2
a − b 는 b + x = a 를 만족하는 x 를 뜻한다.
증명.
b + x = b + y 이면 x = y 이므로, 그러한 x 는 있으면 하나뿐이다.약속, A8, A5
∎
정의 D3
a ÷ b 는 b × x = a 를 만족하는 x 를 뜻한다.
증명.
그러한 x 가 하나뿐일 때에만 a ÷ b 는 값을 갖는다.약속
∎
보조정리 L1
모든 자연수 n 에 대하여 r Sₙ + 1 = Sₙ + rⁿ
증명.
(1)P(n) 을 「rSₙ + 1 = Sₙ + rⁿ」이라 한다.약속
(2)S₁ = 1 이므로 rS₁ + 1 = r × 1 + 1 = r + 1D1, A6
(3)S₁ + r¹ = 1 + rD1, A7
(4)r + 1 = 1 + r 이므로 P(1) 이 성립한다.(2), (3), A5
(5)P(k) 라 하자. rSₖ + 1 = Sₖ + rᵏ가정
(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)그러므로 P(k+1) 이 성립한다.(9), (10)
(12)그러므로 모든 n 에 대하여 P(n) 이다.(4), (11), A1
∎
정리 T1
모든 자연수 n 에 대하여 (r − 1) Sₙ = rⁿ − 1
증명.
(1)rSₙ + 1 = Sₙ + rⁿL1
(2)r − 1 은 1 + x = r 를 만족하는 x 다.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)양변에서 Sₙ 을 소거하면 (r−1)Sₙ + 1 = rⁿ(7), A8
(9)1 + (r−1)Sₙ = rⁿ 이므로 (r−1)Sₙ = rⁿ − 1(8), A5, D2
∎
정리 T2
모든 자연수 n 에 대하여 Sₙ = (rⁿ − 1) / (r − 1)
증명.
(1)r 은 자연수이고 r ≠ 1 이다.A10
(2)자연수는 1 이상이므로 r ≥ 1 이고, r ≠ 1 이므로 r ≥ 2 이다.(1), O, N
(3)그러므로 r − 1 ≥ 1 이고 r − 1 ≠ 0(2), D2, N
(4)(r−1)Sₙ = rⁿ − 1T1
(5)(rⁿ − 1) ÷ (r − 1) 은 (r−1)x = rⁿ − 1 인 x 다.D3
(6)Sₙ 은 그러한 x 이다.(4), (5)
(7)r − 1 ≠ 0 이므로 (r−1)x = (r−1)y 이면 x = y 다. 그러한 x 는 하나뿐이다.(3), A9, A3
(8)Sₙ = (rⁿ − 1) / (r − 1)(6), (7), D3
∎
따름정리 C
r = 2, n = 64 이면 S₆₄ = 2⁶⁴ − 1 = 18446744073709551615
증명.
(1)r = 2, n = 64 라 하자. 2 는 자연수이고 2 ≠ 1 이다.가정, N
(2)S₆₄ = (2⁶⁴ − 1) / (2 − 1)(1), T2
(3)2 − 1 = 1D2, N
(4)(2⁶⁴ − 1) ÷ 1 은 1 × x = 2⁶⁴ − 1 인 x 이고, 1 × x = x 이므로 x = 2⁶⁴ − 1D3, A3, A6
(5)S₆₄ = 2⁶⁴ − 1 = 18446744073709551615(2), (3), (4), N
∎
비고
A10 은 이 증명에서 제거할 수 있는가.
r ≠ 1 은 공식 끝에 작게 붙어 다니는 단서다. 나눗셈을 쓰는 줄이 어디인지 확인하라.