7
$\begingroup$

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:

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

  2. 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}$$

  3. Let's see what the consequences will be if the new fraction is bigger than $\frac{a}{b}$: \begin{align*} \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 \end{align*}

But $bc = ad + 1$ by the definition, so \begin{align*} (ad + 1) + bn & > ad + am\\ bn - am & > -1 \end{align*}

All the variables denote the natural numbers, so if a natural number is bigger than $-1$, it implies that it is greater or equal to $0$:$$bn - am \geq 0$$

  1. Let's see what the consequences will be if the new fraction is less than $\frac{c}{d}$: \begin{align*} \frac{a+c+n}{b+d+m} & < \frac{c}{d}\\ ...\\ cm - dn & \ge 0 \end{align*}

  2. 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):$$\begin{cases} bn - am \ge 0\\ cm - dn \ge 0\end{cases}$$

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

  4. Suppose that $m$ is negative and $n = 0$. Then the second p-equation can't be true:$$-cm - d\cdot 0 \ge 0 \implies -cm \ge 0$$

  5. 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: \begin{gather*} \begin{cases}(-bn) - (-am) \ge 0\\ (-cm) - (-dn) \ge 0\end{cases}\\ \begin{cases}am - bn \ge 0\\ dn - cm \ge 0\end{cases} \end{gather*}

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$: \begin{gather*} \begin{cases}d(am - bn) \ge 0\\ b(dn - cm) \ge 0\end{cases}\\ \begin{cases}da\cdot m - dbn \ge 0\\ dbn - bc\cdot m \ge 0\end{cases} \end{gather*}

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 \begin{gather*} \begin{cases}dam - dbn \ge 0\\ dbn - (da + 1)m \ge 0\end{cases}\\ \begin{cases}dam - dbn \ge 0\\ dbn - dam - m \ge 0\end{cases} \end{gather*}

If two equations are greater or equal $0$, than if we add them together, the sum will still be greater than or equal to $0$. \begin{align*} (dam - dbn) + (dbn - dam - m) & \ge 0\\ -m & \ge 0 \end{align*}

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.

$\endgroup$
1

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .