induction « The Math Less Traveled

Posts Tagged ‘induction’

More hyperbinary fun

Monday, September 28th, 2009

Recounting the Rationals

When I originally posed Challenge #12, a certain Dave posted a series of comments with some explorations and partial solutions to part II (the hyperbinary sequence). Although I gave the “solution” in my last post, no solution to any problem is ever the last word—there’s always more to explore, more connections to see! It’s worth taking another post to explore some of Dave’s discoveries and conjectures, and how they connect to my last post. I’ve used different notations, made up some terms, tried to simplify things where possible, and so on, but all the ideas in this post are fundamentally Dave’s.

First things first

Dave first noticed that

h(2^k - 1) = 1

for all $k \geq 0$ . I noted this in my previous post as well, but said only that this is “apparent” from thinking about the recursive construction I described. However, it’s worth going through a proof of this more formally; it’s a good example of a proof by induction. First, let’s recall the recurrence relation that defines the hyperbinary sequence:

$\begin{align*}h(0) &= 1 \\ h(2n+1) &= h(n) && \text{(O)}\\ h(2n+2) &= h(n+1) + h(n) && \text{(E)}\end{align*}$

Now we can show that h(2^k - 1) = 1 for $k \geq 0$ . First, the base case: when k=0 , h(2^0 - 1) = h(0) = 1 ; check!

Now, let’s suppose that h(2^k - 1) = 1 for some particular $k \geq 0$ ; this is called the inductive hypothesis, which I will abbreviate as IH. we want to show that $h(2^{k+1} - 1) = 1$ as well. $2^{k+1} - 1$ is obviously odd, so we want to apply rule (O). The only trick is to get it into the right form first:

$\begin{align*}h(2^{k+1} - 1) &= h(2^{k+1} - 2 + 1) && \text{\{ arithmetic \}}\\ &= h(2(2^k - 1) + 1) && \text{\{ factor \}}\\ &= h(2^k - 1) && \text{\{ rule (O) \}} \\ &= 1 && \text{\{ IH \}}\end{align*}$

Presto! Since the thing we wanted to show is true when k=0 and is true for k+1 whenever it is true for , by induction it must be true for all $k \geq 0$ .

Second things, third things…

But Dave then went on to notice that this sort of pattern isn’t unique to 1. For example,

$h(3 \cdot 2^k - 1) = 2$

for $k \geq 0$ , and

$h(5 \cdot 2^k - 1) = h(7 \cdot 2^k - 1) = 3$

also for $k \geq 0$ . Dave conjectured that this generalizes, and indeed it does: most generally, we can say that

$h(p \cdot 2^k - 1) = h(p - 1)$

for $k \geq 0$ . That is, once a certain number occurs at position p - 1 , it will keep occurring in a regular pattern after that, at every position of the form $p \cdot 2^k - 1$ . Note that h(2^k - 1) = 1 is a special case with p = 1 .

Why is this? Intuitively, it’s because of the “copying”—the blue numbers in my previous post. Once a number occurs, it will keep getting copied, but with the distance between the copies doubling each time. But again, this is worth proving formally. I’ll let you do this one—the proof by induction is similar to the proof above!

But why do occurrences of 1 correspond to p = 1 , and occurrences of 2 to p = 3 , and occurrences of 3 to p = 5 and p = 7 , and so on? Are there any patterns to be found here? This is what Dave explored next; let’s follow.

Primary occurrences and the inverse of h

Let’s think a little more about this equation $h(p \cdot 2^k - 1) = h(p - 1)$ . Let’s suppose that is odd (if it isn’t, we can always take another factor of two out of it to combine with the 2^k ). Notice that $p \cdot 2^k - 1$ is always odd, except when k = 0 (in which case $p \cdot 2^k - 1 = p - 1$ , which is even). Moreover, we can always write any odd number in the form $p \cdot 2^k - 1$ , where is odd: just add one, and factor out as many copies of 2 as possible. For example, $11 = 12 - 1 = 3 \cdot 2^2 - 1$ .

This means that if is any odd number, we can write it in the form $q = p \cdot 2^k - 1$ , and so h(q) = h(p-1) : that is, every odd position in the hyperbinary sequence is just copied from an earlier even position. Of course, this can also be seen from the recursive construction in my previous post; but now we have really proved it! And what about the even positions? The values of the hyperbinary sequence at even positions are obtained by adding, rather than copying. If occurs at an even position, we will call it a primary occurrence of .

The nice thing about primary occurrences is that (a) there are only finitely many primary occurrences of any particular (challenge: prove this!), and (b) once we know the positions of the primary occurrences of , we know the positions of all the occurrences of : they are at positions of the form $p \cdot 2^k - 1$ , where p - 1 is a primary occurrence.

So, given , can we find all its primary occurrences? Essentially we are asking if we can compute $h^{-1}$ (by which I mean the inverse relation of ; since is not injective its inverse is obviously not a function), but leaving out non-primary occurrences since we can easily find those from primary ones. Let’s start by making a table with some small values of :

n	Primary occurrences
1	0
2	2
3	4, 6
4	8, 14
5	10, 12, 16, 30
6	32, 62
7	18, 22, 24, 28, 64, 126
8	20, 26, 128, 254
9	34, 46, 48, 60, 256, 510
10	38, 56, 512, 1022
11	36, 40, 54, 58, 66, 94, 96, 124, 1024, 2046
12	44, 50, 2048, 4094
13	42, 52, 70, 78, 112, 120, 130, 190, 192, 252, 4096, 8190
14	68, 80, 110, 122, 8192, 16382
15	72, 118, 258, 382, 384, 508, 16384, 32766
16	92, 98, 134, 158, 224, 248, 32768, 65534

Do you see any patterns? If so, can you prove them by induction? I’ll talk about a few in my next post. But I still don’t know whether there’s an effective way to compute $h^{-1}(n)$ !