2.2 INEQUALITIES

2.2 INEQUALITIES

18 Prove by induction on $n \geq 1$ that if $x > -1$, then $(1+x)^n \geq 1 + nx$

18-1. Basis Condition

---

n = 1일 때 성립하는가?

$$
\begin{aligned}
(1+x)^1 &\geq 1 + 1x \\
&\geq 1 + x \\
\end{aligned}
$$
이므로 성립한다.

18-2. Induction (귀납 가정)

---

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

$$
\begin{aligned}
(1+x)^k \geq 1 + kx
\end{aligned}
$$
가 성립한다고 하자.

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

---

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

$$
\begin{aligned}
(1+x)^{k+1} &\geq 1 + (k+1)x \\
&\geq 1 + x+kx
\end{aligned}
$$
이므로
$$
\begin{aligned}
(1+x)^k(1+x) &\geq (1+kx)(1+x)\\
&\geq 1+x+kx+kx^2\\
1+x+kx+kx^2&\geq 1+x+kx\\
\end{aligned}
$$
이므로

$$
\begin{aligned}
(1+x)^{k+1} &\geq 1+x+kx+kx^2\geq 1+x+kx\\\\
\end{aligned}
$$

을 만족한다.
그러므로 n = k + 1일때도 만족한다.

19 Prove by induction on $n \geq 7$ that $$3^n < n!$$

19-1. Basis Condition

---

n = 7일 때 성립하는가?

$$
\begin{aligned}
3^7 &< 7! \\
2187 &<5040
\end{aligned}
$$
이므로 성립한다.

19-2. Induction (귀납 가정)

---

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

$$
\begin{aligned}
3^k < k!
\end{aligned}
$$
가 성립한다고 하자.

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

---

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

$$
\begin{aligned}
3^{k+1} < (k+1)!
\end{aligned}
$$

이므로

$$
\begin{aligned}
3^{k} 3 &< k! 3 \\
3^{k+1} &< k! 3 \\
k! 3 &< (k+1)! \\
k & \geq 7
\end{aligned}
$$

이므로

$$
\begin{aligned}
3^{k+1}< k!*3 <(k+1)!
\end{aligned}
$$

을 만족한다.
그러므로 n = k + 1일때도 만족한다.

20 Prove by induction on $n \geq 5$ that $$2^n > n^2$$

20-1. Basis Condition

---

n = 5일 때 성립하는가?

$$
\begin{aligned}
2^5&> 5^2 \\
32 &> 25
\end{aligned}
$$
이므로 성립한다.

20-2. Induction (귀납 가정)

---

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

$$
\begin{aligned}
2^k > k^2
\end{aligned}
$$
가 성립한다고 하자.

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

---

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

$$
\begin{aligned}
2^{k+1} > (k+1)^2
\end{aligned}
$$
이므로
$$
\begin{aligned}
2^{k}_2 &> k^2_2 \\
2^{k+1} &> k^2_2 \\
k^2_2&>(k+1)^2 \\
k^2*2&>k^2+2k+1 \\
k^2-2k-1 &>0 \\
(k-1)^2-2&>0 \\
(k-1)^2&>2 \\
k\geq5
\end{aligned}
$$
이므로

$$
\begin{aligned}
2^{k+1}> k^2*2> (k+1)^2
\end{aligned}
$$

을 만족한다.
그러므로 n = k + 1일때도 만족한다.

21 Prove by induction on $k \geq 1$ that $$\sum_{i=1}^ni^k \leq n^k(n+1)/2$$

21-1. Basis Condition

---

k = 1일 때 성립하는가?

$$
\begin{aligned}
\sum_{i=1}^ni^1 &\leq n^1(n+1)/2 \\
\sum_{i=1}^ni &\leq n(n+1)/2
\end{aligned}
$$
이므로 성립한다.

21-2. Induction (귀납 가정)

---

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

$$
\begin{aligned}
\sum_{i=1}^ni^t \leq n^t(n+1)/2
\end{aligned}
$$
가 성립한다고 하자.

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

---

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

$$
\begin{aligned}
\sum_{i=1}^ni^{t+1} \leq n^{t+1}(n+1)/2
\end{aligned}
$$

이므로

