Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Letting $a_1,a_2,\cdots,a_r$ be integers which are larger than or equal to $2$, let us define $$[a_1,a_2,\cdots,a_r]=\cfrac{1}{a_1-\cfrac{1}{a_2-\cfrac{1}{\ddots-\cfrac{1}{a_r}}}}$$

(Note that the negative signs are used)

Also, let $X, Y, Z$ be positive integers which satisfy $$Z\lt X+Y,\ Z\gt X,\ Z\gt Y$$ and let $$\frac XZ=[a_1,a_2,\cdots,a_r],\ \frac YZ=[b_1,b_2,\cdots,b_s].$$

Then, here is my question.

Question : Is the following true?

"There exist $r^{\prime}\le r, s^{\prime}\le s$ such that $$[a_1,a_2,\cdots,a_{r^{\prime}}]+[b_1,b_2,\cdots,b_{s^{\prime}}]=1$$ for any $(X,Y,Z)$."

Remark : Observing the initial numbers is not sufficient because the nearer to $1$ the value $\frac XZ+\frac YZ$ is, the harder it is to find the answer (see example 2).

This question has been asked previously on math.SE without receiving any answers.

Examples :

  1. $\frac XZ=\frac 37=[3,2,2]$ and $\frac YZ=\frac 57=[2,2,3]$ leads $[3]+[2,2]=\frac 13+\frac 23=1$ where $\frac 37+\frac 57=\frac 87\approx 1.143$

  2. $\frac XZ=\frac{901}{2067}=[3,2,2,4,2]$ and $\frac YZ=\frac{1170}{2067}=[2,5,2,2,3]$ leads $[3,2,2,4]+[2,5,2,2]=\frac{10}{23}+\frac{13}{23}=1$ where $\frac XZ+\frac YZ=\frac{2071}{2067}\approx 1.002.$

Motivation : I've got an algorithm to find $b_1,b_2,\cdots,b_s$ such that $$1-x=[b_1,b_2,\cdots,b_s]$$ for any given $x=[a_1,a_2,\cdots,a_r]$.

Algorithm : Supposing that $2^r$ represents $r$-consecutive $2$s, I'm going to write $$[a_1,a_2,\cdots,a_r]=[2^{q_1},p_1,2^{q_2},p_2,\cdots,2^{q_s},p_s,2^{q_{s+1}}]$$ where $p_i\ge 3\in \mathbb N, q_i\ge 0\in \mathbb Z$. For example, $[2,2,5,3,2,4]=[2^2,5,2^0,3,2^1,4,2^0]$.

Then, the algorithm is $$1-[2^{q_1},p_1,2^{q_2},p_2,\cdots,2^{q_s},p_s,2^{q_{s+1}}]$$ $$=[(q_1+2),2^{(p_1-3)},(q_2+3),2^{(p_2-3)},(q_3+3),2^{(p_3-3)},\cdots,(q_s+3),2^{(p_s-3)},(q_{s+1}+2)].$$

After getting this algorithm, I reached the above expectation. I can neither find any counterexample even by using computer nor prove that the expectation is true. Can anyone help?

share|improve this question
    
What was the nature of your computer work? Did you do a systematic search of all fractions with denominator up to some $N$? –  Gerry Myerson Oct 16 '13 at 22:44
    
@GerryMyerson: Yes, but not all $N$ of course. –  mathlove Oct 17 '13 at 8:23
    
OK, so, how far up have you checked it? And did you see any patterns that might suggest that it's true in general? Also, are you assuming $\gcd(X,Z)=\gcd(Y,Z)=1$? –  Gerry Myerson Oct 17 '13 at 12:04
    
Just up to $N=100$. I noticed the following: If $[a_1,a_2,\cdots,a_r]+[b_1, b_2,\cdots,b_s]=1$, then $[a_1,a_2,\cdots,a_r,2]+[b_1,b_2,\cdots,b_s+1]=1$ though this may not be a reply to your question. Also, I'm not assuming that. –  mathlove Oct 17 '13 at 14:50
    
