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$
  • 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$ – Adam Hughes Jun 6 '16 at 16:13
  • $\begingroup$ why exactly divided by $4$ and could you elborate please $\endgroup$ – Educ Jun 6 '16 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$ – Adam Hughes Jun 6 '16 at 16:17
  • $\begingroup$ @AdamHughes Thanks $\endgroup$ – Educ Jun 6 '16 at 18:35
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$
  • $\begingroup$ Thanks but Why they took the Euclidean division of n by LCM of the denominators $\endgroup$ – Educ Jun 6 '16 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$ – Ross Millikan Jun 6 '16 at 18:13
  • $\begingroup$ could you add that in ur answer and adding example for it please $\endgroup$ – Educ Jun 6 '16 at 18:28
  • $\begingroup$ could you add example for that please $\endgroup$ – Educ Jun 6 '16 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$ – Ross Millikan Jun 6 '16 at 18:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.