2
$\begingroup$

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:

enter image description here

enter image description here

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

1 Answer 1

1
$\begingroup$

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 $$

$\endgroup$
8
  • $\begingroup$ still not sure how to fit this in inductive proof? $\endgroup$
    – user836026
    Dec 21, 2020 at 3:14
  • $\begingroup$ Add $\lceil \frac nm \rceil = \lfloor \frac{n+m-1}{m} \rfloor$ $\endgroup$
    – Neat Math
    Dec 21, 2020 at 3:16
  • 1
    $\begingroup$ See my edit now. $\endgroup$
    – Neat Math
    Dec 21, 2020 at 3:47
  • 1
    $\begingroup$ That was explained in the line above (1). $\endgroup$
    – Neat Math
    Dec 21, 2020 at 4:22
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Neat Math
    Dec 21, 2020 at 12:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .