이산수학/증명 - 수학적 귀납법

증명의 이해

수학적 귀납법

• 자연수 n에 대하여 정의된 명제함수 P(n)에 대하여 아래의 순서에 따라 증명하는 방법.

  기본가정 : n = 1일 때 P(1)은 참
  
  귀납가정 : 어떤 자연수 k에 대하여 P(k)가 참일 경우 P(k+1)도 참
  
  => (1)에 의해 P(1)은 참이다.
  => (2)에 의해 P(1)이 참이므로 P(2)도 참이다.
  => (2)에 의해 P(2)이 참이므로 P(3)도 참이다.
  
  이를 반복하여 적용하면 모든 자연수 n에 대하여 P(n)이 참이다.

• 자연수 n에 대하여 1에서부터 n까지의 합이 n(n+1)/2임을 보이시오.

  일단 수학적 귀납법이 아닌 가우스가 발견한 방법으로 증명을 해보겠다.
  
  우선 1부터 n까지의 수를 순서대로 나열한다. 이를 수열이라 한다. 이때 수열의 사장 첫 항은 1이고 마지막 항은 n이다.
  이제 수열을 다시 뒤집어 나열한다. 이때 가정 첫 항은 n이고 마지막 항은 1이다.
  각 항끼리 더해보면 n+1과 같은 값이 나타난다. 이 값은 뒤집은 수열과 원래 수열을 더한값과 같다.
  
  즉, 원래 수열과 뒤집은 수열을 더한 값은 (n+1)n이 된다. 이 값을 2로 나누면 1에서부터 n까지의 합인 n(n+1)/2를 얻을 수 있다.
  
  따라서 1에서부터 n까지의 합은 n(n+1)/2임을 보일 수 있다.
  
  
  
  수학적 귀납법을 이용한 증명
  => n=1일 때 1의 합은 1이므로 n(n+1/2 = 1(1+1)/2 = 1이 성립한다.
  => n=k일 때 1부터 k까지의 합이 k(k+1)/2임을 가정한다.
  => n=k+1일 때, 1부터 k+1까지의 합을 구한다.
  => 1부터 k까지의 합에 k+1을 더하면 1부터 k+1까지의 합이 된다. 따라서, 1부터 k+1까지의 합은 k(k+1)/2 + (k+1)이 된다.
  =>이를 정리하면, 1부터 k+1까지의 합은 (k+1)(k+2)/2가 된다.
  따라서, n=k+1일 때, 1부터 n까지의 합이 n(n+1)/2임을 볼 수 있다.
  
  모든 자연수 n에 대해 1부터 n까지의 합이 n(n+1)/2임을 수학적 귀납법을 이용하여 증명할 수 있다.