$$
\begin{aligned}
n \cdot \sum_{i=1}^ni^t &\leq n\cdot n^{t}(n+1)/2 \\
n\cdot\sum_{i=1}^ni^t &\leq n^{t+1}(n+1)/2 \\
\sum_{i=1}^ni^{t+1} &\leq n\cdot\sum_{i=1}^ni^t \\
1^{t+1}+ 2^{t+1} +...+n^{t+1} &\leq n(1^t+2^t+...+n^t) \\
0 &\leq 1^t(n-1) + 2^t(n-2)+...+n^t(n-n)
\end{aligned}
$$

이므로

$$
\begin{aligned}
\sum_{i=1}^ni^{t+1} &\leq n*\sum_{i=1}^ni^t \leq n^{t+1}(n+1)/2
\end{aligned}
$$

을 만족한다.
그러므로 n = k + 1일때도 만족한다.

22 Prove by induction on $n \geq 2$ that $$\sum_{i=1}^n\frac{1}{i^2} < 2 - \frac{1}{n}$$

22-1. Basis Condition

---

n = 2일 때 성립하는가?

$$
\begin{aligned}
\sum_{i=1}^2\frac{1}{i^2} &< 2 - \frac{1}{2} \\
1+\frac{1}{4} &< 2-\frac{1}{2} \\
\frac{3}{4} &< 1 \\
\end{aligned}
$$
이므로 성립한다.

22-2. Induction (귀납 가정)

---

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

$$
\begin{aligned}
\sum_{i=1}^{k}\frac{1}{i^2} < 2 - \frac{1}{k}
\end{aligned}
$$
가 성립한다고 하자.

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

---

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

$$
\begin{aligned}
\sum_{i=1}^{k+1}\frac{1}{i^2} < 2 - \frac{1}{k+1}
\end{aligned}
$$

이므로

$$
\begin{aligned}
\frac{1}{(k+1)^2}+\sum_{i=1}^{k}\frac{1}{i^2} &< \frac{1}{(k+1)^2} +2 - \frac{1}{k} \\
\sum_{i=1}^{k+1}\frac{1}{i^2} &< \frac{1}{(k+1)^2} +2 - \frac{1}{k} \\
2-\frac{1}{k+1} &> \frac{1}{(k+1)^2} +2 - \frac{1}{k} \\
-\frac{1}{k+1} &> \frac{1}{(k+1)^2} - \frac{1}{k} \\
-k(k+1) &> k-(k+1)^2\\
-k^2-k &> k -k^2-2k-1\\
0>-1\\
\end{aligned}
$$
이므로

$$
\begin{aligned}
\sum_{i=1}^{k+1}\frac{1}{i^2}<\frac{1}{(k+1)^2} +2 - \frac{1}{k} < 2 - \frac{1}{k+1}
\end{aligned}
$$

을 만족한다.
그러므로 n = k + 1일때도 만족한다.

해결못함

해결못함

해결못함

해결못함

23 Prove by induction on $n \geq 4$ is even, end $2 \leq i \leq n/2$,then $$\sum_{k=1}^i\prod_{j=1}^k(n-2j+1) \leq 2\prod_{j=1}^i(n-2j+1)$$

23-1. Basis Condition

---

n = 4일 때 성립하는가?

$$
\begin{aligned}
\sum_{k=1}^2\prod_{j=1}^k(4-2j+1) &\leq 2\prod_{j=1}^2(4-2j+1) \\
\sum_{k=1}^2\prod_{j=1}^k(5-2j) &\leq 2\prod_{j=1}^2(5-2j) \\
(5-2) + (5-2)(5-4) &\leq 2(5-2)(5-4) \\
3+3 &\leq 6\\
6 &\leq 6\\
\end{aligned}
$$
이므로 성립한다.

23-2. Induction (귀납 가정)

---

t 가 짝수이고

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

$$
\begin{aligned}
\sum_{k=1}^i\prod_{j=1}^k(t-2j+1) \leq 2\prod_{j=1}^i(t-2j+1)
\end{aligned}
$$
가 성립한다고 하자.

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

---

n 은 짝수이므로..

n = t + 2일 때를 증명해보자

$$
\begin{aligned}
2\prod_{j=1}^i(t-2j+1) &\\
j = a-1 치환\\
&=2\prod_{a=2}^{i+1}(t-2(a-1)+1) \\
&=2\prod_{a=2}^{i+1}((t+2)-2a+1) \\
&=\frac{2}{t+1}(t+2-2(i+1)+1)\prod_{a=1}^{i+1}((t+2)-2a+1) \\
&=\frac{2}{t+1}(t-2i+1)\prod_{a=1}^{i}((t+2)-2a+1) \\
\\
\frac{2}{t+1}(t-2i+1)\prod_{a=1}^{i}((t+2)-2a+1) &\leq 2\prod_{j=1}^i((t+2)-2j+1)\\
\frac{1}{t+1}(t-2i+1) &\leq 1\\
t-2i+1 &\leq t+1\\
0 &\leq 2i
\end{aligned}
$$

