18강에서 을 유도했습니다. 그때 쓴 방법은 합을 두 번 적어 거꾸로 더하는 것이었고, 결과는 맞았지만 그 방법은 등차수열에만 통합니다. 합의 모양이 조금만 달라지면 다시 처음부터 궁리해야 합니다.
이 강의는 자연수 전체에 대한 명제를 모양과 상관없이 증명하는 방법을 줍니다. 값을 어떻게 얻었는지는 묻지 않고, 얻은 식이 맞는지만 확인합니다. 그래서 추측한 공식을 검증하는 데 특히 강합니다.
24강 문제 3에서 "보다 큰 모든 자연수는 소수를 약수로 가진다"를 관찰로만 넘겼습니다. 이 강의의 강한 귀납법으로 그 빚을 갚습니다.
문제. 모든 자연수 에 대하여 임을 증명하세요. 단 18강에서 쓴 방법은 쓰지 않습니다.
생각의 실마리. 에서 확인해도 22강 문제 3의 교훈대로 증명이 되지 않습니다. 대신 도미노를 생각합니다. 도미노가 전부 넘어지려면 두 가지만 있으면 됩니다. 첫 번째가 넘어지는 것과, 어느 하나가 넘어지면 그다음도 넘어진다는 것입니다. 이 두 가지를 식으로 옮겨 봅니다.
풀이. 명제를 이라 부릅니다. 즉 은 "입니다"라는 조건입니다.
기초 단계. 일 때를 확인합니다. 왼쪽은 이고 오른쪽은 이므로 이 참입니다.
귀납 단계. 임의의 자연수 를 잡고 가 참이라고 가정합니다. 즉
라고 놓습니다. 이 가정을 귀납 가정이라고 합니다. 이제 을 보입니다. 왼쪽을 계산합니다.
앞의 개 항의 합에 귀납 가정을 대입합니다.
로 묶습니다.
이것은 의 오른쪽인 과 같습니다. 따라서 가 참이면 도 참입니다.
기초 단계와 귀납 단계가 모두 확인되었으므로 모든 자연수 에 대하여 이 참입니다.
이 문제에서 배우는 것: 수학적 귀납법.
자연수 전체에 대한 명제 을 증명하는 방법으로 다음 두 단계를 확인하는 것을 수학적 귀납법이라고 합니다.
이 두 가지가 확인되면 에서 가 따라 나오고, 에서 이 따라 나오는 식으로 모든 자연수에 도달합니다. 도미노가 전부 넘어지는 것과 같습니다.
여기서 자주 생기는 오해를 정리합니다. 귀납 단계에서 를 가정하는 것은 증명하려는 것을 가정하는 순환논법이 아닙니다. 우리가 증명하는 것은 가 아니라 조건문 입니다. 23강에서 조건문을 증명할 때 가정을 놓고 시작했던 것과 똑같습니다.
증명을 쓸 때 반드시 지킬 것이 두 가지입니다.
첫째, 귀납 가정을 어디에 썼는지 명시합니다. 위 증명에서는 "귀납 가정을 대입합니다"라고 적은 자리입니다. 이 자리가 없으면 귀납법을 쓴 것이 아닙니다.
둘째, 의 정확한 모양을 미리 적어 둡니다. 도착점을 모르면 어디로 계산해 가야 할지 알 수 없습니다.
바로 확인.
확인 1-1. 모든 자연수 에 대하여 임을 귀납법으로 증명하세요.
답. 기초 단계는 에서 왼쪽 , 오른쪽 로 참입니다. 귀납 단계는 을 가정하고 양변에 을 더하면 이므로 이 참입니다.
확인 1-2. 위 증명에서 귀납 가정을 쓴 자리를 지목하세요.
답. 을 만들 때 앞의 개 항의 합을 으로 바꾼 자리입니다.
확인 1-3. 의 오른쪽 모양을 을 대입해 적어 보세요. 명제가 일 때입니다.
답. 입니다. 자리마다 을 넣고 정리한 결과입니다.
문제. 다음 두 명제를 귀납법으로 증명하세요.
(1) 모든 자연수 과 인 실수 에 대하여 입니다.
(2) 모든 자연수 에 대하여 입니다.
생각의 실마리. 두 문제 모두 귀납 단계에서 왼쪽에 항 하나를 더한 뒤 귀납 가정을 대입합니다. 대입한 다음이 관건입니다. 목표인 의 모양을 먼저 적어 두고, 거기로 가려면 무엇으로 묶어야 하는지 역으로 봅니다.
풀이. (1) 기초 단계에서 이면 왼쪽은 이고 오른쪽은 입니다. 이므로 분모가 이 아니고, 참입니다.
귀납 단계에서 을 가정합니다. 양변에 을 더합니다.
오른쪽을 4강의 통분으로 정리합니다.
이것이 입니다. 따라서 명제가 증명됩니다.
(2) 기초 단계에서 이면 왼쪽은 이고 오른쪽은 입니다.
귀납 단계에서 을 가정하고 양변에 을 더합니다.
목표는 확인 1-3에서 적어 둔 입니다. 이 공통이므로 묶습니다.
대괄호 안을 3강의 인수분해로 정리합니다. 이므로
이고 목표와 일치합니다.
이 문제에서 배우는 것: 귀납 단계의 표준 절차.
귀납 단계는 언제나 같은 순서로 진행합니다.
3번이 귀납법의 핵심 장치입니다. 합이든 곱이든 부등식이든, 인 경우를 인 경우와 나머지 한 조각으로 쪼갤 수 있으면 귀납법이 작동합니다.
5번에서 막히면 대개 인수분해가 필요합니다. (2)에서 을 인수분해한 자리가 그 예이며, 목표를 미리 적어 두었기 때문에 어떤 인수를 만들어야 하는지 알 수 있었습니다. 도착점을 적지 않고 계산하면 이 자리에서 헤맵니다.
(1)의 결과는 18강에서 등비수열의 합으로 이미 얻은 식입니다. 그때는 를 계산해 유도했고, 여기서는 결과가 맞는지 확인했습니다. 두 방법의 성격이 다릅니다. 유도는 답을 만들어 내고, 귀납법은 만들어진 답을 검증합니다.
바로 확인.
확인 2-1. 을 귀납법으로 증명할 때 귀납 단계에서 무엇을 더합니까?
답. 을 더합니다. 그리고 이 과 같음을 보입니다.
확인 2-2. 확인 2-1의 계산을 실제로 마치세요.
답. 으로 묶으면 이고 이는 입니다.
확인 2-3. (1)의 증명에서 이라는 조건은 어디에 쓰였습니까?
답. 분모 이 이 아니어야 식이 정의되는 자리에 쓰였습니다. 기초 단계와 귀납 단계 모두에서 필요합니다. 이면 왼쪽 합은 이 되어 다른 공식을 씁니다.
문제. 인 모든 자연수 에 대하여 임을 증명하세요.
생각의 실마리. 22강 확인 3-2에서 가 반례임을 확인했습니다. 그러니 부터 시작할 수 없습니다. 도미노를 처음부터 세울 필요는 없고 다섯 번째부터 세워도 그 뒤는 전부 넘어집니다. 귀납 단계에서는 를 쓰고, 이 보다 큰지 따로 확인해야 합니다.
풀이. 기초 단계. 일 때 이고 이므로 입니다. 참입니다.
귀납 단계. 이고 이라고 가정합니다. 양변에 를 곱합니다.
이제 임을 보이면 됩니다. 차를 계산합니다.
이므로 이고 따라서 입니다. 그러므로 입니다.
두 부등식을 이으면
이므로 이 참입니다.
기초 단계와 귀납 단계가 모두 확인되었으므로 인 모든 자연수에서 입니다.
이 문제에서 배우는 것: 시작점 옮기기와 부등식 귀납법.
기초 단계를 에서 시작하면 결론도 에서만 성립합니다. 도미노를 다섯 번째부터 세운 것이므로 앞의 네 개는 넘어지지 않습니다. 실제로 에서 부등식이 거짓이므로 이것이 맞습니다.
시작점을 정하는 방법은 다음과 같습니다. 작은 값부터 넣어 보아 명제가 참이 되기 시작하는 첫 자리를 찾고, 그 자리를 기초 단계로 삼습니다. 그리고 귀납 단계의 계산이 그 자리 이후에서 실제로 통하는지 확인합니다. 위 증명에서 이라고 쓸 때 를 썼는데, 이것이 그 확인입니다.
부등식을 귀납법으로 증명할 때의 요령은 중간 다리를 놓는 것입니다. 에서 으로 바로 가지 않고 을 거쳤습니다. 귀납 가정이 주는 것은 까지이고, 나머지 구간은 따로 증명해야 합니다. 이 두 조각을 부등호로 이어 붙이는 것이 부등식 귀납법의 표준 모양입니다.
바로 확인.
확인 3-1. 인 모든 자연수에 대하여 임을 증명할 때 기초 단계에서 무엇을 확인합니까?
답. 에서 이고 이므로 임을 확인합니다.
확인 3-2. 확인 3-1의 귀납 단계를 완성하세요.
답. 을 가정하고 양변을 비교합니다. 이고, 이므로 입니다. 따라서 이므로 입니다.
확인 3-3. 에서 을 주장하면 어떤 반례가 나옵니까?
답. 이면 로 같고, 이면 이며, 이면 으로 같습니다. 세 값이 모두 반례입니다.
문제. 보다 큰 모든 자연수는 소수를 약수로 가짐을 증명하세요. 이것은 24강 문제 3에서 관찰로만 넘어간 사실입니다.
생각의 실마리. 이 소수가 아니면 로 쪼개지는데, 여기서 나오는 는 이 아니라 훨씬 작을 수 있습니다. 예를 들어 이면 가 될 수도 있습니다. 그러니 "에서 성립하면 에서도 성립한다"는 형태로는 연결되지 않습니다. 귀납 가정을 어떻게 넓혀야 를 다룰 수 있을지 생각합니다.
풀이. 기초 단계. 일 때 는 소수이고 자기 자신을 약수로 가지므로 참입니다.
귀납 단계. 라고 하고, 부터 까지의 모든 자연수가 소수 약수를 가진다고 가정합니다. 이제 을 봅니다. 경우를 나눕니다.
경우 1. 이 소수인 경우. 자기 자신이 소수 약수이므로 참입니다.
경우 2. 이 소수가 아닌 경우. 소수가 아니고 보다 크므로 인 자연수 가 존재하며 이고 입니다. 특히 이므로 귀납 가정을 에 적용할 수 있습니다. 따라서 는 소수 약수 를 가집니다. 이고 이므로 23강 확인 1-3에 의해 입니다. 따라서 도 소수 약수를 가집니다.
두 경우 모두에서 성립하므로 귀납 단계가 완료되었고, 보다 큰 모든 자연수가 소수 약수를 가집니다.
이 문제에서 배우는 것: 강한 귀납법.
귀납 가정을 "가 참"에서 "부터 까지 모두 참"으로 바꾼 것을 강한 귀납법이라고 합니다.
이름이 강한 귀납법이지만 기본형보다 더 많은 것을 증명할 수 있는 것은 아닙니다. 두 방법은 증명 능력이 같습니다. 다만 쓰기 편한 상황이 다릅니다.
| 상황 | 쓸 방법 |
|---|---|
| 이 와 새 항 하나로 쪼개집니다 | 기본형 |
| 이 훨씬 작은 경우로 쪼개집니다 | 강한 귀납법 |
| 쪼개지는 크기를 미리 알 수 없습니다 | 강한 귀납법 |
| 앞의 두 항이 모두 필요합니다 | 강한 귀납법 |
이번 문제가 두 번째 줄에 해당합니다. 에서 가 얼마나 작아지는지 알 수 없으므로 부터 까지 전부를 가정해 두어야 합니다.
바로 확인.
확인 4-1. 피보나치 수열 , 에 대하여 을 증명하려면 어느 귀납법이 필요합니까?
답. 강한 귀납법입니다. 이 앞의 두 항에 의존하므로 만으로는 부족하고 도 필요합니다. 기초 단계도 과 두 개를 확인해야 합니다.
확인 4-2. 확인 4-1의 귀납 단계를 완성하세요.
답. 과 를 가정하면 입니다.
확인 4-3. 강한 귀납법이 기본형보다 더 많은 명제를 증명할 수 있습니까?
답. 없습니다. 두 방법의 증명 능력은 같습니다. 을 "부터 까지 모두 참"으로 정의하면 강한 귀납법은 에 대한 기본형 귀납법이 됩니다.
문제. 다음 "증명"의 잘못을 찾으세요.
주장: 모든 자연수 에 대하여, 말 마리가 있으면 그 말들은 모두 같은 색입니다.
증명: 기초 단계로 이면 말이 한 마리뿐이므로 당연히 같은 색입니다. 귀납 단계로 말 마리가 항상 같은 색이라고 가정하고 말 마리를 봅니다. 첫 마리는 귀납 가정에 의해 모두 같은 색이고, 마지막 마리도 귀납 가정에 의해 모두 같은 색입니다. 두 무리가 겹치므로 마리 전부가 같은 색입니다.
생각의 실마리. 결론이 명백히 거짓이므로 증명 어딘가가 반드시 틀렸습니다. 기초 단계는 문제가 없어 보이니 귀납 단계를 봅니다. "두 무리가 겹치므로"라는 문장이 모든 에서 성립합니까? 가 아주 작을 때 두 무리를 실제로 그려 봅니다.
풀이. 귀납 단계의 마지막 문장이 일 때 깨집니다.
이면 말이 마리입니다. 첫 마리는 한 무리이고 마지막 마리는 다른 무리인데, 두 무리가 겹치지 않습니다. 첫 번째 말과 두 번째 말이 서로 다른 말이기 때문입니다. 겹치는 말이 없으면 두 무리의 색을 이어 붙일 근거가 사라집니다.
일 때는 실제로 겹칩니다. 예를 들어 이면 말 마리에서 첫 두 마리와 마지막 두 마리가 가운데 말을 공유합니다. 그러므로 이 증명은 부터는 옳고, 만 성립하지 않습니다.
도미노로 말하면 첫 번째와 두 번째 사이가 끊어져 있습니다. 첫 번째는 넘어지지만 두 번째에 닿지 않으므로 그 뒤가 전부 서지 못합니다.
이 문제에서 배우는 것: 귀납법 증명을 점검하는 법.
귀납법 증명은 그럴듯해 보이면서 틀리기 쉽습니다. 다음 네 가지를 점검합니다.
| 점검 항목 | 무엇을 확인합니까 |
|---|---|
| 기초 단계를 실제로 확인했습니까 | 을 계산으로 확인했는지 봅니다 |
| 귀납 단계가 모든 에서 통합니까 | 작은 에서 논증을 직접 그려 봅니다 |
| 귀납 가정을 실제로 썼습니까 | 안 썼다면 귀납법이 필요 없는 증명입니다 |
| 시작점 이후에서 계산이 유효합니까 | 부등식에서 쓴 조건을 다시 확인합니다 |
두 번째가 이번 문제의 함정입니다. 귀납 단계는 을 요구하므로 한 개의 에서만 깨져도 전체가 무너집니다. 22강에서 배운 대로 전칭 명제는 반례 하나로 거짓이 됩니다. 여기서 이 그 반례입니다.
기초 단계를 빠뜨리는 실수도 흔합니다. 예를 들어 ""이라는 거짓 명제도 귀납 단계는 완벽하게 통과합니다. 양변에 같은 이 붙어 있어 차이가 유지되기 때문입니다. 오직 기초 단계에서만 걸립니다. 귀납 단계가 통과했다고 명제가 참인 것이 아닙니다.
바로 확인.
확인 5-1. ""의 귀납 단계가 통과함을 보이고 기초 단계에서 걸림을 확인하세요.
답. 을 가정하고 을 더하면 이 되어 과 일치합니다. 그러나 에서 왼쪽은 , 오른쪽은 이므로 기초 단계가 거짓입니다.
확인 5-2. 귀납 가정을 쓰지 않은 귀납법 증명은 무엇을 뜻합니까?
답. 각 에서 독립적으로 증명된 것이므로 귀납법이 필요 없었다는 뜻입니다. 잘못은 아니지만 형식만 빌린 것입니다.
확인 5-3. 말 문제의 증명은 어느 부터 옳습니까?
답. 부터 옳습니다. 따라서 가 참이라면 그 뒤가 전부 따라 나오지만, 자체가 거짓이므로 아무것도 얻지 못합니다.
| 단계 | 무엇을 합니까 |
|---|---|
| 기초 단계 | 를 계산으로 확인합니다 |
| 귀납 가정 | 또는 전부를 가정합니다 |
| 도착점 확정 | 의 양변을 미리 적습니다 |
| 쪼개기 | 인 경우를 앞의 경우와 새 조각으로 나눕니다 |
| 대입 | 앞의 경우에 귀납 가정을 넣습니다 |
| 마무리 | 도착점과 같음을 보입니다 |
| 상황 | 쓸 방법 |
|---|---|
| 합 공식을 검증합니다 | 기본형 귀납법 |
| 앞의 두 항이 필요합니다 | 강한 귀납법, 기초 단계 두 개 |
| 쪼개지는 크기를 모릅니다 | 강한 귀납법 |
| 작은 에서 거짓입니다 | 시작점을 옮깁니다 |
| 부등식입니다 | 중간 다리를 놓아 이어 붙입니다 |
| 흔한 오류 | 증상 |
|---|---|
| 기초 단계 누락 | 거짓 명제도 귀납 단계를 통과합니다 |
| 작은 에서 논증이 깨짐 | 말 문제처럼 결론이 거짓이 됩니다 |
| 귀납 가정 미사용 | 귀납법의 형식만 빌린 것입니다 |
| 시작점 조건 미확인 | 부등식 계산이 작은 에서 성립하지 않습니다 |
문제 6. 모든 자연수 에 대하여 임을 증명하세요.
답. 에서 왼쪽 , 오른쪽 입니다. 귀납 단계에서 이므로 성립합니다.
문제 7. 모든 자연수 에 대하여 임을 증명하세요.
답. 에서 입니다. 을 가정하면 이므로 의 배수입니다.
문제 8. 모든 자연수 에 대하여 임을 귀납법으로 증명하세요. 23강 문제 4와 비교하세요.
답. 에서 입니다. 을 가정하면 이므로 짝수입니다. 23강에서는 경우 나누기로 증명했고 여기서는 귀납법으로 증명했습니다. 같은 명제를 두 방법으로 증명할 수 있습니다.
문제 9. 에서 임을 증명하세요.
답. 에서 왼쪽 , 오른쪽 입니다. 귀납 단계에서 입니다. 18강의 망원합과 같은 결과입니다.
문제 10. 에서 임을 증명하세요.
답. 에서 왼쪽 , 오른쪽 입니다. 귀납 단계에서 입니다.
문제 11. 에서 이 의 배수임을 증명하세요.
답. 에서 입니다. 을 가정하면 입니다.
문제 12. 에서 임을 증명하세요.
답. 에서 입니다. 를 가정하면 입니다. 마지막에서 이므로 를 썼습니다.
문제 13. 다음 증명의 잘못을 찾으세요. "에서 이다. 귀납 단계에서 이므로 성립한다."
답. 기초 단계가 없고, 이 작은 에서 성립하지 않습니다. 이면 가 거짓입니다. 문제 3에서 일 때만 통함을 확인했습니다.
문제 14. 강한 귀납법으로 모든 자연수 가 소수들의 곱으로 표현됨을 증명하세요.
답. 는 소수 자신입니다. 가 모두 소수의 곱이라 가정하고 을 봅니다. 소수면 끝입니다. 아니면 이고 이므로 귀납 가정에 의해 각각 소수의 곱이며, 둘을 곱하면 도 소수의 곱입니다.
문제 15. 피보나치 수열에서 임을 증명하세요.
답. 에서 왼쪽 , 오른쪽 입니다. 귀납 단계에서 이며 점화식을 쓴 것입니다.
문제 16. 개의 원소를 가진 집합의 부분집합 개수가 임을 귀납법으로 증명하세요.
답. 이면 공집합의 부분집합은 자기 자신뿐이라 입니다. 원소가 개일 때 라고 가정하고 원소 하나를 더합니다. 부분집합은 새 원소를 포함하지 않는 것과 포함하는 것으로 나뉘고 각각 개이므로 합이 입니다.
문제 17. 에서 임을 증명하세요.
답. 에서 왼쪽 , 오른쪽 입니다. 귀납 단계에서 입니다.
문제 18. 귀납법으로 "모든 자연수는 흥미롭다"를 증명했다는 주장이 있습니다. 근거는 "흥미롭지 않은 자연수가 있다면 그중 가장 작은 것이 있는데, 그것은 가장 작은 흥미롭지 않은 수라는 점에서 흥미롭다"입니다. 이 논증의 문제는 무엇입니까?
답. 흥미롭다는 것이 21강 문제 1의 (다)처럼 판정 기준이 없는 술어입니다. 명제가 아니므로 증명의 대상이 될 수 없습니다. 논증의 형식은 최소원 원리를 쓴 귀류법이지만 다루는 대상이 명제가 아니라서 결론이 성립하지 않습니다.
심화 1. 수학적 귀납법이 성립하는 근거는 무엇입니까? 24강 심화 3의 무한강하와 어떻게 연결됩니까?
답. 자연수의 공집합이 아닌 부분집합에는 최소원이 있다는 성질입니다.
풀이. 이 참이고 이 모든 에서 참인데도 어떤 에서 이 거짓이라고 가정합니다. 가 거짓인 자연수들의 집합 는 공집합이 아니므로 최소원 을 가집니다. 이 참이므로 이고 따라서 이 자연수입니다. 이 최소이므로 은 참이고, 귀납 단계를 적용하면 이 참이어야 합니다. 이는 에 어긋나므로 모순입니다.
남는 것. 귀납법과 무한강하와 최소원 원리는 서로 다른 세 도구가 아니라 같은 성질의 세 얼굴입니다. 귀납법은 아래에서 위로 올라가고, 무한강하는 위에서 아래로 내려가며, 최소원 원리는 내려갈 수 없는 바닥이 있음을 말합니다. 어느 쪽이 편한지에 따라 골라 쓰면 됩니다.
심화 2. 기초 단계 없이 귀납 단계만 성립하는 거짓 명제를 하나 만들고, 왜 기초 단계가 필요한지 설명하세요.
답. "모든 자연수 에 대하여 입니다"가 그런 예입니다.
풀이. 을 가정하고 양변에 을 더하면 이므로 이 나옵니다. 귀납 단계가 완벽하게 성립합니다. 그러나 은 이므로 거짓이고, 도미노의 첫 장이 서 있지 않으므로 아무것도 넘어지지 않습니다.
남는 것. 귀납 단계는 "앞이 참이면 뒤도 참"만 보장합니다. 앞이 거짓이면 21강에서 배운 대로 조건문은 공허하게 참이 되고 아무 정보도 주지 않습니다. 기초 단계는 형식적인 절차가 아니라 도미노 전체를 지탱하는 유일한 접점입니다.
심화 3. 확인 4-3에서 강한 귀납법과 기본형의 증명 능력이 같다고 했습니다. 이것을 증명하세요.
답. 을 새로 정의해 서로 옮길 수 있습니다.
풀이. 강한 귀납법으로 를 증명할 수 있다고 합시다. 을 "이 모두 참"으로 정의합니다. 은 이므로 기초 단계에서 확인됩니다. 를 가정하면 가 모두 참이므로 강한 귀납 단계에 의해 이 참이고, 따라서 이 참입니다. 이것은 에 대한 기본형 귀납법입니다. 반대 방향은 강한 귀납 가정이 기본형 가정을 포함하므로 자명합니다.
남는 것. 두 방법의 차이는 능력이 아니라 표기의 편의입니다. 강한 귀납법을 쓴다는 것은 실제로는 "까지 전부"라는 더 강한 명제에 기본형을 적용하는 것입니다. 증명 도구를 늘리는 대신 명제를 바꿔서 같은 도구로 처리하는 이 발상은 뒤에서 계속 나옵니다.
심화 4. 다음 명제를 증명하려면 귀납 가정을 어떻게 강화해야 합니까? "모든 자연수 에 대하여 입니다."
답. 결론을 으로 강화하면 귀납법이 통합니다.
풀이. 원래 형태로는 귀납 단계에서 와 새 항 을 더해도 밖에 나오지 않아 목표를 넘습니다. 대신 를 가정하면
이고, 이므로
이 되어 강화된 형태가 유지됩니다. 기초 단계는 에서 이므로 참입니다. 강화된 명제가 참이므로 원래 명제도 참입니다.
남는 것. 더 강한 명제가 더 증명하기 쉬울 수 있다는 것이 귀납법의 역설적인 성질입니다. 가정이 강해진 만큼 귀납 단계에서 쓸 수 있는 정보도 많아지기 때문입니다. 귀납법이 막히면 명제를 약화할 것이 아니라 강화해 보는 것이 표준 처방입니다. 33강에서 수열의 수렴을 다룰 때 이 기법을 다시 씁니다.
심화 5. 개의 직선이 평면을 최대 몇 개의 영역으로 나눕니까? 답을 추측하고 귀납법으로 증명하세요.
답. 개입니다.
풀이. 작은 값을 세어 봅니다. 이면 개, 이면 개, 이면 개, 이면 개입니다. 늘어나는 폭이 이므로 번째 직선이 영역을 개 늘린다고 추측합니다.
귀납법으로 확인합니다. 을 영역의 최대 개수라 하면 입니다. 를 가정하고 번째 직선을 그립니다. 이 직선이 기존 개 직선과 서로 다른 점에서 만나면 개의 점이 생기고, 그 점들이 새 직선을 개의 조각으로 나눕니다. 각 조각이 지나가는 영역을 둘로 쪼개므로 영역이 개 늘어납니다. 따라서 입니다.
이 점화식을 풀면 입니다. 문제 1의 결과를 그대로 썼습니다.
남는 것. 귀납법은 답을 만들어 주지 않습니다. 작은 값을 세어 규칙을 추측하고, 그 추측을 귀납법으로 검증하는 두 단계가 필요합니다. 이 문제에서 점화식 을 세우는 부분이 실제 내용이고 귀납법은 그것을 정당화했을 뿐입니다. 점화식을 닫힌 형태로 바꾸는 일반적인 방법은 32강에서 다룹니다.
심화 6. 기본형 귀납법과 강한 귀납법 중 어느 쪽을 쓸지 판단하는 기준을 정리하고, 문제 14와 문제 15에 각각 적용해 보세요.
답. 을 증명할 때 필요한 앞 항이 무엇인지 보고 정합니다.
풀이. 판단 순서는 다음과 같습니다. 먼저 인 경우를 쪼개 보고, 나오는 조각이 하나뿐이면 기본형입니다. 조각의 크기를 미리 알 수 없거나 여러 개면 강한 귀납법입니다.
문제 14는 에서 와 의 크기를 모르므로 강한 귀납법입니다. 문제 15는 에서 하나만 쓰고 점화식은 정의이므로 기본형으로 충분합니다. 확인 4-1의 과 비교하면 차이가 분명해집니다. 그쪽은 와 의 부등식이 둘 다 필요해 강한 귀납법이었고, 여기는 합 공식 하나만 필요합니다.
남는 것. 같은 피보나치 수열이라도 무엇을 증명하느냐에 따라 필요한 귀납법이 달라집니다. 기계적으로 정하지 말고 귀납 단계를 한 줄 써 본 뒤 어떤 앞 항이 등장하는지 보고 결정합니다.
귀납법으로 증명한 공식은 유한한 범위에서 실제 합과 비교해 확인할 수 있습니다. 여기서도 확인은 증명이 아니지만, 계산 실수나 인수분해 오류를 잡아 줍니다.
import numpy as np
n = np.arange(1, 501)
# 문제 1: 1 + 2 + ... + n
cum = np.cumsum(n)
print(bool(np.all(cum == n * (n + 1) // 2))) # True
# 문제 2 (2): 제곱의 합
cum2 = np.cumsum(n**2)
print(bool(np.all(cum2 == n * (n + 1) * (2 * n + 1) // 6))) # True
# 확인 2-1: 세제곱의 합은 합의 제곱입니다.
cum3 = np.cumsum(n**3)
print(bool(np.all(cum3 == (n * (n + 1) // 2) ** 2))) # True
# 문제 3: 2^n > n^2 은 n >= 5 에서만 성립합니다.
m = np.arange(1, 21)
ok = 2.0**m > m**2
print(m[~ok]) # [2 3 4]
# 문제 9: 망원합
i = np.arange(1, 201)
tel = np.cumsum(1.0 / (i * (i + 1)))
print(bool(np.allclose(tel, i / (i + 1)))) # True
# 심화 4: 강화된 상계가 실제로 유지됩니다.
s = np.cumsum(1.0 / i**2)
print(bool(np.all(s <= 2 - 1.0 / i))) # True
print(round(float(s[-1]), 4)) # 1.6399
# 심화 5: n 개의 직선이 만드는 최대 영역 수
lines = np.arange(0, 11)
print((lines**2 + lines + 2) // 2) # [ 1 2 4 7 11 16 22 29 37 46 56]
출력이 주석과 모두 일치합니다. 문제 3의 검산에서 반례가 세 개로 정확히 나왔고 은 이라 통과한다는 점을 확인합니다. 그래서 기초 단계를 로 잡은 것이 옳았습니다. 심화 4에서 부분합이 에 머무는 것도 보입니다. 이 합의 정확한 극한값은 이며 59강의 푸리에 급수에서 구합니다.
정답.
| 기호 | 읽는 법 | 뜻 |
|---|---|---|
| 피 오브 엔 | 자연수 에 대한 조건입니다 | |
| 기초 단계 | base case | 를 직접 확인하는 단계입니다 |
| 귀납 단계 | inductive step | 을 증명하는 단계입니다 |
| 귀납 가정 | 가정 | 귀납 단계에서 놓는 가정입니다 |
| F_ | 에프 엔 | 피보나치 수열의 번째 항입니다 |
| 엔 팩토리얼 | 19강에서 정의한 계승입니다 |
이 강의로 01단원 논리와 증명이 끝납니다. 21강에서 명제를 읽고, 22강에서 범위를 붙이고, 23강부터 25강까지 세 가지 증명 방법을 갖췄습니다. 다음 26강부터 시작하는 02단원에서는 이 도구로 집합과 함수를 다시 세웁니다. 9강에서 그림으로 이해한 함수가 그때 정확한 정의를 얻습니다.