—————————

*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} = 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.

*n* |
Position of the *n*-th "a" |
Position of the *n*-th "b" |

*F*_{2} = 1 |
2 |
1 |

*F*_{3} = 2 |
5 |
3 |

*F*_{4} = 3 |
7 |
4 |

4 |
10 |
6 |

*F*_{5} = 5 |
13 |
8 |

6 |
15 |
9 |

7 |
18 |
11 |

*F*_{6} = 8 |
20 |
12 |

9 |
22 |
14 |

10 |
25 |
16 |

11 |
27 |
17 |

12 |
30 |
19 |

*F*_{7} = 13 |
34 |
21 |

14 |
36 |
22 |

15 |
39 |
24 |

16 |
41 |
25 |

17 |
44 |
27 |

18 |
47 |
29 |

19 |
49 |
30 |

20 |
52 |
32 |

*F*_{8} = 21 |
54 |
33 |

22 |
57 |
35 |

23 |
60 |
37 |

24 |
62 |
38 |

25 |
65 |
40 |

26 |
68 |
42 |

27 |
70 |
43 |

28 |
73 |
45 |

29 |
75 |
46 |

30 |
78 |
48 |

31 |
81 |
50 |

32 |
83 |
51 |

33 |
86 |
53 |

*F*_{9} = 34 |
89 |
55 |

35 |
91 |
56 |

36 |
94 |
58 |

37 |
96 |
59 |

38 |
99 |
61 |

39 |
102 |
63 |

40 |
104 |
64 |

41 |
107 |
66 |

42 |
109 |
67 |

43 |
112 |
69 |

44 |
115 |
71 |

45 |
117 |
72 |

46 |
120 |
74 |

47 |
123 |
76 |

48 |
125 |
77 |

49 |
128 |
79 |

50 |
130 |
80 |

51 |
133 |
82 |

52 |
136 |
84 |

53 |
138 |
85 |

54 |
141 |
87 |

*F*_{9} = 55 |
143 |
88 |

56 |
146 |
90 |

57 |
149 |
92 |

58 |
151 |
93 |

59 |
154 |
95 |

60 |
157 |
97 |

61 |
159 |
98 |

62 |
162 |
100 |

63 |
164 |
101 |

64 |
167 |
103 |

65 |
170 |
105 |

66 |
172 |
106 |

67 |
175 |
108 |

68 |
178 |
110 |

69 |
180 |
111 |

70 |
183 |
113 |

71 |
185 |
114 |

72 |
188 |
116 |

73 |
191 |
118 |

74 |
193 |
119 |

75 |
196 |
121 |

76 |
198 |
122 |

77 |
201 |
124 |

78 |
204 |
126 |

79 |
206 |
127 |

80 |
209 |
129 |

81 |
212 |
131 |

82 |
214 |
132 |

83 |
217 |
134 |

84 |
219 |
135 |

85 |
222 |
137 |

86 |
225 |
139 |

87 |
227 |
140 |

88 |
230 |
142 |

*F*_{9} = 89 |
233 |
144 |

90 |
235 |
145 |

91 |
238 |
147 |

92 |
240 |
148 |

93 |
243 |
150 |

94 |
246 |
152 |

95 |
248 |
153 |

96 |
251 |
155 |

97 |
253 |
156 |

98 |
256 |
158 |

99 |
259 |
160 |

100 |
261 |
161 |

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*_{1} excluded. (Since
*F*_{1} = *F*_{2}, including *F*_{1} 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*_{11} + *F*_{6} + *F*_{4}.)

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*_{6} +
*F*_{4} + *F*_{2}. Therefore the first 12 positions of the golden string are the concatenation of *S*_{6},
*S*_{4}, and *S*_{2}. 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*^{2} + *x*^{3} + *x*^{4} + …
= 1 / (1 − *x*) together with the basic *φ* identities
(*φ*^{2} = *φ* + 1 helps a lot). I get answers −√5 / *φ* for
the odd terms and √5 / *φ*^{2} 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/*φ*^{2}

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**φ*⌋