2.3 FLOORS AND CEILINGS

2.3 FLOORS AND CEILINGS

Suppose x ∈ IR+.The floor of x, denoted x
, is defined to be the largest integer that is no larger than x.The ceiling of x, denoted x, is defined to be the smallest
integer that is no smaller than x.

24 Prove by induction on $n \geq 0$ that $$\left \lfloor \frac{n}{2} \right \rfloor = \begin{cases}n/2 &\text{if n is even} \\(n-1)/2 & \text{if n is odd}\end{cases}$$

24-1. Basis Condition

---

n = 0일 때 성립하는가?

$$
\begin{aligned}
\left \lfloor \frac{0}{2} \right \rfloor &=
\begin{cases}
0/2 &\text{if n is even} \\
(0-1)/2 & \text{if n is odd}
\end{cases}
\\
&=0
\end{aligned}
$$
이므로 성립한다.

24-2. Induction (귀납 가정)

---

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

$$
\begin{aligned}
\left \lfloor \frac{k}{2} \right \rfloor &=
\begin{cases}
k/2 &\text{if n is even} \\
(k-1)/2 & \text{if n is odd}
\end{cases}
\end{aligned}
$$
가 성립한다고 하자.

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

---

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

1. k가 짝수일 때
   $$
   \begin{aligned}
   \left \lfloor \frac{k+1}{2} \right \rfloor &=
   \begin{cases}
   (k+1)/2 &\text{if n is even} \\
   ((k+1)-1)/2 & \text{if n is odd}
   \end{cases}
   \\
   &=(k+1)/2
   \end{aligned}
   $$
   (k+1)/2 는 자연수 이고, (k+1)/2보다 크지 않은 자연수를 반환하므로
   참이다.

2. k가 홀수일 때
   $$
   \begin{aligned}
   \left \lfloor \frac{k+1}{2} \right \rfloor &=
   \begin{cases}
   (k+1)/2 &\text{if n is even} \\
   ((k+1)-1)/2 & \text{if n is odd}
   \end{cases}
   \\
   &= ((k+1)-1)/2
   \end{aligned}
   $$
   $(k+1)/2$ 는 자연수가 아니므로,

$(k+1)//2 + 0.5$ 형태가 된다.

$(k+1)//2 + 0.5$ 보다 크지 않은 자연수의 최댓값은
$(k+1)//2 - 0.5$ 즉 $k//2$ 가 된다.

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

25 Prove by induction on $n \geq 0$ that $$\left \lceil \frac{n}{2}\right \rceil = \begin{cases}n/2 &\text{if n is even} \\(n+1)/2 &\text{if n is odd}\end{cases}$$

25-1. Basis Condition

---

n = 0일 때 성립하는가?

$$
\begin{aligned}
\left \lceil \frac{0}{2}\right \rceil &=
\begin{cases}0/2
&\text{if n is even}
\\(0+1)/2 &\text{if n is odd}
\end{cases}
\\
&=0
\end{aligned}
$$
이므로 성립한다.

25-2. Induction (귀납 가정)

---

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

$$
\begin{aligned}
\left \lceil \frac{k}{2}\right \rceil =
\begin{cases}k/2
&\text{if n is even}
\\(k+1)/2 &\text{if n is odd}
\end{cases}
\end{aligned}
$$
가 성립한다고 하자.

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

---

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

1. k+1이 짝수일 때
   $$
   \begin{aligned}
   \left \lceil \frac{k+1}{2}\right \rceil =
   \begin{cases}(k+1)/2
   &\text{if n is even}
   \\((k+1)+1)/2 &\text{if n is odd}
   \end{cases}
   \end{aligned}
   $$
   $(k+1)/2$ 는 자연수 이고,

$(k+1)/2$보다 작지 않은 자연수 최솟값을 반환하므로

참이다.

2. k+1이 홀수일 때
   $$
   \begin{aligned}
   \left \lceil \frac{k+1}{2}\right \rceil =
   \begin{cases}(k+1)/2
   &\text{if n is even}
   \\((k+1)+1)/2 &\text{if n is odd}
   \end{cases}
   \end{aligned}
   $$
   $(k+1)/2$ 는 자연수가 아니므로,

$(k+1)//2 + 0.5$ 형태가 된다.

$(k+1)//2 + 0.5$ 보다 작지 않은 자연수 최솟값은

$(k+1)/2 + 0.5$

즉 $(k+2)//2$ 가 된다.

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

26 Prove by induction on $n \geq 1$ that for all $m \in \operatorname{R}^+$$$\begin{aligned}\left \lceil \frac{n}{m}\right \rceil &=\left \lfloor \frac{n+m-1}{m}\right \rfloor\end{aligned}$$

26-1. Basis Condition

---

n = 1일 때 성립하는가?

$$
\begin{aligned}
\left \lceil \frac{1}{m}\right \rceil &=
\left \lfloor \frac{1+m-1}{m}\right \rfloor
\\
\left \lceil \frac{1}{m}\right \rceil &=
\left \lfloor \frac{1}{m}+\frac{m}{m}-\frac{1}{m}\right \rfloor
\\
\left \lceil \frac{1}{m}\right \rceil &=
\left \lfloor \frac{m}{m}\right \rfloor
\\
\left \lceil \frac{1}{m}\right \rceil &=
\left \lfloor 1\right \rfloor
\\
\end{aligned}
$$
$\left \lceil \frac{1}{m}\right \rceil = 1$ 이므로

m이 1일 때 성립한다.

26-2. Induction (귀납 가정)

---

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

$$
\begin{aligned}
\left \lceil \frac{k}{m}\right \rceil &=
\left \lfloor \frac{k+m-1}{m}\right \rfloor
\end{aligned}
$$

가 성립한다고 하자.

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

---

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

$$
\begin{aligned}
\left \lceil \frac{(k+1)}{m}\right \rceil &=
\left \lfloor \frac{(k+1)+m-1}{m}\right \rfloor
\\
\left \lceil \frac{k+1}{m}\right \rceil &=
\left \lfloor \frac{k+m}{m}\right \rfloor
\\
\left \lceil \frac{k}{m} + \frac{1}{m}\right \rceil &=
\left \lfloor \frac{k}{m}+1\right \rfloor
\end{aligned}
$$

---

$$
\begin{aligned}
\frac{k}{m} &= d_l+r\text{이라 하자}
\\
0 &\leq r < 1
\\
\left \lfloor \frac{k}{m}+1\right \rfloor &=
d_l + 1이다.
\\
\left \lceil \frac{k}{m} + \frac{1}{m}\right \rceil &=
d_l +\left \lceil r + \frac{1}{m}\right \rceil
\\
\frac{1}{m} &= \frac{d_l+r}{k}
\\
\left \lceil r + \frac{1}{m}\right \rceil &=
\left \lceil \frac{d_l+r+k_r}{k}\right \rceil
\\
0 < \frac{d_l+r+k_r}{k} &< \frac{1+d_l+k_r}{k}
\\
\frac{1+d_l+k_r}{k} &\leq 1
\\
1+d_l+k_r &\leq k
\\
1+d*l &\leq k(1-r)
\\
\end{aligned}
$$

참이다.

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