Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Sequences and Series > Recurrence Relations > Sums of Powers of 2

A periodic recurrence relation is one containing a cycle of infinitely repeating elements.

Sums of Powers of Two

Ponder this puzzle, August, 2007:

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.

Henceforth I will refer to such a partition of n as a "hyper-binary" partition.

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 sequence {f(n)/f(n-1)} for positive integer n.
Show your proof to this sentence.

 . . . . . . this needs to be edited to clean it up a bit.  Code fragments need to be put in monospace font and indented properly.

Initial research

Using Excel, I converted numbers 0,1,2,... to base three, and then interpreted the result as "hyper-binary", which means each place had a binary place value, but the digits can range from 0 to 2 instead of just 0 to 1. This allowed me to cycle through all of the ways to express numbers as sums of powers of 2 using each power no more than twice. I counted up the number of occurrences of each number, and then searched in OEIS for the resulting sequence. There, I found the following:

f(n) is OEIS A002487(n+1) ( http://www.research.att.com/~njas/sequences/A002487 ), which is described in OEIS as
Stern's diatomic series: a(0) = 0, a(1) = 1; for n >= 0, a(2n) = a(n), a(2n+1) = a(n) + a(n+1).

The second comment listed in the description of this sequence describes the sequence {a(n)/a(n+1)} as follows:
"a(n)/a(n+1) runs through all the reduced nonnegative rationals exactly once" which struck me as an interesting statement very close to the single-sentence description sought by this puzzle.

Understanding the Recurrence Relation

Now we see Stern's diatomic series is the same as our series except the index is off by one.  Thus we have discovered the recurrence relation that describes the number of hyper-binary partitions of n, namely

f(0)=1, for n>=1, f(2n+1) = f(n), f(2n) = f(n) + f(n-1)

But why should this be the case?

First, let's consider an arbitrary hyper-binary partition, A, of an odd number, 2n+1.  Clearly, A contains a single 1, because otherwise it could not be odd.  By deleting this 1, and dividing all the remaining elements in half, we're left with a unique partition, A', of n.  So we see there is a one-to-one correspondence between hyper-binary partitions of 2n+1 and hyper-binary partitions of n, i.e. f(2n+1)=f(n)

Next, let's consider an arbitrary hyper-binary partition of an even number, 2n.  If the partition contains a 1 then it contains two 1's, because 2n is even.  Let's consider both cases.  We'll let B be an arbitrary partition of 2n that does not contain any 1's, and we'll let C be an arbitrary partition of 2n that contains two 1's.

Since B contains no 1's, we can add a single 1 to it to form partition B', so there is a one-to-one correspondence of partitions of 2n without any 1's and partitions of 2n+1.

Since C contains two 1's, we can delete a single 1 from it to form partition C', so there is a one-to-one correspondence of partitions of 2n with two 1's and partitions of 2n-1.

Thus we see f(2n) = f(2n+1) + f(2n-1).

Well, we have already seen that f(2n+1)=f(n), and it's a short step to also realize that f(2n-1)=f(n-1), so we have our result for this case, namely f(2n) = f(n) + f(n-1), which proves the result.

Puzzle Solution

The corresponding statement for our question is, "The sequence {f(n)/f(n-1)} contains all the reduced nonnegative rationals exactly once."

A constructive proof of the statement will show (1) that f(n) and f(n-1) are coprime for all n, and (2) a function arcf exists such that given any positive coprime integers x,y arcf(x,y) exists, and f(arcf(x,y)-1)=x and f(arcf(x,y))=y, and for positive n, arcf(f(n-1),f(n))=n.

I start by proving Lemma 1, which provides a recursive definition of f: f(0)=1, for n>=1, f(2n+1) = f(n), f(2n) = f(n) + f(n-1).

Then I prove Lemmas 2 and 3, which prove the properties of f and arcf, essentially completing the proof. That arcf exists, i.e. it is defined for all coprime x,y, the "contains all reduced nonnegative rationals" part of the statement is proved. Since both f and arcf are injective, and each one is, in a sense, the inverse of the other, they are both bijective in that sense, which completes the proof of the "exactly once" part of the statement. The remainder of this document provides these proofs in detail.

Lemma 1

f(0)=1, for n>=1, f(2n+1) = f(n), f(2n) = f(n) + f(n-1)

I will refer to a "restricted partition" of n as a partition of n into powers of 2 using each power no more than twice.

In overview, the first part of this proof will show that any restricted partition of an odd number 2n+1 contains a single "1", so it can be converted to a restricted partition of n by deleting the 1 and dividing every other number in half. Conversely, a restricted partition of n can be converted to a restricted partition of 2n+1 by doubling every number and adding a "1".

The second part of this proof will show that every restricted partition of an even number has either two 1's or zero 1's. If it has two 1's, it can be converted to a restricted partition of the next-lower odd number by deleting one of the 1's. If it has zero 1's, it can be converted to a restricted partition of the next-higher odd number by adding a "1". Conversely, every odd restricted partition can be converted to a restricted partition of the neighboring lower even number by deleting a 1, and it can be converted to a restricted partition of the next higher even number by adding a 1. Then, by applying the first result, the result follows.

First part, in detail: Let a0, a1, a2,... represent the number of times 1, 2, 4, ... appear in a given restricted partition of 2n+1.
Since 2n+1 is odd, a0=1. Let b0=a1, b1=a2, ... Now b0, b1, b2, ... represents a corresponding restricted partition of n.
Now let b0, b1, b2,... represent any restricted partition of n. Let a0=1, a1=b0, a2=b1,... represent a corresponding restricted partition of 2n+1.
Thus the number of restricted partitions of 2n+1 is equal to the number of restricted partitions of n.

Second part, in detail: Let a0, a1, a2,... represent a restricted partition of 2n. Note that a0=0 or a0=2. Since b0=1, b1=a1, b2=a2,... is a restricted partition of an odd number neighboring 2n, we see that every restricted partition of an even number 2n corresponds to a restricted partition of one of 2n's odd neighbors. Conversely, let b0=1, b1, b2,... be a restricted partition of 2n-1 and let c0=1, c1, c2,... be a restricted partition of 2n+1. A one-to-one mapping can be made from the union of the sets of b0,b1,b2,... restricted partitions and c0,c1,c2,... restricted partitions by simply changing b0 to 2, and changing c0 to 0. Thus the number of restricted partitions of 2n is equal to the sum of the number of restricted partitions of 2n-1 and the number of restricted partitions of 2n+1. Using "f(n)" notation,

f(2n) = f(2n+1) + f(2n-1)

Now, applying the result from the first part of the proof to each of the terms on the right-hand side of this equation,

f(2n) = f(n) + f(n-1)

Lemma 2

f(n) and f(n-1) are coprime

Proof:

Outline of the proof: Assume the opposite for contradiction. Let n be the smallest positive integer such that f(n) and f(n-1) are not coprime. We know n is at least 2 because f(1) and f(0) are both 1 and thus coprime. Then I will show that f([n/2]) and f([n/2]-1) are also coprime contrary to our assumption.

Detailed proof: Suppose f(n) and f(n-1) share a common factor, k. Let r=[n/2].

Case 1: If n is even then f(n) = f(2r), and f(2r) = f(r) + f(r-1) by Lemma 1.
f(n-1) = f(2r-1), and f(2r-1) = f(r-1) by Lemma 1.

Case 2: If n is odd then f(n) = f(2r+1), and f(2r+1) = f(r), by Lemma 1.
f(n-1) = f(2r) = f(r) + f(r-1), by Lemma 1.

Thus, in either case, f(r)+f(r-1) divisible by k, and either f(r) or f(r-1) is divisible by k, so f(r-1) and f(r) are both divisible by k. r is positive and smaller than n, contradicting the choice of n as the smallest positive integer that makes f(n) and f(n-1) coprime.

Lemma 3

The arcf algorithm presented here (written in VBA) is such that given any positive coprime integers x,y arcf(x,y) exists, and f(arcf(x,y)-1)=x and f(arcf(x,y))=y. In addition, arcf(f(n-1),f(n))=n for all positive n.

Function arcf(ByVal x As Long, ByVal y As Long) As Long
Dim z As Long, result As Long
If x < 1 Or y < 1 Then Exit Function
z = 1
Do While x <> 0
If x >= y Then
x = x - y
result = result + z
Else
y = y - x
End If
z = z * 2
Loop
arcf = result
End Function

First, an overview of how arcf works. It repeatedly replaces the larger of x,y with |x-y|, keeping a binary string to "remember" which value was replaced. This continues until x=y, in which case x is replaced by the difference, 0, and the loop terminates. The binary string contains a "1" for every time x was replaced by the difference, and "0" for every time y was replaced by the difference. The binary string is interpreted as a base 2 number, with the first bit in the 1's place, the second in the 2's place, etc.

Proof of the first assertion, that arcf(x,y) exists as long as x and y are positive coprime integers: This is true because each iteration of the loop reduces x+y by some nonzero amount, never allowing x or y to become negative. This can't continue for ever, because at some point x+y would become zero. Before that happens, x would have to be zero, and this ends the loop. So no matter what input values are given, arcf terminates. As a practical matter, it terminates even if x and y aren't positive (it returns zero) and even if x and y are not coprime (it returns arcf(x/GCD(x,y),y/GCD(x,y))).

Proof of the second assertion that f(arcf(x,y)-1)=x and f(arcf(x,y))=y
Though this proof is a bit sketchy, you can think of it as either an induction proof or better yet a proof by contradiction. Suppose the second assertion is not always true. Then there exists an x,y for which it isn't true and x+y is minimal. Thus, for smaller x+y it is true, and this is used to show that it is also true for this x+y.

The following is evident from the algorithm when x,y are coprime:

if x=y then arcf(x,y) = 1
if x>y then arcf(x,y) = 2*arcf(x-y,y)+1
if x<y then arcf(x,y) = 2*arcf(x,y-x)

Thus if x>y,

f(arcf(x,y)-1) = f(2*arcf(x-y,y)) by the algorithm
= f(arcf(x-y,y))+f(arcf(x-y,y)-1) by Lemma 1
= y + (x-y)
= x
f(arcf(x,y)) = f(2*arcf(x-y,y)+1)
= f(arcf(x-y,y))
= y

And if x<y,

f(arcf(x,y)-1) = f(2*arcf(x,y-x)-1)
= f(arcf(x,y-x)-1)
= x
f(arcf(x,y)) = f(2*arcf(x,y-x))
= f(arcf(x,y-x))+f(arcf(x,y-x)-1)
= (y-x) + x
= y

Proof of the third assertion that arcf(f(n-1),f(n))=n, using a similar technique as the second assertion, above. Suppose n is the largest number for which arcf(f(k-1),f(k))=k whenever k<=n.

arcf(f(2n),f(2n+1)) = arcf(f(n)+f(n-1),f(n)) by Lemma 1
= 2*arcf(f(n-1),f(n))+1 by the algorithm
= 2n+1
arcf(f(2n-1),f(2n)) = arcf(f(n-1),f(n)+f(n-1))
= 2*arcf(f(n-1),f(n))
= 2n

Conclusion and general comments

A non-recursive implementation of the f function in VBA, called "frac1" here, is:

' f(0)=1, for n>=1, f(2n+1) = f(n), f(2n) = f(n) + f(n-1)
Function frac1(ByVal n As Long) As Long
Dim x As Long, y As Long, z As Long
x = 0: y = 1
If n < 0 Then Exit Function
If n < 65536 Then z = 32768 Else z = 1073741824
Do While z > 0
If n >= z Then x = x + y: n = n - z Else y = x + y
z = z \ 2
Loop
frac1 = y
End Function


This problem was one of the more delightful problems that has ever appeared in "Ponder This" because of the simplicity yet richness of the functions f and arcf. Thank you for presenting it.

The reason f(n) and f(n-1) are coprime is the same as the reason every pair of adjacent Fibonacci numbers are coprime -- because the recursion formula that defines the sequence is, in effect, the Euclidean algorithm, and the first two elements of the sequence are coprime -- which is true for both this sequence, f, and the Fibonacci sequence.

I was initially disappointed to find such a full detailed description of the function, f, in OEIS. At first, I was tempted to send you an email saying simply A002487, but then I realized that a proof was needed. I always prefer a constructive proof to an existence proof, so that led me to try to find where in the sequence of f(n)/f(n-1) any particular rational number might be found. The description of this sequence in OEIS suggests writing out a pyramid of values of f in a certain way, but I found it was much more instructive to write a "tree" of values of f. The tree is the same as the pyramid, but it's organized so that the left branch of every node brings you to an identical-value node. The binary sequence of branch selections (left=0, right=1) corresponds roughly to the value of arcf(x,y).

Finding arcf was a big breakthrough, because in so doing, I proved what I thought was the major part of the statement, that every rational is represented. It turned out that the "exactly once" part of the proof was a bit harder. For that, I had to show not only that f(arcf(x,y)-1)=x and f(arcf(x,y))=y but also that arcf(f(n-1),f(n)) = n, which wouldn't be the case if f(n-1),f(n) appeared in sequence more than once.

Additional information from OEIS

If the terms are written as an array:
1
1, 2
1, 3, 2, 3
1, 4, 3, 5, 2, 5, 3, 4
1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5
1, 6, 5, 9, 4,11, 7,10, 3,11, 8,13, 5,12, 7, 9, 2, 9, 7,12, 5,13, 8,11, 3,10, 7,11, 4, 9, 5, 6
then the sum of the k-th row is 3^(k-1), each columns is an arithmetic progression, and the steps are nothing but the original sequence.

Recursive formula for f(n):
f(n+1) = (2k+1)f(n) - f(n-1) where k = [f(n-1) / f(n)] is the largest integer smaller than or equal to f(n-1)/f(n)

 

Internet references

http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/rationals.pdf

Related pages in this website

Counting


The webmaster and author of this Math Help site is Graeme McRae.