TAOCP 5.4.2 Exercise 8

Let $N_m^{(p)}$ denote the number of ordered representations of $m$ as a sum of integers from $\{1,2,\dots,p\}$.

taocpmathematicsalgorithmsvolume-3math-medium

Section 5.4.2: The Polyphase Merge

Exercise 8. [M20] [M20] (E. Netto, 1901.) Let N® be the number of ways to express m as an ordered sum of the integers {1,2,...,p}. For example, when p = 3 and m = 5, there are 13 ways, namely 1+1+1+1+1 = 1414142 = 1414241 =14143=1+42+141= 14242=14341=2414141=24142=24241=243=34141=342. Show that N®) is a generalized Fibonacci number.

Verified: yes
Solve time: 1m29s

Solution

Let $N_m^{(p)}$ denote the number of ordered representations of $m$ as a sum of integers from ${1,2,\dots,p}$.

Fix $m \ge 1$. Partition all such ordered sums according to the first summand. If the first summand equals $k$, where $1 \le k \le p$, then the remaining part is an ordered sum of $m-k$ using the same allowed parts. The number of completions for fixed $k$ is $N_{m-k}^{(p)}$. Summing over all admissible first parts gives

$$ N_m^{(p)} = \sum_{k=1}^{p} N_{m-k}^{(p)}. $$

For boundary conditions, there is exactly one empty ordered sum, so $N_0^{(p)} = 1$. If $m < 0$, no representation exists, so $N_m^{(p)} = 0$.

The recurrence together with these initial conditions matches the definition of the $p$th-order Fibonacci numbers $F_m^{(p)}$, which satisfy

$$ F_m^{(p)} = F_{m-1}^{(p)} + F_{m-2}^{(p)} + \cdots + F_{m-p}^{(p)}, \quad m \ge 1, $$

with $F_0^{(p)} = 1$ and $F_m^{(p)} = 0$ for $m < 0$.

Since both sequences satisfy the same recurrence and initial conditions, they coincide for all $m$:

$$ N_m^{(p)} = F_m^{(p)}. $$

This completes the proof. ∎