수학적 귀납법 1

이번 포스팅에서는 수학적 귀납법에 대해서 알아 보고 간단한 예제 하나를 수학적 귀납법을 통해서 증명 하겠습니다.

증명할 예제는 다음과 같습니다.

Show by induction on $n$ that if $r \neq 1$ and $n \geq 1$, then:

Scratch Work

수학적 귀납법은 페아노 공리계로 부터 유도 된 proposition 입니다. 그러므로 페아노 공리계를 먼저 확인 해 보겠습니다.

Peano's Axioms:

There is a set $\mathbb{N}$ such that:

(1) 1 is in $\mathbb{N}$
(2) If $\mathbb{n} \in \mathbb{N}$, then its successor $\mathbb{n+1} \in \mathbb{N}$
(3) $1$ is not the successor of any element in $\mathbb{N}$
(4) $n \neq m \Rightarrow n+1 \neq m+1$ (different numbers have different successors)
(5) Induction Axiom

• Suppose $S$ is a subset of $\mathbb{N}$ such that:
  a. $1 \in S$
  b. If $n \in S$, then $n+1 \in S$

Then $S = \mathbb{N}$

다음으로 수학적 귀납법(Mathematical Induction)에 대한 proposition을 확인 해 보겠습니다.

Mathematical Induction

• Let $P_n$ be a proposition and suppose
  (1) $P_1$ is true
  (2) For all $n \in \mathbb{N}$, if $P_n$ is true, then $P_{n+1}$ is true
• Then $P_n$ is true for all $n \in \mathbb{N}$

위의 내용을 보면 수학적 귀납법은 페아노 공리계의 (5)번에서 유도 된 proposition 임을 알 수 있습니다.

이제 예제를 증명 하겠습니다.

증명

먼저 다음과 같이 정의 하겠습니다.

$P_n = 1 + r + r^2 + \cdots + r^n = \frac{1-r^{n+1}}{1-r}$

다음으로 Base Case에 대해서 확인 해 보겠습니다. 즉, $P_1$이 참임을 확인 해야 합니다.
그리하면

Base Case:

과 같으므로 $P_1$은 참입니다.

다음으로 Inductive Step에 대해서 확인 해 보겠습니다.

Inductive Step:

$P_n$을 참으로 가정 하겠습니다. 그리하면 다음과 같습니다.

우리는 이제 $P_{n+1}$가 참임을 보여야 합니다. $P_{n+1}$는 다음과 같습니다.

$P_{n+1}$가 참임을 보이는데에 우리차 참으로 가정한 $P_n$을 이용하면 됩니다.(Inductive Hypothesis)

그러면 이제 $P_{n+1}$가 참임을 보이겠습니다.

따라서 $P_{n+1}$은 참입니다.

결론적으로 Mathematical Induction에 의해 $P_n$은 참이고 이것은 모든 자연수 $n$에 대하여

$P_n = 1 + r + r^2 + \cdots + r^n = \frac{1-r^{n+1}}{1-r}$

참으로 성립합니다. $\blacksquare$

참고문헌

Dr. Peyam. Math 140A – Intro to Analysis