TAOCP 5.4.2 Exercise 9
Let $K_m$ denote $K^{(p)}$, the number of sequences of length $m$ consisting of $0$’s and $1$’s that contain no $p$ consecutive $1$’s.
Section 5.4.2: The Polyphase Merge
Exercise 9. [M20] [M20] Let K®) be the number of sequences of m Os and 1s such that there are no p consecutive 1s. For example, when p = 3 and m = 5 there are 24 such sequences: 00000, 00001, 00010, 00011, 00100, 00101, 00110, 01000, 01001,...,11011. Show that Ke isa generalized Fibonacci number.
Verified: no
Solve time: 53s
Solution
Let $K_m$ denote $K^{(p)}$, the number of sequences of length $m$ consisting of $0$’s and $1$’s that contain no $p$ consecutive $1$’s. Let $K_0=1$, representing the empty sequence.
For $1 \le m < p$, no restriction is active, hence every binary sequence of length $m$ is admissible, so
$$ K_m = 2^m \qquad (1 \le m < p). $$
For $m \ge p$, classify admissible sequences by the length $k$ of the final block of consecutive $1$’s, where $0 \le k \le p-1$.
If $k=0$, the sequence ends in $0$. Removing this final symbol yields a bijection with admissible sequences of length $m-1$, contributing $K_{m-1}$ sequences.
If $1 \le k \le p-1$, the sequence ends in $1^k$ and the symbol immediately preceding this block must be $0$. Removing the final block $0,1^k$ yields a bijection with admissible sequences of length $m-k-1$, contributing $K_{m-k-1}$ sequences.
These cases are disjoint and exhaustive, hence
$$ K_m = K_{m-1} + \sum_{k=1}^{p-1} K_{m-k-1} = \sum_{j=1}^{p} K_{m-j} \qquad (m \ge p). $$
Thus $(K_m)$ satisfies the linear recurrence
$$ K_m = K_{m-1} + K_{m-2} + \cdots + K_{m-p} \qquad (m \ge p), $$
with initial values $K_0=1$ and $K_m=2^m$ for $1 \le m < p$.
This is the defining recurrence of the $p$th-order Fibonacci numbers in the sense of Section 5.4.2, after the standard normalization of initial conditions. Therefore $K_m$ is a generalized Fibonacci number of order $p$.
This completes the proof. ∎