I tried to prove the part c) of "Problem 42" from the book "Algebra" by Gelfand.
Fractions $\frac{a}{b}$ and $\frac{c}{d}$ are called neighbor fractions if their difference $\frac{cb-ad}{db}$ has numerator ±1, that is, $cb-ad = ±1$. Prove that:
b) If $\frac{a}{b}$ and $\frac{c}{d}$ are neighbor fractions, then $\frac{a+c}{b+d}$ is between them and is a neighbor fraction for both $\frac{a}{b}$ and $\frac{c}{d}$.
Me: It is easy to prove.
c) no fraction $\frac{e}{f}$ with positive integer $e$ and $f$ such that $f < b+d$ is between $\frac{a}{b}$ and $\frac{c}{d}$.
Me: we know that $\frac{a+c}{b+d}$ is between $\frac{a}{b}$ and $\frac{c}{d}$. The statement says that if we make the denominator smaller than $b+d$, the fraction can't be between $\frac{a}{b}$ and $\frac{c}{d}$ with any numerator.
Let's prove it:
0) Assume that $\frac{a}{b}$ < $\frac{c}{d}$, and $cb-ad = 1$, ($cb = ad + 1$). I also assume that $\frac{a}{b}$ and $\frac{c}{d}$ are positive.
1) Start with the fraction $\frac{a+c}{b+d}$, let $n$ and $m$ denote the changes of the numerator and denominator, so we get $\frac{a+c+n}{b+d+m}$ ($n$ and $m$ may be negative). We want it to be between the two fractions: $\frac{a}{b} < \frac{a+c+n}{b+d+m} < \frac{c}{d}$
2) Let's see what the consequences will be if the new fraction is bigger than $\frac{a}{b}$:
$\frac{a+c+n}{b+d+m} > \frac{a}{b}$
$b(a+c+n) > a(b+d+m)$
$ba+bc+bn > ba+ad+am$
$bc+bn > ad+am$
but $bc = ad + 1$ by the definition, so
$(ad + 1) + bn > ad + am$
$bn – am > -1$
All the variables denote the natural numbers, so if a natural number is bigger than -1 it implies that it is greater or equal $0$.
$bn – am \geq 0$
3) Let's see what the consequences will be if the new fraction is less than $\frac{c}{d}$:
$\frac{a+c+n}{b+d+m} < \frac{c}{d}$
…
$cm – dn \geq 0$
4) We've got two equations, I will call them p-equations, because they will be the base for our proof (they both have to be right):
$bn – am \geq 0$
$cm – dn \geq 0$
5) Suppose $\frac{a}{b} < \frac{a+c+n}{b+d+m} < \frac{c}{d}$. What $n$ and $m$ have to be? It was conjectured that if $m$ is negative, so for any $n$ this equation would not be right. Actually if $m$ is negative, $n$ can be only less or equal $0$, because when the denominator is getting smaller, the fraction is getting bigger.
6) Suppose that $m$ is negative and $n = 0$. Then the second p-equation can't be true:
$-cm – d\cdot 0 \geq 0 \implies -cm \geq 0$
7) If both n and m are negative, the p-equations can't both be true. I will get rid of the negative signs so we can treat $n$ and $m$ as positive:
$(-bn) – (-am) \geq 0$
$(-cm) – (-dn) \geq 0$
$am – bn \geq 0$
$dn – cm \geq 0$
If something is greater or equal $0$ then we can multiply it by a positive number and it still will be greater or equal $0$, so multiply by $d$ and $b$:
$d(am – bn) \geq 0$
$b(dn – cm) \geq 0$
$da\cdot m – dbn \geq 0$
$dbn – bc\cdot m \geq 0$
But $bc$ is greater than $da$ by the definition. You can already see that the equations can't both be true, but I will show it algebraicly:
by the definition $bc = da + 1$, then
$dam – dbn \geq 0$
$dbn – (da + 1)m \geq 0$
$dam – dbn \geq 0$
$dbn – dam – m \geq 0$
If two equations are greater or equal $0$ than if we add them together, the sum will still be greater or equal $0$.
$(dam – dbn) + (dbn – dam – m) \geq 0$
$-m \geq 0$
It is impossible (I changed $n$ and $m$ from negative to positive before by playing with negative signs).
QED.
If $n$ and $m$ are positive, the p-equations can both be true, I won't go through it here because it is irrelevant to our problem. But it is the common sense that I can choose such big $n$ and $m$ to situate $\frac{a+c+n}{b+d+m}$ between any two fractions.
PS: maybe my proof is too cumbersome, but I want to know is it right or not. Also advices how to make it simpler are highly appreciated.
Best Answer
First of all, the proof is correct and I congratulate you on the excellent effort. I will only offer a few small comments on the writing.
It's not clear until all the way down at (5) that you intend to do a proof by contradiction, and even then you never make it explicit. It's generally polite to state at the very beginning of a proof if you plan to make use of contradiction, contrapositive, or induction.
Tiny detail, maybe even a typo: $n$ and $m$ are integers, not necessarily naturals, so the statement at the end of (2) needs to reflect that. But for integers, also $x>-1$ implies $x\geq 0$, so it's not a big deal.
You didn't really need to make $n$ and $m$ positive since the only place you use positivity is at the very, very end you need $m>0$ to derive the contradiction. You don't even use it when you multiply by $d$ since that relied on the expressions being positive and not the individual numbers themselves. This is the only place I can imagine really see simplifying the proof.
As it stands, it would make the reader more comfortable if you named the positive versions of $(n,m)$ as $(N,M)$ or $(n',m')$ or something.
Finally, as you hint at, you don't need to consider the positive-positive case. But perhaps you should be more explicit why this is, earlier in the proof.