[수학1] 수학적 귀납법

앞에서 우리는 수열을 귀납적으로 정의하는 것에 대해 이야기 했습니다. 수열의 귀납적 정의는 마치 도미노를 쓰러뜨리는 것과 같이 반복적이고 연쇄적인 현상에 대해 두 개의 식으로 표현한 것 입니다.

지금부터 이야기 할 수학적 귀납법은 이런 귀납적 정의를 응용하여 명제가 참임을 증명하는 방법입니다.

 

▣ 수학적 귀납법 

자연수에 n에 대해 정의된 어떤 명제 p(n)를 생각해 봅시다.

이 명제가 참임을 직관적으로 알아내는 방법은 

P(1)이 참임을 증명

P(2)이 참임을 증명

P(3)이 참임을 증명

입니다. 하지만  자연수는 무수히 많으므로 계속 대입해 갈 수 없습니다. 

하지만 p(n)이 성립할 때, p(n+1)도 성립한다면, p(1)이 성립함만을 알게 되면 이 식으로 부터 

이 되므로 P(n)은 모든 자연수에 대해 참이 된다는 걸 알 수 있습니다.

즉, 수학적 귀납법은  p(1)이 성립함과 p(n)이 성립할 때, p(n+1)도 성립을 밝히기만 하면 된다는 것을 알 수 있습니다. 

수학적 귀납법

자연수 n에 대한 명제 p(n)에 대하여 

p(n)이 모든 자연수에 대해 성립

함을 보이기 위해서는 다음 두 가지를 밝히면 됩니다.

i) n=1일 때 p(n)이 성립함을 증명

ii) n=k일 때 p(n)이 성립한다고 가정하면  n=k+1일 때 p(n)도 성립함을 증명

수학적 귀납법에서 가장 핵심적인 부분은 「p(k)가 성립한다고 가정」한 후 이것을 가지고 「p(k+1)일 때 성립」함을 증명하는 것입니다. 즉, 참이라고 가정한 명제 p(k)로 부터 p(k+1)이 참임을 밝혀야 하는 것 입니다. 하지만 많은 학생들은 p(k)처럼 p(k+1)도 역시 n대신 k+1을 대입해 놓고 증명을 하려 합니다. 이것은 증명해야 하는 대상인 p(k+1)을 이미 성립했다고 해 놓은 상태에서 다시 증명하려 하는 어리석은 행동입니다.

그러면 구체적인 예를 통해 정확한 방법을 익히도록 하겠습니다.

 

▣ 수학적 귀납법 문제

문제1. 모든 자연수 n에 대하여 다음 등식이 성립함을 보여라.

증명)   i)  n=1일 때,

이므로 성립합니다.

ii) n=k일 때,  이 성립한다고 가정하면

이다. 

이 때, 의 양변에  를 더하면

  

이다. 따라서  은  n=k+1일 때도 성립합니다.

그러므로 i), ii)에 의해 은 모든 자연수에 대해서 성립합니다.

등식을 증명하는 것은 비교적 쉬운편이나 부등식을 증명하는 데는 약간의 기술이 필요합니다. 왜냐하면 등식의 경우는 같은것을 등호로 연결해 나가니까 생각의 여지가 적지만 부등식의 경우 크거나 작은 수는 사실 무수히 많으므로 부등호의 다음에 연결할 수나 식이 무수히 많게 되기 때문입니다. 즉, 부등호의 다음에 어떤 수나 식을 사용하여 증명하느냐에 따라 증명의 성패가 달려있습니다.

문제2. 일 때, 인 모든 자연수 n에 대하여 다음 부등식이 성립함을 증명하여라.

증명)    i) n=2일 때, 

이므로  에 대하여 (좌변) > (우변) 이다. 

따라서  은 n=2일 때 성립한다.

ii) n=k일 때,  이 성립한다고 가정하면

이다.

이 때,  의 양변에  를 곱하면  이므로

이다. 따라서 

이므로  은  n=k+1일 때도 성립합니다.

그러므로 i), ii)에 의해 은 2이상의 모든 자연수에 대해서 성립합니다.