4

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.

JoeyAndres
  • 1,269
  • 1
    In case $n/2 \notin \Bbb Z$, then $\lfloor n/2\rfloor = (n-1)/2$, and likewise for the ceiling. You'll get rid of all those nasty floor / ceiling functions and can just compute it directly. – Arthur Jul 11 '14 at 11:21
  • $n$ is either even or odd. You have already proven the case when $n$ is even. If $n$ is odd, write $n= 2k+1$. – Yiyuan Lee Jul 11 '14 at 11:22
  • @Arthur Crap, I failed to divide in case when n is even or odd. Would've save a lot of time. Thanks – JoeyAndres Jul 11 '14 at 11:23

2 Answers2

9

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$

Wonder
  • 4,769
0

So you've got the case when $n$ is even. When $n$ is odd, then $\lfloor n/2 \rfloor * \lceil n/2 \rceil = \frac{n - 1}{2} * \frac{n + 1}{2} = \frac{n^2 -1}{4}$.

We want to show that this equals the right hand side. Since $n^2/4 = (n/2)^2$, we can rewrite $n^2/4$ as $(m + 1/2)^2$ where $m$ is an integer, and $m = \frac{n-1}{2}$. Furthermore, $(m + 1/2)^2 = m^2 + m + 1/4$.

Observe that $\lfloor m^2 + m + 1/4 \rfloor = m^2 + m$ since $m$ is an integer. Let's go write $m^2 + m$ in terms of $n$:

$m^2 + m = \frac{(n-1)^2}{2^2} + \frac{n-1}{2} = \frac{n^2 - 2n + 1}{4} + \frac{2n - 2}{4} = \frac{n^2 -1}{4}$.

I hope that's not too roundabout. The important thing was to show that flooring $n^2/4$ is the same as subtracting $1/4$.

NoName
  • 2,975