[Real Analysis] 2. Mathematical Induction

이번 시간에는 수학적 귀납법에 대해서 알아보도록 하겠습니다.

 

수학적 귀납법은 많은 사람들이 고등학교때부터 마치 공리인 것처럼 받아들이고 있지만, 실제로는 공리가 아닌 증명이 필요한 정리입니다. 정리 내용은 다음과 같습니다.:

Thm (Mathematical Induction)
Let $P(n)$ be a statement for $n\in\mathbb{N}$.
If
     1) $P(1)$ is true, and
     2) $P(k)$ is true $\Rightarrow P(k+1)$ is true,
then $P(n)$ is true for all $n\in\mathbb{N}$.

 

 

수학적 귀납법은 자연수에 대한 명제가 주어져 있을 때, 해당 명제가 모든 자연수에 대해서 성립하는 것을 확인하고 싶을 때 쓰는 정리입니다. 그런데 자연수의 집합은 무한한데 어떻게 모든 자연수에 대해서 성립하는 것을  보장할 수 있을까요? 무한한 프로세스를 유한한 프로세스로 내리는 작업이 필요한데, 여기서는 이를 위해서 아래의 자연수의 성질을 사용해야 합니다. Well Ordering Principle은 Zorn's lemma 및 하우스도르프의 극대원리 등과 동치를 이루는 공리입니다.

Well Ordering Principle
Every nonempty subset of $\mathbb{N}$ has a smallest element.

 

 

이를 이용하면 위의 수학적 귀납법을 증명할 수 있습니다.:

proof)
모든 자연수 $n\in\mathbb{N}$에 대해서 $P(n)$이 참인 것을 보이는 것이 목표이므로, 귀류법을 사용하여 모순을 이끌어내 보겠습니다. 이를 위해 $P(n_o)$이 거짓이 되게끔 하는 적당한 자연수 $n_o\in\mathbb{N}$이 존재한다고 가정하겠습니다.


여기서 $$ A\coloneqq\{n\in\mathbb{N}\::\:P(n)\text{ is false.}\} $$ 로 정의하면, $n_o\in A$이므로 $A\neq\empty$임을 쉽게 알 수 있습니다. 그리고 정의상 $A\subset\mathbb{N}$ 또한 성립합니다. 즉, $A$는 $\mathbb{N}$의 nonempty subset인 것입니다.


이제 Well Ordering Principle에 의하여, $A$는 smallest element $k_o$을 가지게 됩니다.

한편, 가정에 의해 $P(1)$은 참이므로 $1\notin A$이고, 이에 따라 $k_o>1$이 됩니다.

또한, $k_o$은 주어진 명제를 거짓으로 만드는 가장 작은 자연수이므로 $P(k_o-1)$은 참임을 알 수 있습니다.

여기서 다시 한 번 가정에 의하면 $P(k_o)$이 참이라는 결론이 나오게 됩니다.

하지만 이는 $k_o\notin A$을 의미하므로 모순이 됩니다.


이 모순의 시작은 $A$를 nonempty set으로 만드는 가정이므로, 귀류법에 의하여 모든 자연수 $n\in\mathbb{N}$에 대하여 $P(n)$이 참임을 알 수 있습니다. $\square$

 

 

수학적 귀납법을 활용하는 예제를 하나 살펴보겠습니다.:

Example
For $r\neq 1$, show that $$ r+\cdots+r^n=\frac{r-r^{n+1}}{1-r}. $$

proof)
위 명제를 $P(n)$이라 하겠습니다.

만약 $n=1$인 경우, 좌변은 $$ r^1 = r, $$ 우변은 $$ \frac{r-r^2}{1-r} = \frac{r(1-r)}{1-r} = r $$ 이므로 좌우변이 같습니다. 따라서 $P(1)$이 참임을 알 수 있습니다.

다음으로 자연수 $k\ge 1$에 대해 $P(k)$가 참이라 가정하겠습니다.
그러면,
$$ \begin{aligned} r + \cdots + r^k + r^{k+1} &= \frac{r-r^{k+1}}{1-r} + r^{k+1} \\ &= \frac{r-r^{k+1}+r^{k+1}(1-r)}{1-r} \\ &= \frac{r-r^{k+2}}{1-r} \end{aligned} $$ 이므로 $P(k+1)$도 참임을 알 수 있습니다.

따라서 mathematical induction에 의해 모든 자연수 $n$에 대해 $P(n)$이 참임을 증명하였습니다. $\square$

 

 

이번에는 부등식으로 주어진 명제를 증명해보겠습니다.:

Example (Bernoulli's inequality)
For $h>-1$, prove that $$ (1+h)^n \ge 1+nh. $$

proof)
위 명제를 $P(n)$이라고 정의하겠습니다.

$n=1$인 경우, 좌변은 $$ (1+h)^1 = 1+h, $$ 우변은 $$ 1+1\cdot h= 1+h $$이므로 좌우변이 같아져 $P(1)$이 성립하게 됩니다.

이제 자연수 $k$에 대하여 $P(k)$가 참이라고 가정하겠습니다.
그러면 아래의 부등식이 성립하게 됩니다.:
$$ \begin{aligned} (1+h)^{k+1} &= (1+h)^k(1+h) \\ &\ge (1+kh)(1+h) \\ &= 1 + (k+1)h + kh^2 \\ &\ge 1+ (k+1)h. \end{aligned} $$ 이로부터 $P(k+1)$ 또한 참이 됩니다.

그러므로 mathematical induction에 의해 모든 자연수 $n$에 대해 $P(n)$이 참이 됩니다. $\square$

 

 

수학적 귀납법을 동작하게 하는 핵심 동력은 자연수의 Well Ordering Principle이고, 이 axiom의 핵심은 successive이기 때문에, 꼭 처음에 $1$부터 시작할 필요도, 꼭 바로 직전만의 성공을 보장받을 필요도 없을 것입니다. 실제로 induction은 핵심 property인 successive는 공유한채로, 다양한 modified version을 가지고 있습니다.:

Modified #1
Fix $n_o\in\mathbb{N}$ and let $P(n)$ be a statement for natural numbers $n\ge n_o$.
If
     1) $P(n_o)$ is true, and
     2) $P(k)$ is true for a natural number $k\ge n_o$ $\Rightarrow P(k+1)$ is true,
then $P(n)$ is true for all $n\ge n_o$.

Modified #2
Let $P(n)$ be a statement for $n\in\mathbb{N}$.
If
     1) $P(1)$ is true, and
     2) $P(j)$ is true for all $j<k$ $\Rightarrow P(k)$ is true,
then $P(n)$ is true for all $n\in\mathbb{N}$.

 

 

두 modified versions 모두 굉장히 자주 쓰이는 정리들이니, 기존 mathematical induction을 활용하여 한 번쯤은 증명해보시길 권장드립니다. Induction은 이렇게 증명하는 것도 물론 중요하지만, 수학 전반에 걸쳐 굉장히 자주 쓰기 때문에 정리의 내용을 똑바로 숙지하고 있어야 하겠습니다.

 

 

이상으로 수학적 귀납법에 대한 설명을 마치겠습니다.

감사합니다.