»  Solutions to puzzles in my National Review Online Diary

—————————

Solution

An observation, then some exploration.

Observation:  The Fibonacci sequence is obviously going to figure in here somewhere. The length of the string S_n is F_n, by the rule of construction. (If, like me, you have trouble remembering how the Fibonacci sequence is indexed, the key is that F₅ = 5. Here just for reference, are the Fibonacci numbers F_n for n = 1 to 20:   1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765.)

Exploration:  Let's look at some actual values of the function we seek, for n = 1 to 100. When n is a Fibonacci number, I've noted the fact, just to see if it illuminates anything.

We sure do have some illumination. It looks as though the F_k -th "b" will be found at position F_k+1 when k is odd, and at position F_k+1 − 1 when k is even. (With a similar rule for the a's … but I'm going to ignore them from here on.)

What does this suggest? Let's bring in the golden ratio 1.6180339887498948482045868343 …, nowadays usually denoted by φ (the Greek letter phi).

This number φ is intimately connected with the Fibonacci sequence. For example: if you divide a Fibonacci number by the previous one, you get φ, plus or minus a small error that dwindles fast as you go along the sequence. So 13/8, for example, is 1.625, which differs from φ by less than half of one percent. A bit further along the sequence, 6765 divided by 4181 gives 1.6180339631667065295383879454 …, which differs from φ by less than one part in fifty million.

So those entries in the table for which n is a Fibonacci number show the position of the n-th "b" as being the next Fibonacci number, i.e. approximately φn. There's a good first guess as to the answer: The n-th "b" is at position φn. That can't be exactly right, of course, since φn is never a whole number (because φ is irrational), but from a quick exploration, it's not bad.

—————————

OK, let's get formal.

Our exploration turned up a very suggestive result for the position of the n-th "b" when n is a Fibonacci number. Alas, not every positive whole number is a Fibonacci number. It's not the position of the F_k -th "b" that we want, it's the position of the n-th "b" in general.

However, even though not every n is an F_k, Fibonacci theory offers us something almost as good: Zeckendorf's Theorem, which says that every positive whole number n is the sum of different non-consecutive Fibonacci numbers, F₁ excluded. (Since F₁ = F₂, including F₁ would foul up the "different" condition.)

(Zeckendorf's Theorem actually says slightly more than that, but that's all we need.)

More formally:

For any positive whole number n it is the case that n = F_p + F_q + F_r + …, where p, q, r, … are all different, no two are consecutive, and none is equal to 1.

(I'm actually going to assume here and from now on that p, q, r, … are in descending order. So for example 100 = F₁₁ + F₆ + F₄.)

That's one of the key facts we need — call it Fact I.

Here's another, Fact II. Suppose we have — as by the above-mentioned theorem we always can have — a decomposition of n into F_p + F_q + F_r + …, the p, q, r, … descending in size. Then by concatenating the strings S_p, S_q, S_r, …, in that order, I will get the first n positions of the golden string S_∞.

I shan't pause to prove Fact II. You can do a formal proof by induction, but it follows quite easily from the rules for constructing the strings.

So for example, 12 = 8 + 3 + 1, so 12 = F₆ + F₄ + F₂. Therefore the first 12 positions of the golden string are the concatenation of S₆, S₄, and S₂. If you concatenate those strings as I listed them above, in that order, and compare with the first 12 positions of S_∞, you will see that this is correct.

Here's yet another fact, Fact III. Recall the the length of the string S_k is F_k. How many of those F_k positions contain a "b"? The answer is F_k−1. You can check this out with the strings I started with, and it follows fairly immediately from the rules for constructing the strings.

Now for the last and biggest of my facts, Fact IV. The actual precise relation between the Fibonacci numbers and the golden ratio φ is this:

F_k  =  (φ^k − (−φ)^−k) / √5

There's a proof of that in my book Unknown Quantity, Endnote 35. It's a fundamental fact of Fibonacci theory though, and you should have no difficulty finding a proof on the net, if you're too damn cheap to buy my book.

Just writing k−1 in place of k gives this:

F_k-1  =  (φ^k−1 − (−φ)^−(k−1)) / √5

Those two results combined, after a bit of algebraic manipulation, give this:

F_k /φ =  F_k−1  + (−1)^k−1[φ^−(k−1) + φ^−(k+1)] / √5

I'm going to call that Fact IVa. It's the main key to the proof.

Go back to my number n. How many b's are there in the first n letters of S_∞?

Well, decompose n by Zeckendorf's Theorem into F_p + F_q + F_r + …. By Fact II and Fact III, the number of b's in those first n positions of S_∞ will be F_p−1 + F_q−1 + F_r−1 + ….

Now just add up all the statements of Fact IVa with k replaced in turn by p, q, r, …. The F_k's add up to n and the F_k−1's add up to the number of b's in the first n positions of S_∞!

The number of b's in the first n positions of S_∞ is not precisely what I'm looking for, but it sure seems like it would help. I'll call it C_b(n), read as "count of b's in the first n positions." Then adding up all those Fact IVa's got me this:

n/φ = C_b(n) + ∑{(−1)^k−1[φ^−(k−1) + φ^−(k+1)]} / √5

 … where the sum is taken over k = p, q, r, …

That sum looks a bit gruesome, but if you separate out the even and odd powers of −1, you just get two sums:  the first, with a minus sign in front, of a bunch of (φ^−s +φ^−t), where s and t are consecutive odd numbers, and the second, with a plus sign in front, of a bunch of (φ^−u +φ^−v), where u and v are consecutive even numbers.

Those are both finite sums; but since all the terms are positive, each is less than the corresponding infinite sum. I can work out the infinite sums using the rule  1 + x + x² + x³ + x⁴ + … = 1 / (1 − x)  together with the basic φ identities (φ² = φ + 1 helps a lot). I get answers −√5 / φ for the odd terms and √5 / φ² for the even.

So, since we've added up infinite series of which only some finite part is actually in play, it is certainly the case, substituting the lowest and highest possible results for the joint sum, that:

n/φ > C_b(n) − 1/φ

While also:

n/φ < C_b(n) + 1/φ²

That implies:

C_b(n) < (n + 1) / φ < C_b(n) + 1

A neater way to express that mathematically is:

C_b(n) = ⌊(n + 1) / φ⌋

Those partial brackets represent the floor function: ⌊x⌋ is the biggest whole number not bigger than x. For example, ⌊π⌋ = 3, and so is ⌊3⌋ = 3 (since 3 is not bigger than 3). However, ⌊−π⌋ = −4. (The floor function is actually called Floor in Mathematica, though it's Int in Visual Basic.)

That's not the final result, but the final result follows very easily, and I want my dinner.

Solution:   The n-th "b" of S_∞ occurs at position ⌊nφ⌋