이산수학 증명법 쉽게 이해하기: 직접증명과 귀납법 기준

핵심 정의와 기호

증명은 정한 범위의 모든 대상에 대해 주장이 성립하는 근거를 제시합니다. 이 글에서 정수는 ℤ, 자연수는 1,2,3,…으로 둡니다.

방법	시작점	핵심 흐름
직접증명	가정 p	정의·이미 아는 사실로 q 도출
대우증명	¬q	동치인 ¬q→¬p 증명
모순증명	주장 전체의 부정	양립할 수 없는 결론 도출
수학적 귀납법	자연수 명제 P(n)	기초 P(1), 임의 k에서 P(k)→P(k+1)

귀납 가정은 결론 전체를 미리 참이라고 두는 것이 아닙니다. 임의의 k에 대한 ‘한 단계 전진’을 증명하기 위한 가정입니다.

가장 작은 예제

직접증명: 정수 n이 짝수이면 어떤 정수 k에 대해 n=2k입니다. n²=4k²=2(2k²)이므로 n²도 짝수입니다.

대우증명: ‘n²이 짝수이면 n은 짝수’의 대우는 ‘n이 홀수이면 n²이 홀수’입니다. n=2k+1이면 n²=2(2k²+2k)+1이므로 홀수입니다.

모순증명: 가장 큰 정수 M이 있다고 가정하면 M+1도 정수이며 더 큽니다. ‘M이 가장 크다’와 모순이므로 가장 큰 정수는 없습니다.

헷갈리는 반례

P(n): n≤3은 n=1,2,3에서 참이지만 n=4에서 거짓입니다. 처음 세 값을 확인한 것은 모든 자연수의 증명이 아닙니다. 반대로 유한한 정의역 전체를 빠짐없이 검사한 경우에는 전수 확인이 증명이 될 수 있습니다.

손으로 풀어보기

P(n): 1+2+…+n=n(n+1)/2를 증명합니다.

1. 기초: n=1이면 왼쪽 1, 오른쪽 1×2/2=1입니다.
2. 귀납 가정: 임의의 k≥1에서 1+…+k=k(k+1)/2라고 가정합니다.
3. 귀납 단계: 1+…+k+(k+1)=k(k+1)/2+(k+1)=(k+1)(k+2)/2입니다.
4. 이는 n=k+1의 식이므로 모든 자연수 n≥1에서 성립합니다.

기초를 빼면 출발점이 없고, 귀납 단계를 빼면 다음 수로 이어질 근거가 없습니다.

선택: JavaScript로 검산하기

코드 직접 실행

본문 예제를 선택하고 실제 계산 결과를 확인합니다.

예제 크게 보기 (새 탭)

손풀이 뒤 선택해서 실행하는 짧은 전체 코드입니다. 브라우저 Console 또는 Node.js가 준비된 환경의 check.mjs에서 실행할 수 있으며 수학 학습에 설치는 필수가 아닙니다.

for (let n = 1; n <= 10; n += 1) {
  const left = (n * (n + 1)) / 2;
  const right = Array.from({ length: n }, (_, i) => i + 1)
    .reduce((sum, x) => sum + x, 0);
  console.log(n, left === right);
}

기대 결과: 1 true부터 10 true까지 열 줄이 나옵니다.

n=1부터 10까지의 계산 확인이며 모든 자연수에 대한 증명은 위 기초·귀납 단계가 담당합니다.

자주 발생하는 오해와 교정

처음 몇 자연수를 검사한 결과를 전체 증명으로 쓰지 않습니다. 귀납법에서는 P(k+1)를 가정하지 않고 P(k)로부터 도출합니다. ‘n² 짝수→n 짝수’의 대우는 ‘n 홀수→n² 홀수’이며 역과 다릅니다.

직접 풀어볼 문제와 해설

쉬운 개념

몇 값을 넣어 맞는지 보는 검산과 모든 자연수에 대한 증명은 다릅니다. 귀납법은 시작값을 확인하고, k에서 참이라는 가정으로 k+1의 식을 도출합니다.

단계별 예제

1. 1+3+5=9=3²로 n=3을 먼저 손으로 확인합니다.
2. 일반적으로 P(k): 첫 k개 홀수의 합=k²라고 가정합니다.
3. 다음 홀수 2k+1을 더하면 k²+2k+1=(k+1)²입니다.

직접 풀 문제

모든 자연수 n≥1에서 1+3+…+(2n−1)=n²임을 귀납법으로 완성하세요. 기초 단계도 반드시 적으세요.

정답·해설 보기

1. n=1에서 왼쪽 1, 오른쪽 1²=1로 기초가 성립합니다.
2. P(k)를 가정하면 첫 k+1개 합은 k²+(2k+1)=(k+1)²입니다.
3. 기초와 귀납 단계가 이어지므로 모든 n≥1에서 성립합니다. n=3 한 사례만으로는 증명이 아닙니다.

다음 학습

4회차에서는 집합의 순서쌍으로 관계를 표현하고 세 성질을 검사합니다. 다음 글 읽기

학습 완료 체크리스트

• 정의의 적용 범위와 기호를 말로 설명할 수 있습니다.
• 위 손풀이를 답을 가린 상태에서 다시 계산합니다.
• 반례가 어떤 조건을 어기는지 설명합니다.

알고리즘 수학 노트

누적 이전 체크포인트: discrete-step-02-set. 아래는 이번 회차의 완성 예시입니다. 자신의 다른 예제 하나를 덧붙여도 좋습니다.

합계 반복문이 처음 k개를 처리한 뒤 sum=1+…+k를 유지한다고 설명하는 것은 반복문 불변식의 출발점입니다. 수학적 귀납법과 연결되지만 종료 조건까지 따로 확인해야 프로그램 정확성을 설명할 수 있습니다. 직접·대우·모순의 출발 가정과 합 공식의 두 단계를 기록합니다.

완료 체크포인트

discrete-step-03-proof

다음 학습

이산수학 관계 쉽게 이해하기: 곱집합과 동치관계 기준에서 다음 개념을 이어갑니다.