수학적 귀납법과 유한 검사의 한계

무한 범위에는 연결 논증이 필요하다

정수를 많이 검사하면 패턴을 찾을 수 있지만 미검사 사례와 연결되지는 않습니다. 수학적 귀납법은 시작점과 임의 사례에서 다음 사례로 가는 규칙을 증명합니다. 4에서 5로 가는 것만 확인하는 것과 모든 k의 연결을 증명하는 것은 다릅니다.

ℕ={0,1,2,…}를 사용합니다. 1에서 시작하는 주장은 별도 시작점이 필요합니다. 참인 합 공식, 틀린 거듭제곱 부등식, 늦게 반례가 나오는 소수 패턴을 함께 다룹니다.

귀납 원리

음이 아닌 정수의 술어 P(n)에 대해

을 확보하면 모든 n≥0에서 P(n)입니다. 귀납 가정은 임의 k에서 조건문을 증명하기 위한 임시 가정이지 모든 n의 최종 결론을 미리 가정하는 허가가 아닙니다.

실패하는 최소 자연수가 있다고 해봅시다. 시작점은 아니고, 앞의 성공 사례 다음에도 올 수 없다는 모순을 얻습니다. 자연수의 정렬 원리와 연결되는 설명이며 모든 실수 매개변수에 자동으로 적용되는 규칙은 아닙니다.

합 공식 증명

S(0)=0, n≥1에서 $S(n)=1+\cdots+n$로 정의하고

를 증명합니다. 기초 n=0에서 양쪽이 0입니다. 임의 정수 k≥0에서 식이 성립한다고 가정하면

입니다. 정확히 P(k+1)이므로 시작점과 임의 단계가 전체 범위를 연결합니다.

기준 실험의 최대값 5에서는 합이 0,1,3,6,10,15입니다. 여섯 사례는 유한 구현을 검산하고, 위 논증은 무한 주장을 증명합니다. 서로 보완하지만 같은 표식으로 대체할 수는 없습니다.

시작점 하나만으로는 부족하다

n≥1의 $2^n>n^2$는 n=1에서 2>1로 참이지만 n=2에서는 4>4가 거짓입니다. 기초 사례가 후속 단계를 보장하지 않습니다.

n≥5로 바꾸면 참이지만 다른 정리와 다른 시작점입니다. 32>25에서 출발하여 k≥5의 가정으로 $2^{k+1}>2k^2\ge(k+1)^2$를 얻습니다. 이때 $k^2-2k-1>0$을 사용합니다. 반례를 본 뒤 원래 범위를 몰래 바꾸지 말고 수정했다고 밝혀야 합니다.

시작점 누락도 다릅니다. P(n)을 n=n+1로 두면 P(k)에서 다음 식을 대수적으로 유도하는 조건문은 만들 수 있어도 P(0)이 거짓입니다. 연결만 있고 시작이 없으면 실제 사례를 증명하지 못합니다.

긴 패턴을 깨는 늦은 반례

n²+n+41은 n=0부터 39까지 소수입니다. 하지만

여서 모든 n의 소수 주장은 거짓입니다. 실험은 가능한 약수로 나누어 가장 작은 약수를 표시합니다. 소수이면 그 수 자체가 가장 작은 약수이며 별도 참·거짓 열이 소수 여부입니다.

긴 성공은 추측을 만들지만 귀납 연결을 대신하지 못합니다. 순서대로 값을 생성했다고 귀납 증명이 되는 것도 아닙니다. 핵심은 P(k)가 논리적으로 P(k+1)을 보장하는지입니다.

강한 귀납과 재귀

강한 귀납은 시작부터 k까지 모두 가정하여 k+1을 보입니다. 이전 사례들을 묶은 더 강한 술어를 만들 수 있어 자연수에서 보통 귀납과 같은 강도입니다.

예를 들어 모든 정수 n≥2는 소인수분해를 가집니다. 2는 소수라 기초가 됩니다. 다음 n이 소수면 끝이고, 합성수면 n=ab, 2≤a,b<n입니다. 더 작은 두 수의 분해를 강한 가정으로 얻어 곱하면 n의 분해입니다. 존재를 증명한 것이며 유일성 정리는 별도입니다.

재귀 알고리즘에도 감소하는 크기나 정초 구조가 필요합니다. 같은 크기로 자신을 호출한다고 귀납이 정당화되지는 않습니다. 식·트리의 구조 귀납은 시간 번호가 아니라 생성 규칙을 따릅니다.

유한 검사기를 정직하게 읽기

칸은 n과 그 사례의 진릿값입니다. 표는 양쪽 값 또는 다항식·약수를 보여줍니다. 합과 소수는 0부터, 거듭제곱은 1부터입니다. 최대값 때문에 적용 사례가 없더라도 빈 검사 통과를 무한 명제의 증명으로 읽지 마세요.

참인 합 예제만 별도 일반 증명 패널을 제공합니다. 검색 한계는 유한 증거만 바꾸며 이미 증명한 일반 논증의 유효성을 바꾸지 않습니다. 틀린 예제의 정의역도 자동으로 고쳐주지 않습니다.

AI와 연구 습관

반복 알고리즘의 불변식, 재귀 프로그램의 정확성, 기호 구조에 관한 논증에 연결됩니다. 학습 손실이 처음 100회 줄었다고 영원히 단조 감소하는 것은 아닙니다. 귀납을 쓰려면 불변식과 모든 허용 갱신의 보존 조건을 정해야 합니다.

학습한 추론기의 그럴듯한 증명 문장과 검증된 도출은 다릅니다. 많은 과제 통과는 유한 성능 주장입니다. 허용 표현 전체의 정리는 규칙·검사기·모든 생성 경우의 검토가 필요합니다.

연습과 근거

1. n=0을 포함해 홀수 합 $\sum_{i=1}^n(2i-1)=n^2$를 귀납 증명하세요.
2. P(5)만 보인 것이 모든 n의 합 공식 증명이 아닌 이유는?
3. 거듭제곱의 첫 실패 사례는? 답: n=2입니다.
4. n=40의 다항식 약수는? 답: 41입니다.
5. 누적 합 반복문의 초기화·보존·종료 결과를 연결하는 불변식을 적으세요.

보충은 MIT Mathematics for Computer Science 읽기 자료를 참고하세요. 이 실험은 작은 정수의 정확 계산이며 범용 자동 정리 증명기가 아닙니다.