Ponder This Challenge - August 2007 - Describe the sequence

Ponder This Challenge:

Define f(0)=1 and f(n) to be the number of different ways n can be expressed as a sum of integer powers of 2 using each power no more than twice.
For example, f(10)=5 since there are five different ways to express 10: 1+1+8, 1+1+4+4, 1+1+2+2+4, 2+4+4 and 2+8.
Describe, in a single sentence, the multiset {f(n)/f(n-1)} for positive integer n.
Show your proof to this sentence.

As usual, we ask that you only submit your original work.

UPDATE, 8/2/07: The solution is more elegant than just a recursion formula. You'll recognize it once you find it.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  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

Solvers

• Henry Bottomley (08.02.2007 @01:14:21 PM EDT)
• Alan Murray (08.02.2007 @03:19:18 PM EDT)
• Yang Frank (08.02.2007 @04:55:02 PM EDT)
• Jiri Navratil (08.02.2007 @06:06:34 PM EDT)
• Balakrishnan V (08.02.2007 @06:41:20 PM EDT)
• Ashutosh Mehra (08.02.2007 @06:46:31 PM EDT)
• Ramasamy Chandramouli (08.02.2007 @07:09:32 PM EDT)
• John T Robinson (08.02.2007 @08:34:12 PM EDT)
• Dan Dima (08.02.2007 @09:39:32 PM EDT)
• Irem Koprulu and Atilla Eryil (08.02.2007 @11:29:10 PM EDT)
• maz (08.02.2007 @11:29:10 PM EDT)
• Michael Quist (08.03.2007 @12:04:50 AM EDT)
• Graeme McRae (08.03.2007 @ 02:11:13 AM EDT)
• Albert Stadler (08.03.2007 @ 02:45:17 AM EDT)
• Daniel Bitin (08.03.2007 @ 07:07:35 AM EDT)
• Joseph DeVincentis (08.03.2007 @ 11:01:22 AM EDT)
• Michael Brand (08.04.2007 @12:20:00 AM EDT)
• Alexander Vardy (08.04.2007 @01:01:43 PM EDT)
• Celia Anteneodo (08.04.2007 @02:32:01 PM EDT)
• Harsha HS (08.05.2007 @02:09:23:22 AM EDT)
• Daniel Hsu (08.05.2007 @02:41:27 AM EDT)
• Harald Boegeholz (08.05.2007 @12:28:10 PM EDT)
• Philippe Fondanaiche (08.05.2007 @01:04:09 PM EDT)
• Ed Sheppard (08.05.2007 @03:24:01 PM EDT)
• Josh Boorstein (08.05.2007 @04:10:33 PM EDT)
• Gale Greenlee (08.05.2007 @08:07:17 PM EDT)
• John G. Fletcher (08.06.2007 @01:12:05 AM EDT)
• James Dow Allen (08.06.2007 @02:48:27 AM EDT)
• Christian Blatter (08.06.2007 @07:35:15 AM EDT)
• Arthur Breitman (08.06.2007 @10:57:25 AM EDT)
• Dr. Phil Muhm (08.06.2007 @11:15:37 AM EDT)
• Dion Harmon (08.06.2007 @11:26:09 AM EDT)
• Adel El-Atawy (08.06.2007 @03:56:18 PM EDT)
• Wei Zhou (08.06.2007 @08:02:49 PM EDT)
• Zhou Guang (08.07.2007 @03:40:45 AM EDT)
• Riyaaz Shaik (08.07.2007 @04:04:38 AM EDT)
• Adrian Atanasiu (08.07.2007 @7:25:47 AM EDT)
• Wang Tong (08.07.2007 @07:41:11 AM EDT)
• Cobus de Waal (08.07.2007 @09:38:11 AM EDT)
• Se Kwon Kim (08.07.2007 @12:42:45 PM EDT)
• Karl D’Souza (08.07.2007 @01:59:09 PM EDT)
• Dave Biggar (08.08.2007 @07:39:54 AM EDT)
• Roy John (08.09.2007 @07:07:56 AM EDT)
• David McQuillan (08.09.2007 @05:04:06 PM EDT)
• Parashar Dave (08.10.2007 @01:05:07 AM EDT)
• Andrew Buchanan (08.10.2007 @11:38:26 AM EDT)
• Øyvind Grotmol (08.11.2007 @06:30:31 AM EDT)
• Roger Thompson (08.13.2007 @02:58:43 AM EDT)
• José H. Nieto (08.13.2007 @06:51:50 AM EDT)
• Patricios Tlacaelel Alva Pufleau (08.13.2007 @06:35:30 PM EDT)
• Rajeev Rao (08.15.2007 @002:33:37 PM EDT)
• Abhisek Ukil (08.16.2007 @07:17:45 AM EDT)
• Clive Tong (08.16.2007 @11:24:26 AM EDT)
• Ionel Santa (08.16.2007 @03:09:34 PM EDT)
• Tom Gutman (08.16.2007 @03:56:25 PM EDT)
• Hongcheng Zhu (08.16.2007 @10:26:49 PM EDT)
• Martin Thiim (08.20.2007 @09:48:06 AM EDT)
• Suthambhara N (08.20.2007 @02:17:09 PM EDT)
• Jack Kennedy (08.21.2007 @05:46:55 AM EDT)
• Wolfgang Kais (08.21.2007 @09:01:54 AM EDT)
• Duane Bailey (08.21.2007 @05:11:39 PM EDT)
• Renato Fonseca (08.21.2007 @08:58:20 PM EDT)
• Balazs Ugron (08.22.2007 @07:38:49 AM EDT)
• Maxim G. Smith (08.22.2007 @01:18:27 PM EDT)
• Erik Hostens (08.23.2007 @04:11:41 AM EDT)
• Karthik Tadinada (08.23.2007 @10:56:31 AM EDT)
• Ervan Darnell (08.25.2007 @01:53:34 AM EDT)
• Changyuan Yu (08.26.2007 @04:29:34 AM EDT)
• David Friedman (08.26.2007 @10:38:23 AM EDT)
• Andreas Eisele (08.27.2007 @12:23:23 PM EDT)
• Bhaumik Chokshi (08.27.2007 @03:11:01 PM EDT)
• Guillaume de Longeaux (08.29.2007 @05:47:10 PM EDT)
• Dharmadeep Muppalla (08.31.2007 @07:46:00 AM EDT)