# Prove by induction floor and ceiling

I couldn't solve below question ... I was able to start the solution .. but I couldn't turn left side to be same as write side in the inductive step:

• Note that there is a perfectly straightforward non-inductive proof. Requirement you to use induction is poor pædagogy. Dec 21, 2020 at 6:19

Hint: you only need to show

$$\left\lceil \frac{n+1}{m}\right\rceil - \left\lceil \frac nm \right\rceil = \left\lfloor \frac{n+m}{m} \right\rfloor - \left\lfloor \frac{n+m-1}{m}\right\rfloor$$

Now the LHS is either $$0$$ or $$1$$, usually $$0$$. So is the RHS.

When is LHS $$1$$? When is RHS $$1$$?

When $$\frac nm \in \mathbb N$$, both LHS and RHS are equal to 1. Otherwise they are both zeros. Therefore, $$\left\lceil \frac{n+1}{m}\right\rceil - \left\lceil \frac nm \right\rceil = \left\lfloor \frac{n+m}{m} \right\rfloor - \left\lfloor \frac{n+m-1}{m}\right\rfloor \tag1$$ $$\left\lceil \frac nm \right\rceil = \left\lfloor \frac{n+m-1}{m}\right\rfloor \text{ (from last step)} \tag 2$$ $$(1)+(2)$$, then we have $$\left\lceil \frac{n+1}{m}\right\rceil = \left\lfloor \frac{n+m}{m} \right\rfloor$$

• still not sure how to fit this in inductive proof? Dec 21, 2020 at 3:14
• Add $\lceil \frac nm \rceil = \lfloor \frac{n+m-1}{m} \rfloor$ Dec 21, 2020 at 3:16
• See my edit now. Dec 21, 2020 at 3:47
• That was explained in the line above (1). Dec 21, 2020 at 4:22
• Yes this is induction. On the contrary it's much easier to prove it without induction by just looking at the remainder when dividing $n$ by $m$. Dec 21, 2020 at 12:47