수학적 귀납법 2

이번 포스팅에서는 간단한 정수론 문제를 수학적 귀납법을 가지고 증명 해 보겠습니다.

Scratch Work

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

For every nonnegative interger $n, \; 9|(4^{3n}-1)$

증명

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

$P_n:=n, \; 9|(4^{3n}-1)$

다음으로 Base Case에 대해서 참임을 확인 해 보겠습니다.

Base Case:

$n=0$ 일 때 $9|(4^{4 \cdot 0}-1) \Rightarrow 9|0$

과 같으므로 $P_0$은 참입니다. 여기서 $9|0 \Rightarrow 0=9 \cdot c$ where $c=0$ 입니다.

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

Inductive Step:

$n=k$에 where $k \in \mathbb{Z}^{+}$ 대해서 참으로 가정 하겠습니다. 그리하면 $P_k$에 대해서

$9|(4^{3k}-1) \Rightarrow 4^{3k}-1=9 \cdot x \Rightarrow 4^{3k}=9x+1$ where $x \in \mathbb{Z}$ 입니다.

우리는 이제 $n=k+1$의 경우에 대해 참임을 보이겠습니다.

$P_{k+1} = 9|4^{3(k+1)-1}$입니다.

그리하면

입니다.

그런데 $64x+7 \in \mathbb{Z}$ 이므로 $9|(4^{3n}-1)$이 성립함을 보였습니다. $\blacksquare$