Thanks. The kind of pattern I had in mind is this: we may assume $X\lt Y$. If $X\ge Z/2$, then $1/2$ shows up as a convergent for both fractions, so we may assume $X\lt Z/2\lt Y$. Now, for certain ranges of $X$ and $Y$, $1/3$ will show up as a convergent for $X/Z$, and $2/3$ for $Y/Z$, so we can eliminate those ranges as possible sources of counterexamples. Then we can eliminate the ranges that lead to $1/4$ and $3/4$. And so on. Then we can look at what's left, and see which ranges of $X/Z$ and $Y/Z$ lead to which convergents summing to 1. And so on. –  Gerry Myerson Oct 17 '13 at 22:04

2 Answers 2

up vote 6 down vote accepted

The answer is YES even for numbers $\alpha$, $\beta$ of the form $\alpha=\frac X{Z_1}$, $\beta=\frac Y{Z_2}$. Suppose we look for convergents $\bar\alpha$, $\bar\beta$ to $\alpha$, $\beta$ such that $\bar\alpha+\bar\beta=1$.

If both numbers $\alpha$, $\beta$ are not less when $1/2$ an answer is trivial: $\bar\alpha=\bar\beta=1/2$. So we can assume that $\alpha<1/2$ and $\alpha+\beta>1$. It means that $$\tag{1}\alpha=[a-\alpha']$$ for some $a\ge 3$ and $\alpha'\in[0,1)$. Then $\alpha<\frac1{a-1}$ and $\beta>1-\alpha>1-\frac1{a-1}$. From last inequality follows that continued fraction expansion (CF) for number $\beta$ has the form $$\beta=[\underbrace{2,\ldots,2-\delta}_{a-2}]=\frac{a-2-(a-3)\delta}{a-1-(a-2)\delta}\tag{2}$$ with $\delta\in[0,1)$. If we have one more digit $2$ in CF for $\beta$ then we have a solution, because $$\bar\beta=[\underbrace{2,\ldots,2}_{a-1}]=\frac{a-1}{a}$$ and we can take $\bar\alpha=\frac 1a$.

If next digit in CF for $\beta$ is not equal to $2$, then $\delta=[b_1,b_2,\ldots]$, where $b_1\ge 3$. From (1) and (2) follows that inequality $\alpha+\beta>1$ equivalent to $$\alpha'+\beta'>1,$$ where $\alpha'$ is defined in (1) and $$\beta'=\frac{\delta}{1-\delta}=[b_1-1,b_2,\ldots].$$ The formula $\bar\alpha+\bar\beta=1$ is equivalent to $\bar\alpha'+\bar\beta'=1$, so we reduced our problem from $\alpha$, $\beta$ to simpler numbers $\alpha'$, $\beta'$.

share|improve this answer
    
Thank you very much for nice answer. –  mathlove Oct 18 '13 at 14:30
    
Are where any reasons beyond this question? –  Alexey Ustinov Oct 19 '13 at 9:00
    
Sorry, but I can't get what you mean. –  mathlove Oct 21 '13 at 14:39
    
Has this question arised as an auxiliary fact for something more serious? –  Alexey Ustinov Oct 22 '13 at 1:41
    
No. I found the property of this question just because I've been interested in continued fractions. –  mathlove Oct 22 '13 at 14:28

$\let\ds\displaystyle$Here is a different proof of the fact proven by Alexey Ustinov; it was found by Alexey Volostnov.

Assume that $[a_1,\dots,a_r]=\frac ab$, $[b_1,\dots,b_s]=\frac cd$, $\frac ab+\frac cd>1$, and $d\leq b$. We will prove that if we delete $a_r$ the resulting fractions will sum up to at least one; the conclusion follows. Notice that the case $r=1$ is impossible: otherwise we would have $\frac ab=\frac1{a_r}$ and $\frac cd\leq 1-\frac 1d\leq 1-\frac 1b=1-\frac ab$.

Let $\frac pq=[a_1,\dots,a_{r-1}]$, and assume that $\frac pq+\frac cd<1$. Then we have $\frac pq+\frac cd\leq 1-\frac 1{qd}$, $\frac ab+\frac cd\geq 1+\frac1{bd}$, and $aq-bp=1$. This implies $$ \frac 1{bq}=\frac ab-\frac pq\geq \frac1{bd}+\frac1{qd}, $$ in particular, $bq<qd$ and $b<d$. A contradiction.

share|improve this answer
    
Very nice solution –  Alexey Ustinov Nov 11 '13 at 2:49

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.