1
$\begingroup$

Show that :$$ \forall \in \mathbb{Z}, \left\lfloor \dfrac{n-1}{2}\right\rfloor +\left\lfloor \dfrac{n+2}{4}\right\rfloor + \left\lfloor\dfrac{n+4}{4} \right\rfloor =n$$

Solution provide by book:

In separate cases, as the remainder of the Euclidean division of $n$ by $4$ and present the results in a table

\begin{array} {|r|r|r|r|} \hline n & \left\lfloor \dfrac{n-1}{2}\right\rfloor & \left\lfloor \dfrac{n+2}{4}\right\rfloor & \left\lfloor\dfrac{n+4}{4} \right\rfloor & \sum \\ \hline 4k & 2k-1 & k & k+1 & 4k \\ \hline 4k+1 & 2k & k & k+1 & 4k+1\\ \hline 4k+2 & 2k & k+1 & k+1 & 4k+2 \\ \hline 4k+3 & 2k+1 & k+1 & k+1 & 4k+3 \\ \hline \end{array}

This establishes the desired result by examining all cases modulo $4$

  • I didn't understand that solution which provided by Book could someone elaborate it Please ?

Reference

enter image description here

$\endgroup$
5
  • 1
    $\begingroup$ All the integers are of one of those forms, so you've just broken it up into cases based on how $n$ looks. $\endgroup$ Commented Jun 6, 2016 at 16:13
  • $\begingroup$ why exactly divided by $4$ and could you elborate please $\endgroup$
    – Educ
    Commented Jun 6, 2016 at 16:15
  • 1
    $\begingroup$ Because the largest denominator is $4$, so when you divide you know if the remainder is <1 or not, which is how the floor functions works. $\endgroup$ Commented Jun 6, 2016 at 16:17
  • $\begingroup$ @AdamHughes Thanks $\endgroup$
    – Educ
    Commented Jun 6, 2016 at 18:35
  • $\begingroup$ It would be slightly more accurate to say that the least common denominator is 4. $\endgroup$ Commented Oct 27, 2021 at 22:00

2 Answers 2

3
$\begingroup$

Because the least common multiple of the denominators is $4$, the effect of the floor functions will repeat with period $4$. You can convince yourself of this by trying $n$ from $0$ to $12$ or so. This means there are four cases depending on $n \bmod 4$ and they try all four cases. Each column in the middle of the table corresponds to one of the terms in the expression and they compute the value of that term,then add them up to get the last column. The fact that the first and last columns match establishes the identity. As and example, if $n=11,$ it is of the form $4k+3$ with $k=2$ Then $$\left\lfloor \dfrac{11-1}{2}\right\rfloor +\left\lfloor \dfrac{11+2}{4}\right\rfloor + \left\lfloor\dfrac{11+4}{4} \right\rfloor =5+3+3=11$$

Added per request: The point is that on adding one to nn exactly one of the floor functions will increase, maintaining the identity. Which one increases depends on $n \bmod 4$ Taking the LCM gets you through one cycle of the pattern.

$\endgroup$
6
  • $\begingroup$ Thanks but Why they took the Euclidean division of n by LCM of the denominators $\endgroup$
    – Educ
    Commented Jun 6, 2016 at 17:39
  • 1
    $\begingroup$ The point is that on adding one to $n$ exactly one of the floor functions will increase, maintaining the identity. Which one increases depends on $n \bmod 4$ Taking the LCM gets you through one cycle of the pattern. $\endgroup$ Commented Jun 6, 2016 at 18:13
  • $\begingroup$ could you add that in ur answer and adding example for it please $\endgroup$
    – Educ
    Commented Jun 6, 2016 at 18:28
  • $\begingroup$ could you add example for that please $\endgroup$
    – Educ
    Commented Jun 6, 2016 at 18:32
  • $\begingroup$ You should be able to do the calculations. I suggest making a spreadsheet and doing $n$ from $0$ through $12$ or $20$ or so. Compute the columns of the matrix you have and see how they work. $\endgroup$ Commented Jun 6, 2016 at 18:34
2
$\begingroup$

Uses Hermite’s identity $\lfloor x \rfloor =\left\lfloor\dfrac{x}{2}\right\rfloor+\left\lfloor\dfrac{x+1}{2}\right\rfloor$.

We have \begin{align*} \left\lfloor\dfrac{n+2}{4}\right\rfloor+\left\lfloor\dfrac{n+4}{4}\right\rfloor&=1+\left\lfloor\dfrac{\frac{n}{2}}{2}\right\rfloor+\left\lfloor\dfrac{\frac{n}{2}+1}{2}\right\rfloor\\ &=1+\left\lfloor\dfrac{n}{2}\right\rfloor \end{align*} Therefor \begin{align*} &\left\lfloor\dfrac{n-1}{2}\right\rfloor+\left\lfloor\dfrac{n+2}{4}\right\rfloor+\left\lfloor\dfrac{n+4}{4}\right\rfloor\\ =&\left\lfloor\dfrac{n-1}{2}\right\rfloor+1+\left\lfloor\dfrac{n}{2}\right\rfloor\\ =&\left\lfloor\dfrac{n+1}{2}\right\rfloor+\left\lfloor\dfrac{n}{2}\right\rfloor\\ =&n \end{align*}

$\endgroup$

You must log in to answer this question.

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