Proving that Spec(α) and Spec(ß) partition positive integers iff α and ß are irrational and 1/α + 1/ß = 1 From Concrete Math, problem 3.13 asks:
"Let α and ß be positive real numbers. Prove that Spec(α) and Spec(ß) partition positive integers if and only if α and ß are irrational and 1/α + 1/ß = 1"
The solution claims:
"If they form a partition, the text's formula for N(α,n) implies that 1/α + 1/ß = 1, because the coefficients of n in the equation N(α,n) + N(ß,n) = n must agree if the equation is to hold for large n" (it goes on to the next part of the proof but I only care about this part)
In this chapter, they define Spec(α) to mean an infinite multiset of integers: $\{\lfloorα\rfloor,\lfloor2α\rfloor, ...\}$, and define N(α,n) to be the number of elements in Spec(α) that are $\le$ n. They show that N(α,n) = $\lceil(n+1)/α\rceil - 1$. They also show that a necessary condition for Spec(α) and Spec(ß) to partition the positive integers is N(α,n) + N(ß,n) = n  
I can write out the equation N(α,n) + N(ß,n) = n by substituting that equation:
$$\lceil(n+1)/ß\rceil + \lceil(n+1)/α\rceil - 2 = n$$
then converting to floor
$$\lfloor (n+1)/ß\rfloor + \lfloor (n+1)/α\rfloor = n$$
then splitting the floor into the fractional and actual part of its arguments
$$n(1/ß + 1/α) + 1/α + 1/ß - \{(n+1)/ß\} - \{(n+1)/α\} = n$$
...but, at that point, I don't see how I can conclude that 1/α + 1/ß = 1. I see that 1/α + 1/ß appears as a coeffecient of n, but there's the problem of the fractional stuff on the right. For their claim to be correct, the fractional parts would have to add up to 1 to cancel out the 1 from  1/α + 1/ß. I know that the fractional parts both have values less than one (since they are fractional parts of real numbers), but I don't see how to conclude that they sum to 1. Can I just claim that, since n appears on the right hand side with a coefficient of 1, that the coefficient for n on the left must be 1?
 A: The hint is in the phrase "for large $n$".
As you proved, we must have that for all $n$, 
$$n(1/\beta + 1/\alpha) + 1/\alpha + 1/\beta - \{(n+1)/\beta\} - \{(n+1)/\alpha\} = n.$$
Let us denote $1/\beta + 1/\alpha$ by $c$, to rewrite this as
$$nc + c - \{(n+1)/\beta\} - \{(n+1)/\alpha\} = n.$$
As $0 \le \{x\} < 1$ for all $x$ and here we have $\{(n+1)/\beta\} - \{(n+1)/\alpha\} = nc + c - n$, this means that
$$0 \le nc + c -n < 2.$$
Now consider what happens for very large $n$. If $c < 1$, then $nc + c - n = c - n(1-c)$ eventually becomes negative (in fact, it becomes negative for $n > \frac{c}{1-c}$), violating the "$0 \le$" inequality. And if $c > 1$, then for very large $n$, we'll have $nc + c - n > 2$: specifically, for $n > 2/(c-1)$, we'll have $nc + c - n > nc - n > 2$. So we must have $c = 1$.
Another way of writing the same thing is to divide $0 \le nc + c - n < 2$ by $n$ and say that $$0 \le c + \frac{c}{n} - 1 < \frac{2}{n},$$
and taking the limit as $n \to \infty$ gives $c - 1 = 0$, as it is sandwiched between the left- and right-limits, both equal to $0$.
A: Remember that the last equation holds for all positive integers $n$.
If, say, $1/\alpha + 1/\beta$ were greater than 1, then for sufficiently large $n$, the left side of the last equation would be bigger than the right.  (This is certainly true if we ignore the fractional parts, but even with the fractional parts, it's still true, because the 2 sides get farther and farther apart as $n \to \infty$ while the fractional parts remain bounded.)
A similar contradiction arises if $1/\alpha + 1/\beta$ were less than 1.
A: The set of positive integers equal to $[nx]$ for some $n$ (where $x > 1$ to avoid the trivial situation of covering all positive integers) has density $\frac{1}{x}$. If every number is covered exactly once by the $\alpha$ and $\beta$ sets, then the sum of their densities is $1$.
http://en.wikipedia.org/wiki/Natural_density
The rest of the proof can be found at 
http://en.wikipedia.org/wiki/Beatty_sequence
A: In chairbender's derivation, there is a minor error between the first two equations, which says 
$$\lceil(n+1)/β\rceil + \lceil(n+1)/α\rceil - 2 = n$$ 
becomes
$$\lfloor (n+1)/β\rfloor + \lfloor (n+1)/α\rfloor = n$$
He converted two ceiling expressions to flooring ones by subtracting 
from ceilings respectively. But this conversion is correct only if $\frac{n+1}{α}$ (and $\frac{n+1}{β}$) is non-integer for every n, which means α and β are both irrationals. But we can't guarantee that, in fact, the property of irrationality is what Knuth ask us to prove.

So we should use another method to express ceilings by factions.
$$\lceil\frac{n+1}{α}\rceil=-\lfloor-\frac{n+1}{α}\rfloor=- \Big( \big(-\frac{n+1}{α}\big)- \{ -\frac{n+1}{α} \}\Big)=\frac{n+1}{α}+\{ -\frac{n+1}{α} \}$$
$$\lceil\frac{n+1}{β}\rceil=-\lfloor-\frac{n+1}{β}\rfloor=- \Big( \big(-\frac{n+1}{β}\big)- \{ -\frac{n+1}{β} \}\Big)=\frac{n+1}{β}+\{ -\frac{n+1}{β} \}$$ 
so
$$\lceil \frac{n+1}{α} \rceil + \lceil \frac{n+1}{β} \rceil - 2 = n$$ implies $$\frac{n+1}{α} + \{ -\frac{n+1}{α} \} + \frac{n+1}{β} + \{ -\frac{n+1}{β} \} - 2 = n$$
The rest of the proof is almost the same, for details, please see ShreevatsaR's answer.
