녹원학원 수학과학영재교육 010-3549-5206 : 수학적 귀납법(數學的歸納法, mathematical induction)

2013년 10월 15일 화요일

수학적 귀납법(數學的歸納法, mathematical induction)

수학적 귀납법(數學的歸納法, mathematical induction)은 수학에서 어떤 주장이 모든 자연수에 대해 성립함을 증명하기 위해 사용되는 방법이다. 무한개의 명제를 함께 증명하기 위해, 먼저 '첫 번째 명제가 참임을 증명'하고, 그 다음에는 '명제들 중에서 어떤 하나가 참이면 언제나 그 다음 명제도 참임을 증명'하는 방법으로 이루어진다.

보다 일반적으로, 이는 모든 서수의 집합에 대해 초한귀납법으로 확장할 수 있으며, 임의의 기초관계에 대해 구조적 귀납법으로 확장할 수도 있다. 수학적 귀납법은 자연수 집합에서 정렬순서원리와 동치이다.

수학적 귀납법은 이름과는 달리 귀납적 논증이 아닌 연역적 논증에 속하며, 따라서 이는 명확하고 엄밀한 증명 방법이다. 그러나 의미에 혼란이 없을 때에는 수학적 귀납법을 줄여서 귀납법이라고 부르기도 한다.

수학적 귀납법의 원리는 자연수 집합 $\mathbb{N}$ 의 부분집합을 $S$ 라 할 때, 두 조건

$1\in S$
$k\in S$ 이면 $k+1\in S$

을 만족하면 $S=\mathbb{N}$ 이라는 정리이다.

증명 귀류법으로 증명한다. 먼저 $S\not=\mathbb{N}$ 이라고 가정하자. 그러면 $S$ 는 $\mathbb{N}$ 의 진부분집합이므로, $\mathbb{N}-S\not=\emptyset$ 이다. 따라서 자연수의 정렬성에 의해 $\mathbb{N}-S$ 의 최소원 $m$ 이 존재한다. 이때 $1\in S$ 이므로 $m>1$ 이다. 따라서 $m-1\in S$ 이므로, 두 번째 조건에 의해 $m\in S$ 이다. 이는 $m\not\in S$ 라는 것에 모순이 된다. 따라서 원하는 결론을 얻는다.

일반적인 수학적 귀납법의 형태는

P(1)이 성립
P(n)이 성립하면 P(n+1)도 성립

을 증명하지만 이를 확장하여,

P(1)이 성립
P(2)가 성립
P(n)이 성립하면 P(n+2)도 성립

P(1)이 성립
P(2)가 성립
P(n), P(n+1)이 성립하면 P(n+2)도 성립

P(1)이 성립
P(1), P(2), ..., P(n)이 성립하면 P(n+1)도 성립

등을 증명하기도 한다.

Mathematical induction is a method of mathematical proof typically used to establish a given statement for all natural numbers. It is done in two steps. The first step, known as the base case, is to prove the given statement for the first natural number. The second step, known as the inductive step, is to prove that the given statement for any one natural number implies the given statement for the next natural number. From these two steps, mathematical induction is the rule from which we infer that the given statement is established for all natural numbers.
The method can be extended to prove statements about more general well-founded structures, such as trees; this generalization, known as structural induction, is used in mathematical logic and computer science. Mathematical induction in this extended sense is closely related to recursion.
Although its namesake may suggest otherwise, mathematical induction should not be misconstrued as a form of inductive reasoning (also see Problem of induction). Mathematical induction is an inference rule used in proofs. In mathematics, proofs are examples of deductive reasoning and inductive reasoning is excluded from proofs.^[1]

The simplest and most common form of mathematical induction infers that a statement involving a natural number n holds for all values of n. The proof consists of two steps:

The basis (base case): prove that the statement holds for the first natural number n. Usually, n = 0 or n = 1.
The inductive step: prove that, if the statement holds for some natural number n, then the statement holds for n + 1.

The hypothesis in the inductive step that the statement holds for some n is called the induction hypothesis (or inductive hypothesis). To perform the inductive step, one assumes the induction hypothesis and then uses this assumption to prove the statement for n + 1.

