# Check my proof of an algebraic statement about fractions

## 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.

-
Thomas Andrews gave a very elegant and short proof of this problem: math.stackexchange.com/questions/43455/… – Graduate Jan 3 '13 at 12:39

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.

-
Thanks, it helped a lot. – Graduate Jan 2 '13 at 9:21