Question
Use a proof by cases to show that $\lfloor n/2 \rfloor$ * $\lceil n/2 \rceil$ = $\lfloor \frac{n^2}{4} \rfloor$ for all integers $n$.
My Attempt:
I can only think of two cases,
- $n/2 \in \mathbb{Z}$
- $n/2 \notin \mathbb{Z}$
First case is straightforward:
$\lfloor n/2 \rfloor = \lceil n/2 \rceil = n/2$,
$\frac{n}{2}*\frac{n}{2} = \frac{n^2}{4}$
Second case troubled me,
$\lceil n/2 \rceil = \lfloor n/2 \rfloor + 1\\
\lceil n/2 \rceil = \lfloor n/2 + 1\rfloor$
$n/2 – 1 \leq \lfloor n/2 \rfloor < n/2\\
n/2 \leq \lfloor n/2 + 1 \rfloor < n/2 + 1$
I multiply both inequalities,
$\frac {n^2 – 2n}{4} \leq \lfloor n/2 \rfloor * \lfloor n/2 + 1 \rfloor < \frac{n^2 + 2n}{4}$
I need to prove that $\lfloor n/2 \rfloor * \lfloor n/2 + 1 \rfloor$ should be at least $n^2 /4$ and less than $n^2 /4 + 1$, this ensures that if I floor that, it will be $n^2/4$, but I'm lost.
My second attempt, (I didn't think the top have anywhere to go). This time I used some epsilon $\epsilon \in (0, 1)$,
$\lfloor n/2 \rfloor = n/2 – \epsilon\\
\lceil n/2 \rceil = n/2 + 1 – \epsilon$
$\lfloor n/2 \rfloor * \lfloor n/2 + 1 \rfloor = (n/2 – \epsilon)*(n/2 + 1 – \epsilon)\\
= n^2/4 + n/2 – n*\epsilon/2 – n*\epsilon/2 – \epsilon + \epsilon ^ 2\\
= n^2/4 + n/2 – 2n\epsilon/2 + 2\epsilon^2/2\\
= n^2/4 + \frac{n-2n\epsilon – 2\epsilon + 2\epsilon^2}{2}$
The problem now is I need to prove that $\frac{n-2n\epsilon – 2\epsilon + 2\epsilon^2}{2}$ is between 0 and 1. I don't really think this one is the solution is either so I gave up.
Best Answer
Why make it so complicated:
Case 1: n is even. Let n = 2k.
$\lceil n/2 \rceil \times \lfloor n/2 \rfloor = k * k = \lfloor n^2/4 \rfloor$
Case 2: n is odd. Let n = 2k + 1.
$\lceil n/2 \rceil \times \lfloor n/2 \rfloor = k (k + 1) = \lfloor n^2/4 \rfloor$ as $n^2/4 = (4k^2 + 4k + 1)/4 = k(k+1) + 1/4$