Whether n = 0 or n = 1 depends on the definition of the natural numbers. If 0 is considered a natural number, as is common in the fields of combinatorics and mathematical logic, the base case is given by n = 0. If, on the other hand, 1 is taken as the first natural number, then the base case is given by n = 1.

Mathematical induction can be used to prove that the following statement, which we will call P(n), holds for all natural numbers n.

$0 + 1 + 2 + \cdots + n = \frac{n(n + 1)}{2}\,.$

P(n) gives a formula for the sum of the natural numbers less than or equal to number n. The proof that P(n) is true for each natural number n proceeds as follows.

Basis: Show that the statement holds for n = 0.
P(0) amounts to the statement:

$0 = \frac{0\cdot(0 + 1)}{2}\,.$

In the left-hand side of the equation, the only term is 0, and so the left-hand side is simply equal to 0.
In the right-hand side of the equation, 0·(0 + 1)/2 = 0.
The two sides are equal, so the statement is true for n = 0. Thus it has been shown that P(0) holds.

Inductive step: Show that if P(k) holds, then also P(k + 1) holds. This can be done as follows.

Assume P(k) holds (for some unspecified value of k). It must then be shown that P(k + 1) holds, that is:

$(0 + 1 + 2 + \cdots + k )+ (k+1) = \frac{(k+1)((k+1) + 1)}{2}.$

Using the induction hypothesis that P(k) holds, the left-hand side can be rewritten to:

$\frac{k(k + 1)}{2} + (k+1)\,.$

Algebraically:

$\begin{align} \frac{k(k + 1)}{2} + (k+1) & = \frac {k(k+1)+2(k+1)} 2 \\ & = \frac{k^2+k+2k+2}{2} \\ & = \frac{(k+1)(k+2)}{2} \\ & = \frac{(k+1)((k+1) + 1)}{2} \end{align}$

thereby showing that indeed P(k + 1) holds.

Since both the basis and the inductive step have been performed, by mathematical induction, the statement P(n) holds for all natural n. Q.E.D.

Pólya's proof that there is no "horse of a different color"

Main article: All horses are the same color

In this example, the binary relation in question is an equivalence relation applied to horses, such that two horses are equivalent if they are the same color. The argument is essentially identical to the one above, but the crucial n = 1 case fails, causing the entire argument to be invalid.

In the middle of the 20th century, a commonplace colloquial locution to express the idea that something is unexpectedly different from the usual was "That's a horse of a different color!". George Pólya posed the following exercise: Find the error in the following argument, which purports to prove by mathematical induction that all horses are of the same color:

Basis: If there is only one horse, there is only one color.
Induction step: Assume as induction hypothesis that within any set of n horses, there is only one color. Now look at any set of n + 1 horses. Number them: 1, 2, 3, ..., n, n + 1. Consider the sets {1, 2, 3, ..., n} and {2, 3, 4, ..., n + 1}. Each is a set of only n horses, therefore within each there is only one color. But the two sets overlap, so there must be only one color among all n + 1 horses.

The basis case n=1 is trivial (as any horse is the same color as itself), and the inductive step is correct in all cases n > 1. However, the logic of the inductive step is incorrect for n = 1, because the statement that "the two sets overlap" is false (there are only n+1=2 horses prior to either removal, and after removal the sets of one horse each do not overlap). Indeed, going from the n = 1 case to the n = 2 case is clearly the crux of the matter; if one could prove the n = 2 case directly without having to infer it from the n=1 case, then all higher cases would follow from the inductive hypothesis.

If we want to prove a statement not for all natural numbers but only for all numbers greater than or equal to a certain number b then:

Showing that the statement holds when n = b.
Showing that if the statement holds for n = m ≥ b then the same statement also holds for n = m + 1.

This can be used, for example, to show that n² ≥ 3n for n ≥ 3. A more substantial example is a proof that

${n^n \over 3^n} < n! < {n^n \over 2^n}\mbox{ for }n\ge 6.$

In this way we can prove that P(n) holds for all n ≥1, or even n ≥−5. This form of mathematical induction is actually a special case of the previous form because if the statement that we intend to prove is P(n) then proving it with these two rules is equivalent with proving P(n + b) for all natural numbers n with the first two steps.

Wikipedia

댓글 없음:

댓글 쓰기