2.4 DIVISIBILITY

2.4 DIVISIBILITY

24 Prove by induction on $n \geq 0$ that $n^3 + 2n$ is divisible by 3

24-1. Basis Condition

---

n = 0일 때 성립하는가?

$$
\begin{aligned}
n^3 + 2n \mod 3 &= n^3 + 2n - 3 \lfloor \frac{n^3+2n}{3} \rfloor
\\
0 \mod 3 &= 0 - 3 \lfloor 0/3 \rfloor
\\
&= 0
\end{aligned}
$$
이므로 성립한다.

24-2. Induction (귀납 가정)

---

n = k일 때 성립한다고 가정하자.

$$
\begin{aligned}
n^3 + 2n \mod 3 &= n^3 + 2n - 3 \lfloor \frac{n^3+2n}{3} \rfloor
\\
k^3 + 2k \mod 3 &= k^3 + 2k - 3 \lfloor \frac{k^3+2k}{3} \rfloor
\\
&= 0
\\
\lfloor \frac{k^3+2k}{3} \rfloor &= \frac{k^3+2k}{3}
\end{aligned}
$$
가 성립한다고 하자.

24-3. Induction Proof (가정을 이용한 증명)

---

n = k + 1일 때를 증명해보자

$$
\begin{aligned}
n^3 + 2n \mod 3 &= n^3 + 2n - 3 \lfloor \frac{n^3+2n}{3} \rfloor
\\
(k+1)^3 + 2(k+1) \mod 3 &= (k+1)^3 + 2(k+1) - 3 \lfloor \frac{(k+1)^3+2(k+1)}{3} \rfloor
\\
&= (k+1)^3 + 2(k+1) - 3 \lfloor \frac{(k^3+3k^2+3k+1)+(2k+2)}{3} \rfloor
\\
&= (k+1)^3 + 2(k+1) - 3 \lfloor \frac{k^3+3k^3+5k+3}{3} \rfloor
\\
&= (k+1)^3 + 2(k+1) - 3 \lfloor \frac{k^3+2k}{3}+\frac{3k^3+3k+3}{3} \rfloor
\\
&= (k+1)^3 + 2(k+1) - 3 \lfloor \frac{k^3+2k}{3}+\frac{3k^3+3k+3}{3} \rfloor
\\
&= (k+1)^3 + 2(k+1) - 3 \frac{k^3+2k}{3}-3(k^3+k+1)
\\
&= (k+1)^3 + 2(k+1) -k^3-2k -3k^3 -3k -3
\\
&= (k+1)^3 + 2(k+1) -k^3-3k^3-5k-3
\\
&= 0
\end{aligned}
$$

따라서 k+1일 때 성립한다.