Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

1 Answer

up vote 6 down vote accepted

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.

share|improve this answer
    
Thanks, it helped a lot. –  Graduate Jan 2 '13 at 9:21
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.