1993 USAMO Problems/Problem 4

Problem 4

Let $a$ , $b$ be odd positive integers. Define the sequence $(f_n)$ by putting $f_1 = a$ , $f_2 = b$ , and by letting $f_n$ for $n\ge3$ be the greatest odd divisor of $f_{n-1} + f_{n-2}$ . Show that $f_n$ is constant for $n$ sufficiently large and determine the eventual value as a function of $a$ and $b$ .

Solution

Part 1) Prove that $f_n$ is constant for sufficiently large $n$ .

Note that if there is some $f_n=f_{n-1}$ for any $n$ , then $\frac{f_{n}+f_{n-1}}{2}=f_n$ , which is odd. Thus, $f_{n+1}=f_n=f_{n-1}$ and by induction, all $f_p$ is constant for $p\ge n$ .

Also note that $f_n>0$ since average of $2$ positive number is always positive.

Thus, assume for contradiction, $\nexists n$ , $f_n=f_{n-1}$ .

Then, $f_{n+1}\le\frac{f_{n}+f_{n-1}}{2}< \max (f_{n},f_{n-1})$ , $f_{n+2}\le\frac{f_{n+1}+f_{n}}{2}< \max (f_{n},f_{n+1})\le\max (f_{n},f_{n-1})$

Thus, $\max (f_{n},f_{n-1})> \max (f_{n+1},f_{n+2})$ and that means that $\max (f_{2n},f_{2n+1})$ is a strictly decreasing function and it must reach $0$ as $n\rightarrow\infty$ , which contradict with the fact that $f_n>0$ .

Part 1 proven.

Part 2) Show that the constant is $\gcd(a,b)$ .

For any $f_n$ where $\gcd(a,b)=d\ne1$ . $f_n=dg_n$ for $g_n$ with the same property except with $g_1=\frac{a}{d}$ and $g_2=\frac{b}{d}$ .

Therefore, if I prove that the constant for any $f_n$ with relatively prime $a$ , $b$ is $1$ , then I have shown that part 2 is true.

Lemma) If $\gcd(f_n,f_{n-1})=1$ , then $\gcd(f_n,f_{n+1})=1$ .

Assume for contradiction that $\gcd(f_n,f_{n+1})=d\ne1$ , since both $f_n$ and $f_{n+1}$ are odd, $d$ is not divisible by $2$ .

$f_{n+1}=\frac{f_n+f_{n-1}}{2^n}$ for some $n\in \mathbb{Z}^+$ such that $f_{n+1}$ is odd.

$(2^n)f_{n+1}-f_n=f_{n-1}$

$d(p+q)=f_{n-1}$ , where $p$ and $q$ is another integer.

Thus, $f_{n-1}$ is divisible by $d$ which contradicts with the assumption that $\gcd(f_n,f_{n-1})=1$ .

Lemma proven

By induction, $\gcd(f_n,f_{n-1})=1$ since $\gcd(a,b)=\gcd(f_1,f_2)=1$ .

Since there must exist some $n$ where $f_n=f_{n+1}$ (part 1), $\gcd(f_n,f_{n+1})=f_n=1$ .

$\mathbb{Q.E.D}$

1993 USAMO (Problems • Resources)
Preceded by Problem 3	Followed by Problem 5
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

Page

Toolbox

Search

1993 USAMO Problems/Problem 4

Problem 4

Solution

See Also