TAOCP 1.2.4 Exercise 6
Let n=\lfloor x\rfloor.
Section 1.2.4: Integer Functions and Elementary Number Theory
Exercise 6. ▶ [20] Which of the following equations are true for all positive real numbers $x$?
(a) $\lfloor \sqrt{\lfloor x \rfloor} \rfloor = \lfloor \sqrt x \rfloor$;
(b) $\lceil \sqrt{\lfloor x \rfloor} \rceil = \lceil \sqrt x \rceil$;
(c) $\lceil \sqrt{\lfloor x \rfloor} \rceil = \lfloor \sqrt x \rfloor$.
Verified: yes
Solve time: 7m16s
Solution
Let
$$ n=\lfloor x\rfloor. $$
Then
$$ n\le x<n+1. $$
We examine each statement.
(a) $\lfloor \sqrt{\lfloor x\rfloor}\rfloor=\lfloor \sqrt x\rfloor$
Since $\lfloor x\rfloor=n$, the left-hand side is
$$ \lfloor \sqrt n\rfloor. $$
Let
$$ m=\lfloor \sqrt n\rfloor. $$
By definition of the floor function,
$$ m\le \sqrt n<m+1, $$
hence
$$ m^2\le n<(m+1)^2. $$
Since $n$ is an integer and $n<(m+1)^2$, we have
$$ n+1\le (m+1)^2. $$
Combining this with $n\le x<n+1$, we obtain
$$ m^2\le n\le x<n+1\le (m+1)^2. $$
Therefore
$$ m^2\le x<(m+1)^2. $$
Taking square roots gives
$$ m\le \sqrt x<m+1. $$
Hence
$$ \lfloor \sqrt x\rfloor=m. $$
Since $m=\lfloor \sqrt n\rfloor$,
$$ \lfloor \sqrt x\rfloor = \lfloor \sqrt n\rfloor = \lfloor \sqrt{\lfloor x\rfloor}\rfloor. $$
Thus (a) is true for every positive real number $x$.
(b) $\lceil \sqrt{\lfloor x\rfloor}\rceil=\lceil \sqrt x\rceil$
This is not true for all $x$.
Take $x=1.01$. Then
$$ \lfloor x\rfloor=1, $$
so
$$ \left\lceil \sqrt{\lfloor x\rfloor}\right\rceil = \lceil \sqrt1\rceil = 1. $$
But
$$ \left\lceil \sqrt x\right\rceil = \left\lceil \sqrt{1.01}\right\rceil = 2, $$
since $\sqrt{1.01}>1$.
Therefore
$$ \left\lceil \sqrt{\lfloor x\rfloor}\right\rceil \ne \left\lceil \sqrt x\right\rceil. $$
So (b) is false.
(c) $\lceil \sqrt{\lfloor x\rfloor}\rceil=\lfloor \sqrt x\rfloor$
This is also not true for all $x$.
Take $x=2.1$. Then
$$ \lfloor x\rfloor=2, $$
and
$$ \left\lceil \sqrt{\lfloor x\rfloor}\right\rceil = \lceil \sqrt2\rceil = 2. $$
On the other hand,
$$ \lfloor \sqrt x\rfloor = \lfloor \sqrt{2.1}\rfloor = 1, $$
because $1<\sqrt{2.1}<2$.
Hence
$$ \left\lceil \sqrt{\lfloor x\rfloor}\right\rceil \ne \lfloor \sqrt x\rfloor. $$
So (c) is false.
Therefore the only identity that holds for all positive real numbers $x$ is
$$ \boxed{\text{(a) only}.} $$