Great question! Let's break this down with recursion and symmetry to see exactly why the number of valid binary strings matches twice the nth Fibonacci number.

First, let's define some terms to make this clearer:

• Let f(n) = the number of valid length-n binary strings (where every run of 0s or 1s has odd length).
• We'll use the Fibonacci sequence definition where Fib(1) = 1, Fib(2) = 1, Fib(3) = 2, Fib(4) = 3, etc. (the standard "classical" Fibonacci starting point).

Step 1: Initial Conditions #

Let's compute the first few values manually to spot the pattern:

• For n=1: Valid strings are "0" and "1" → f(1) = 2 = 2×Fib(1).
• For n=2: Valid strings are "01" and "10" (since "00" and "11" have even-length runs) → f(2) = 2 = 2×Fib(2).
• For n=3: Valid strings are "000", "010", "101", "111" → f(3) = 4 = 2×Fib(3).
• For n=4: Valid strings are "0001", "0101", "0111", "1000", "1010", "1110" → f(4) = 6 = 2×Fib(4).

The pattern holds for small n—now let's prove it applies to all n.

Step 2: Recursive Relation for f(n) #

To link valid strings of length n to shorter valid strings, split f(n) into two valid scenarios:

1. Case 1: The last character starts a new odd run
   Take any valid string of length n-1, then append the opposite character. Since the original string's last run is odd-length, adding the opposite character creates a new run of length 1 (still odd). Every valid n-1 string gives exactly one valid n-length string here, contributing f(n-1) total.

2. Case 2: The last character extends an existing odd run
   To extend a run without making its length even, we add two copies of the last character (since odd + 2 = odd). Take any valid string of length n-2, append two copies of its final character. Every valid n-2 string gives exactly one valid n-length string here, contributing f(n-2) total.

Combining these cases gives the recurrence formula:

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

Step 3: Connect to Fibonacci Numbers #

Our recurrence for f(n) is identical to the Fibonacci sequence's core rule. The only difference is the initial conditions:

• f(1) = 2 = 2×Fib(1)
• f(2) = 2 = 2×Fib(2)

Since both sequences follow the same recurrence and their starting terms are proportional by a factor of 2, every subsequent term will also be proportional by 2. By mathematical induction, this means:

f(n) = 2×Fib(n)

for all n ≥ 1.

Bonus: Symmetry Check #

Another way to see this is splitting f(n) into two equal subsets: strings ending with 0 (a(n)) and strings ending with 1 (b(n)). By symmetry, a(n) = b(n), so f(n) = 2a(n).

For a(n) (strings ending with 0):

• Either it's a valid n-1 string ending with 1, with a 0 appended (new run of 1) → b(n-1) = a(n-1)
• Or it's a valid n-2 string ending with 0, with two 0s appended (extends the odd run by 2) → a(n-2)

So a(n) = a(n-1) + a(n-2), which is exactly the Fibonacci recurrence. With a(1)=1 (string "0") and a(2)=1 (string "10"), a(n) = Fib(n), so f(n)=2×Fib(n).

内容的提问来源于stack exchange，提问作者pravir