PROOF 129
증명하라.
귀납법으로 일반항을 확인한다
자연수 ℕ 위에서.
한 줄씩, 이유를 따라가 봅시다
먼저 이미 주어진 것과 앞으로 보여야 할 것을 나누어 읽어 보세요. 다음 줄로 넘어갈 때마다 어떤 정의나 앞의 결과를 사용했는지 묻습니다. 연결이 보이지 않으면 결론을 외우기보다 그 전제로 잠시 돌아가도 좋습니다.
정의 D1
수열 (aₙ) 은 첫 항 a₁ 과 점화식 aₖ₊₁ = F(aₖ, k) 로 정한다. 각 자연수 n 에 하나의 값을 주는 식 f 에 대하여 명제 P(n) 을 「aₙ = f(n)」이라 한다.
증명.
(1)a₁ 이 주어지고 aₖ₊₁ 이 aₖ 로부터 정해지므로 각 n 에서 aₙ 은 하나로 정해진다.약속
(2)f 는 추측이다. P(n) 이 확인되기 전까지 aₙ 자리에 f(n) 을 쓸 수 없다.약속
∎
정리 T1
P(1) 이 성립하고 모든 자연수 k 에 대하여 P(k) ⟹ P(k+1) 이면, 모든 자연수 n 에 대하여 aₙ = f(n) 이다.
증명.
(1)P(1) 이 성립한다.가정
(2)모든 k 에 대하여 P(k) ⟹ P(k+1) 이다.가정
(3)그러므로 모든 n 에 대하여 P(n) 이고, 즉 aₙ = f(n) 이다.(1), (2), A1, D1
∎
정리 T2
귀납 단계만으로는 결론이 따라오지 않는다.
증명.
(1)a₁ = 1, aₖ₊₁ = aₖ + 2 인 수열 (aₙ) 과 추측 f(n) = 2n 을 잡는다.D1
(2)aₖ = 2k 라 하면 aₖ₊₁ = 2k + 2 이다.(1), E
(3)2(k+1) = 2k + 2×1 = 2k + 2A2, A3
(4)그러므로 aₖ₊₁ = 2(k+1) 이고, 모든 k 에 대하여 P(k) ⟹ P(k+1) 이 성립한다.(2), (3)
(5)f(1) = 2 × 1 = 2 = 1 + 1A3, A6
(6)a₁ = f(1) 이라 하면 1 = 1 + 1 이 되어 A5 에 어긋난다.(1), (5), E, A5
(7)그러므로 P(1) 이 성립하지 않고, 모든 n 에 대하여 aₙ = f(n) 인 것도 아니다.(6)
∎
정리 T3
기저만으로는 결론이 따라오지 않는다.
증명.
(1)a₁ = 1, aₖ₊₁ = aₖ + 2 인 수열 (aₙ) 과 추측 h(n) = n 을 잡는다.D1
(2)a₁ = 1 = h(1) 이므로 P(1) 이 성립한다.(1)
(3)a₂ = a₁ + 2 = 1 + 2 = 2 + 1 = 3(1), A7, A6
(4)h(2) = 2(1)
(5)3 = 2 라 하면 2 + 1 = 2 = 1 + 1 이다.A6, E
(6)그러면 2 = 1 이고, 다시 1 + 1 = 1 이 되어 A5 에 어긋난다.(5), A4, A6, A5
(7)그러므로 a₂ ≠ h(2) 이고, P(1) 이 성립해도 P(2) 는 성립하지 않는다.(3), (4), (6)
(8)모든 n 에 대하여 aₙ = h(n) 인 것도 아니다.(7)
∎
비고
A1 은 이 증명에서 제거할 수 있는가.
확인 절차의 두 조건은 유한한 계산이다. 그 계산이 어디까지 덮는지 확인하라.