Sequoia

{{|
수학에서 사용하는 증명 방법의 하나, 자연수 N과 크기가 같거나 작은 집합 A에 대해 A의 모든 원소 x에 대해 f(x)가 성립한다를 증명할 때 사용된다. 귀납적 추론과는 다름에 주의하라. (see also 귀납의문제) 수학적귀납법은 논리적으로 완전히 빈틈없고 엄밀한 증명이다.

N_0(0를 포함한 자연수)에 대해, f(0)이 성립되고, N_0에 포함된 모든 x에 대해 f(x)가 성립하면 f(x+1)이 성립한다면, N_0에 포함된 모든 x에 대해 f(x)가 성립한다.

f(0)이 참이고, f(x)가 참이라고 가정하면 f(x+1)이 참임을 증명한다. f(0)이 참이므로 f(1)이 참이고, f(1)이 참이므로 f(2)도 참이다. 이와 같이 모든 자연수 x에 대해 f(x)가 참임이 증명되었다.
이 때, f(x)이면 f(x+1)을 증명하기 위해 f(x)가 참임을 증명할 필요가 없음을 유의하라. f(x)를 참이라고 가정하고 f(x+1)을 증명하는 것이다.

모든 자연수 n에 대해, 1부터 n까지 자연수의 합은 n(n+1)/2 이다.

f(x)가 1부터 x까지 자연수의 합일때, f(1) = 1 = 1*2/2 이고 이것은 당연히 참이다.
f(x)=x(x+1)/2 라고 가정하면, f(x+1) = x(x+1)/2+x+1 = { x(x+1) + 2(x+1) } / 2 = (x+1)(x+2) / 2 = (x+1){ (x+1)+1 } / 2 이므로 f(x+1)에 대해서도 성립한다.
그러므로 모든 자연수 n에 대해 1부터 n까지 자연수의 합은 n(n+1)/2 이다.

N_0에 대해 위의 수학적 귀납법이 성립하는 것은, 0으로부터 시작하여 원소에 +1을 하는 것만으로 N_0의 모든 원소를 만들(construct) 수 있기 때문이다.
즉 특정한 집합 A에 대해, A의 모든 원소를 유한한 개수의 방법으로 만들 수 있다면, 각각의 방법에 대해 수학적 귀납법을 적용하여 A의 모든 원소를 순회(iterate)할 수 있도록 증명하면 된다.

모든 문법에 맞는 다항식(polynomial)에서 왼쪽 괄호('(')와 오른쪽 괄호(')')의 개수는 같다.

증명은 생략. -o-
|}}

몸이 엄청 많이 피곤하네요^{; 건강하시죠? 매지님}; K리그 팀들 우수수 떨어지고... 돈 있는 삼성은 끌고있죠^^; 나중에 또 연락드릴께요. 한동안 정신없을것도 같네요~ ^^; --Crystal

홈페이지분류