PhiRepresentation : Type ≡ List Bool
PhiValue : PhiRepresentation → ℕ ≡
λrep . sum_{i=0}^{|rep|-1} rep[i] * F_{i+1}
where F uses the shifted Fibonacci: 1,2,3,5,8,...
Proof of recurrence:
For strings of length n without "11":
1. Strings ending in '0':
- Can append '0' to any valid string of length n-1
- Count: CountValidStrings(n-1)
2. Strings ending in '1':
- Previous bit must be '0' (to avoid "11")
- Equivalent to appending '01' to strings of length n-2
- Count: CountValidStrings(n-2)
3. Total: CountValidStrings(n) =
CountValidStrings(n-1) + CountValidStrings(n-2) ∎
Proof combining all lemmas:
1. By Lemma T2-6.1: Recurrence relation established
2. By Lemma T2-6.2: Correspondence with Fibonacci
3. By Lemma T2-6.3: Base cases verified
4. By Lemma T2-6.4: Generating function confirms
5. By Lemma T2-6.5: Growth rate is φ
Therefore the theorem holds ∎
def verify_fibonacci_recurrence():
# 计算前20个值
valid_counts = []
for n in range(20):
count = count_valid_strings_no11(n)
valid_counts.append(count)
# 验证递归关系
for i in range(2, len(valid_counts)):
expected = valid_counts[i-1] + valid_counts[i-2]
actual = valid_counts[i]
assert actual == expected, f"Failed at n={i}"
# 验证与Fibonacci数列的关系
fibonacci = compute_fibonacci_sequence(22)
for i in range(len(valid_counts)):
assert valid_counts[i] == fibonacci[i+2], f"Not F_{i+2}"
return True
def count_valid_strings_no11(n: int) -> int:
"""计算长度为n的不含'11'的二进制串数量"""
if n == 0:
return 1
if n == 1:
return 2
# 使用动态规划
prev2, prev1 = 1, 2
for i in range(2, n+1):
current = prev1 + prev2
prev2, prev1 = prev1, current
return prev1
def enumerate_valid_strings(n: int) -> List[str]:
"""枚举所有长度为n的不含'11'的二进制串"""
if n == 0:
return [""]
valid = []
for i in range(2**n):
binary = format(i, f'0{n}b')
if "11" not in binary:
valid.append(binary)
return valid
def compute_fibonacci_sequence(n: int) -> List[int]:
"""计算前n个Fibonacci数"""
if n == 0:
return []
if n == 1:
return [0]
fib = [0, 1]
for i in range(2, n):
fib.append(fib[i-1] + fib[i-2])
return fib
def is_valid_phi_representation(rep: List[int]) -> bool:
"""检查是否是有效的φ-表示（无相邻的1）"""
for i in range(len(rep) - 1):
if rep[i] == 1 and rep[i+1] == 1:
return False
return True
def compute_phi_value(rep: List[int], fib_sequence: List[int]) -> int:
"""计算φ-表示的值"""
value = 0
for i, bit in enumerate(rep):
if bit == 1:
value += fib_sequence[i]
return value
def generate_all_valid_strings_up_to_n(max_n: int) -> Dict[int, List[str]]:
"""生成所有长度不超过max_n的有效字符串"""
result = {}
for n in range(max_n + 1):
result[n] = enumerate_valid_strings(n)
return result