I can't seem to prove propositions involving floor/ceiling function and the like..

What I know is: The floor function of $x$, denoted $[x]$, is the greatest integer smaller than $x$, ceiling of $x$ is the smallest integer greater than $x$. We define $\{x\} = x- [x]$, the factional part of x.

Till now all is okay and fine, but whenever I come across a proving question involving these type of functions, I can't even seem to get started.

I try to use extreme cases to disprove the statement if possible, but when it comes to proving, I'm just....lost. Like where do I even begin??

An example would be:

Proposition: For any real numbers $x, y,$ and $z$, prove that $[x + y + z] = [x + y] + [z + \{x + y\}]$.

I don't even know what to do with this except try and check it for some cases, which I already did.

Solution 1:

$\newcommand{\fl}[1]{\left \lfloor #1\right \rfloor}$ $\newcommand{\cl}[1]{\left \lceil #1\right \rceil}$ Let me first link to some fairly obvious identities involving the floor and ceiling function, which can be used to solve the given question very easily. The Wikipedia page for the floor and ceiling function contains these fundamental identities.

Essentially speaking, every identity in the article given follows from the definition of the floor function as $\fl{x}$ being the unique integer $k$ such that $k \leq x < k+1$.

For example, supposing you wanted to show that $\fl{x+n} = \fl{x}+n$ for any integer $n$ and real number $x$, then it suffices to see that $k \leq x < k+1$ if and only if $k+n \leq x+n < k+n+1$ for any $k$, so the unique $k$ for which the former statement is true, plus $n$, is the unique $k$ for which the latter statement is true. Of course, the unique $k$ for the former statement is $\fl{x}$ so $\fl{x}+n $ is the unique $k$ satisfying the latter statement i.e. $\fl{x+n} = \fl{x}+n$.

I loved William's answer above, but I felt it important to mention a result that isn't talked about very much, yet is extremely powerful. In particular, this can be used to prove identities involving the floor function very, very easily.

The point is, many people have asked this question before us : how do we make computations involving the floor and ceiling simpler? (People have also asked similar questions about making results involving the maximum/minimum of sets have easier proofs, rather than going case-by-case).

There is a rather magnificent tool that can be used very very nicely for this purpose. It's called the universal property of the floor (and ceiling) function. Basically speaking, for equating functions involving the floor and ceiling functions, one just needs to make manipulations dictated by the universal property.

The Universal Property

The universal property is the most obvious thing one can think of : for the floor function, let $x$ be real and $n$ be an arbitrary integer. Then, we know that : $$ n \leq x \iff n \leq \lfloor x \rfloor $$ This characterizes $\lfloor x \rfloor$ in the following sense : this quantity is decided by the set of natural numbers that lie below it.

Similarly, we have for the ceiling function : $$ n \geq x \iff n \geq \lceil x \rceil $$ so the quantity $\lceil x \rceil$ is decided by the integers that sit above it.

But how do we use the universal property? It is actually pretty simple : let's say you had to prove something like $\lfloor f(x) \rfloor = \lfloor g(x)\rfloor$ for two functions $f$ and $g$. The universal property tells you this : it's enough to prove for each integer $n$ and element $x$ that $n \leq f(x)$ if and only if $n \leq g(x)$.

How nice does this sound? Let's prove something.

Let's prove this remarkable theorem first : which gives us so, so many generalizations that I can't imagine how many questions could have been solved using this on this site!

A Remarkable Result

Let $f : \mathbb R \to \mathbb R$ have the following properties :

$f$ is continuous.

$f$ is strictly monotonically increasing and hence one-one.

$f^{-1}(n)$ , for any integer $n$, is either empty ($f$ can satisfy the above two conditions without being surjective) or is an integer. Then : $$ \lceil f(x)\rceil = \lceil f(\lceil x\rceil)\rceil \quad \text{and}\quad \lfloor f(x)\rfloor = \lfloor f(\lfloor x\rfloor)\rfloor $$
for all $x \in \mathbb R$.

What this means is quite simple : you can replace $x$ by $\lceil x\rceil$ (or floor of $x$) in such functions, and you'd not change the quantity!

Proof : Use the universal property, and let's do it just for the floor. Let $k$ be an arbitrary integer. Suppose that $k \leq f(\lfloor x \rfloor)$. Then since $x \geq \lfloor x\rfloor$ we get from monotonicity that $f(\lfloor x \rfloor) \leq f(x)$ so $k \leq f(x)$.

For the other direction : suppose that $k \leq f(x)$. Suppose that $f(\lfloor x \rfloor) < k \leq f(x)$.Then by the intermediate value theorem , there exists $y \in (\lfloor x \rfloor , x]$ such that $f(y) = k$. But then $f^{-1}(k)$ is not empty but $y$ is not an integer. Hence, it follows that $k \leq f(\lfloor x \rfloor)$ and we are done! $\blacksquare$

Let's see some fairly remarkable uses of this result.

With $f(x) = \sqrt x$ (note : this is for positive $x$ : the domain of real numbers can be suitably varied , the proof structure doesn't really depend upon the domain), which is continuous on $[0,\infty)$, one-one on the same interval and $f^{-1}(n) = n^2$ for any $n$, we get : $$ \lfloor \sqrt{x}\rfloor = \left\lfloor \sqrt{\lfloor x\rfloor}\right\rfloor $$ Looks difficult to prove otherwise? I'd like your thoughts.
With $f(x) = \frac {x+n}m$ for $m>0$, we get : $$ \fl{\frac {x+n}m} = \fl{\frac{\fl x + n}{m}} $$
Use iteration of the above theorem to prove the following result : for any positive integers $a_1,a_2...a_n$ we have : $$ \fl{\fl{\ldots \fl{\fl{x / a_1}/a_2} / \ldots} / a_n} = \fl{\frac x{a_1a_2....a_n}} $$

all these properties apply to the ceiling as well!

Interchange of ceil and floor

Let's see a slightly different property now : one for alternating between floor and ceiling functions.

For any $m$ integer and $n>0$ we have $$ \cl{\frac mn} = \fl{\frac{m+n-1}n} $$

Proof : Suppose that $k$ is an arbitrary integer. Then $k \leq \frac{m+n-1}{n}$ implies ,following rearrangement and factorization (pretty simple stuff that I leave to you to see) that $kn-n+1\leq m$, which (because they are all integers) happens if and only if $kn-n < m$, or $k-1 < \frac mn$, which is equivalent to $k \leq \cl{\frac mn}$(why?). Thus, we get from the universal property (for the floor) that $\fl{\cl{\frac mn}} = \fl{\frac{m+n-1}{n}}$, but the LHS is equal to $\cl{\frac mn}$, obviously.

Which gives a funny fascinating technique : introduce the floor of an integer just to apply the universal property! This can be used to flip between ceilings and floors in arguments.

Periodicity

Now, let's find a third technique for these kind of situations : I refer to it as periodicity. This basically says the following :

Given an identity, it's equivalent to proving that $f = 0$ for some $f$ once you transfer everything to one side. If this $f$ is found to be periodic, and found to be zero on one of the periodic intervals, then it's zero everywhere!

What a simple thought : but it's so profound.

Let's use it to prove the result above : that $[x+y+z] = [x+y] + [z+\{x+y\}]$.

Switch everything to one side : so that we have $[x+y+z] -[x+y] - [z+\{x+y\}]$. Increase $x$ by $1$ : then $[x+y+z]$ is up by $1$, $[x+y]$ is up by $1$ and $[z+\{x+y\}]$ doesn't change! So with respect to $x$, the function repeats upon addition of $1$ (it could be smaller, of course!).

With respect to $y$, it repeats by $1$ again. With respect to $z$ as well, as a matter of fact!

Because of this, it's enough to prove the result when $0 \leq x,y,z< 1$ : because the periodicity ensures that equality carries through everywhere.

But now we just have to literally look at two cases : $[x+y]=0$ and $[x+y]=1$, because $[x+y]$ can't be anything else. In the former case, we have $x+y = \{x+y\}$ so the identity is obvious. In the latter case we have ${x+y} = x+y-1$ and so you get the result once you realize that $[z-x-y+1] = [z-x-y]+1$.

(Note that , as in Hagen's answer, we could have used this technique directly).

But the point is, that there's much, much harder problems that can be handled through this absolutely brilliant technique. Let's see one of them.

Hermite's identity : for all $x \in \mathbb R$ and $n>0$ we have : $$ \sum_{k=0}^{n-1} \fl{x+ \frac kn} = \fl{nx} $$

How to prove this? Well, of course you can try the universal property, by taking a ceil on the LHS and then proceeding perhaps, but periodicity is so amazing!

Indeed, take everything to one side so $f(x) = \sum_{k=0}^{n-1} \fl{x+ \frac kn} - \fl{nx}$. Then, Moving forward $x$ by $\frac 1n$, note that $f(x)$ doesn't change : because exactly one of the terms in the summation will move forward by $1$ (for the unique $k$ for which $\fl{x+\frac kn} \neq \fl{x+ \frac{k+1}n}$) and that will be compensated by $\fl{nx+1} = \fl{nx}+1$, whence a $1$ gets subtracted.

So it's enough to prove this when $0 \leq x < \frac 1n$. But in that case, it's terribly obvious that every term in the summation is zero, and $\fl{nx} = 0$. Done!

So the takeaways are :

The universal property and the theorem.
The ceil-floor flip relation.
The periodicity trick.

These, along with standard fundamental results mentioned here will take you a long, long way in handling such identities with fluid ease.

Solution 2:

You ask for a general toolkit to prove these kinds of questions.

I will give an answer in two forms.

First, it's worth remembering (or understanding) a suite of facts about $\text{Floor}$. This includes, but it not limited to:

$\lfloor x \rfloor + \{x\} = x$ (this is by definition)
$\lfloor x \rfloor = \max \{ m \in \mathbb{Z} : m \leqslant x\}$ (in some cases, this is the definition of $\text{Floor}$. It's useful for the most elementary of problems)
$\lfloor x + z \rfloor = \lfloor x \rfloor + z \Longleftrightarrow z \in \mathbb{Z}$ (this is good for breaking up problems, as in Hagen von Eitzen's answer)
$\lfloor x + y\rfloor \geq \lfloor x \rfloor + \lfloor y \rfloor $ (can you see why this is? Check cases where $\{x\},\{y\} > 1/2$)
$\lfloor x \rfloor \leq x$ (this one seems obvious, but is important when dealing with integer bounds. It makes more sense to say the number of elements of a set at most $\lfloor r\rfloor $ rather than some real number $r$.)

The second way I will answer this question may be less satisfying. These kind of elementary problems often have one most direct way to solve it, with other ways being valid, but seen as inferior. If I can do a proof in three steps, or do it in 6 steps with those three steps secretly in it, one would see the second way as more elegant. It takes practice to be able to be see this quickest way, and there is rarely, if ever, a way to develop this intuition other than doing problems.

I will use Hagen von Eitzen's answer as a kind of paradigmatic example. What they did was:

Run with a few test cases (presumably. Practiced mathematicians sometimes skip this step, but I certainly don't!)
See what structure is exposed in the test cases.
Think about how to describe this structure with mathematical fact.

This third step is the hardest of all. Often times the most obvious thing is the hardest to prove rigorously, simply because you don't know how to even put it into different words! Steps (2) and (3) will also vary wildly from object to object. As we are working with a function going into the integers, one of the most obvious points of structural limitation is looking at where your argument can "break" into integral and fractional parts. Another structural limitation is that you can only make really good inferences with inequalities and substitutions, since we're working purely arithmetically. A good proof for an arithmetical problem will use words sparingly to explain steps; the actual meat of the proof will be found in substitutions, identities, and bounds.

Translate your argument into this mathematical argument, and write it down.

This is what Hagen von Eitzen did. They saw a useful way to break up the fractional and integral parts (which is often a key step in these kinds of proofs), and then found a useful substitution into identities which we know are true.