August 2007
<<July August September>>
Ponder This Solution:
The sequence {f(n)/f(n-1)} for positive integers n-s covers all the positive rational numbers in reduced form.
If n is odd (=2m+1), from the definition of f(n) (modulo 2) we get that 1 (=2^0) appears exactly once and hence
(1a) f(2m+1) = f(m).
If n is even (=2m), 1 either does not appear at all or appears twice. In the first case, we get f(m) possibilities and in the second we get f(m-1). Therefore,
(1b) f(2m)=f(m)+f(m-1).
Clearly f(n)>0 and therefore
(2) f(2n-1) = f(n-1) < f(n-1)+f(n) = f(2n).
Claim 1: gcd(f(n),f(n-1))=1
Proof: By induction on n. The base (n=1) is trivial: gcd(f(1),f(0))=gcd(1,1)=1
Suppose the induction hypothesis holds for k<n, then from (1a) & (1b):
gcd(f(n),f(n-1)) = gcd(f(2m+1),f(2m)) = gcd(f(m), f(m)+f(m-1)) = gcd(f(m),f(m-1)) = 1
or
gcd(f(n),f(n-1)) = gcd(f(2m),f(2m-1)) = gcd(f(m)+f(m-1), f(m-1)) = gcd(f(m),f(m-1)) = 1
qed.
Claim 2: f(n+1)/f(n) = f(n’+1)/f(n’) implies that n=n’
Proof: Again, by induction on max(n,n’). The base (max(n,n’)=0) is trivial since n=n’=0.
Assume the induction hypothesis holds for k<n, then from (2) we get that
f(n)/f(n-1) = f(n’)/f(n’-1) can only hold when n=n’(mod 2) and from (1a)&(1b) we get
f(m)/f(m-1) = f(m’)/f(m’-1) and by induction m=m’ yields n=n’.
qed.
Claim 3: For every positive rational number r, there exists a positive integer n such that r = f(n)/f(n-1).
Proof: Write r as a quotient of two relative prime natural numbers p and q.
We prove by induction on max(p,q).
The base (p=q=1) is trivial: n=1.
Assume the induction hypothesis holds for all k<n.
If p<q (q<p), then define r’ as p’/q’ where p’=p & q’=q-p (p’=q & q’=p-q). r’ satisfies the induction hypothesis and therefore r’ = f(m)/f(m-1). Hence r = f(2m+1)/f(2m) (f(2m)/f(2m-1))
qed.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com