---

$$
\begin{aligned}
\sum_{k=1}^i\prod_{j=1}^k((t+2)-2j+1) &\leq 2\prod_{j=1}^i((t+2)-2j+1) \\
\sum_{k=1}^i\prod_{j=1}^k(t-2(j-1)+1) &\leq 2\prod_{j=1}^i(t-2(j-1)+1) \\
j-1 = a \\
\sum_{k=1}^i\prod_{a=0}^{k-1}(t-2a+1) &\leq 2\prod_{a=0}^{i-1}(t-2a+1) \\
(t+1)\sum_{k=1}^i\prod_{a=1}^{k-1}(t-2a+1) &\leq 2(t+1)\prod_{a=1}^{i-1}(t-2a+1) \\
\sum_{k=1}^i\frac{t+1}{t-2k+1}\prod_{a=1}^{k}(t-2a+1) &\leq 2\frac{t+1}{t-2i+1}\prod_{a=1}^{i}(t-2a+1) \\
\\
2\prod_{j=1}^i(t-2j+1) &\leq 2\frac{t+1}{t-2i+1}\prod_{a=1}^{i}(t-2a+1) \\
t-2j+1 &\leq \frac{t+1}{t-2i+1} \\
(t-2j+1)^2 &\leq t+1 \\
t^2-4jt+1 &\leq t+1 \\
t^2 &\leq (4j+1)t \\
t &\leq (4j+1) \\
2 \leq &i \leq t/2 이므로 \\

2\prod_{j=1}^i(t-2j+1) &\leq 2\prod_{j=1}^i((t+2)-2j+1)
\end{aligned}
$$

---

이므로

$$
\begin{aligned}
\sum_{k=1}^i\prod_{j=1}^k((t+2)-2j+1)&\leq \sum_{k=1}^i\prod_{j=1}^k(t-2j+1) \\
\sum_{k=1}^i\prod_{j=1}^k((t-2(j-1)+1)&\leq \sum_{k=1}^i\prod_{j=1}^k(t-2j+1) \\
j-1 = a치환\\
\sum_{k=1}^i\prod_{a=0}^{k-1}(t-2a+1)&\leq \sum_{k=1}^i\prod_{j=1}^k(t-2j+1) \\
\sum_{k=1}^i\frac{t+1}{t-2k+1}\prod_{a=1}^{k}(t-2a+1)&\leq \sum_{k=1}^i\prod_{j=1}^k(t-2j+1) \\
\frac{t+1}{t-2k+1}\\
\\
\\
\sum_{k=1}^i\prod_{j=1}^k((t+2)-2j+1) &\leq \frac{2}{t+1}(t-2i+1)\prod_{a=1}^{i}((t+2)-2a+1) \\
\prod_{j=1}^1((t+2)-2j+1) +\prod_{j=1}^2((t+2)-2j+1)+...+\prod_{j=1}^i((t+2)-2j+1) &\leq \frac{2}{t+1}(t-2i+1)\prod_{a=1}^{i}((t+2)-2a+1) \\
\prod_{j=1}^1((t+2)-2j+1) +\prod_{j=1}^2((t+2)-2j+1)+...+\prod_{j=1}^{i-1}((t+2)-2j+1) &\leq \frac{2}{t+1}(t-2i+1)\prod_{a=1}^{i}((t+2)-2a+1)-\prod_{j=1}^i((t+2)-2j+1) \\
\prod_{j=1}^1((t+2)-2j+1) +\prod_{j=1}^2((t+2)-2j+1)+...+\prod_{j=1}^{i-1}((t+2)-2j+1) &\leq (\frac{2}{t+1}(t-2i+1)-1)\prod_{a=1}^{i}((t+2)-2a+1)\\
\\
\frac{2}{t+1}(t-2i+1) \leq 2 \\\\

\end{aligned}
$$
이므로

$$
\begin{aligned}

\end{aligned}
$$

을 만족한다.
그러므로 n = k + 1일때도 만족한다.