A Combinatorial Interpretation of @apu_yokai's k-Lucas Number Identity

Introduction

The Fibonacci numbers admit a straight-forward generalisation by modifying the recurrence relation $F_{n+1}=F_{n-1}+F_n$
to $f_{n+1}=f_{n-k+1}+\cdots +f_n$, that is, we replace the sum of two previous terms by the sum of $k$ previous terms.
Another way to write this recursion is via matrix multiplication:

$$\left(\begin{array}{c}{f}_{n-k+2}\\ ⋮\\ f_{n+1}\end{array}\right)=\underset{M_k^T:=}{\underbrace{\left(\begin{array}{cccc}0& 1& & 0\\ ⋮& \ddots & \ddots & \\ 0& \cdots & 0& 1\\ 1& \cdots & \cdots & 1\end{array}\right)}}\left(\begin{array}{c}{f}_{n-k+1}\\ ⋮\\ f_n\end{array}\right)$$

This matrix $M_k$ has characteristic polynomial $x^k-x^{k-1}-\cdots -1$, and by Cayley-Hamilton we get the identity $M^k=M^{k-1}+\cdots +M+I,$ which encodes the recurrence relation of the $f_i$.
Furthermore the polynomial has $k$ roots $a_1,...,a_k$, which are the eigenvalues of $M_k$.

An important companion of the Fibonacci numbers are the Lucas numbers $L_n$, which can be seen as the trace of powers of $M_2$:
$$L_n=\text{trace}(M_2^n)$$
Accordingly we can define the $k$-Lucas numbers to be ${\ell }_n:=\text{trace}(M_k^n)=a_1^n+...+a_k^n$.

For small $n$ the $k$-Lucas numbers have a surprisingly simple form: ${\ell }_n=2^n-1$ for $1\le n\le k$.
This has been observed by @apu_yokai and proven in a collaborative effort on Twitter and Mathlog.
The proof is short and uses Newton's identities.
For this article I want to go in a different direction and ask: Why $2^n-1$? I found a combinatorial answer which I will present two steps:

1. View the matrix $M_k$ as a directed graph
2. Build finite deterministic automata from this directed graph which together produce all non-zero binary numbers.

The Graph

The Matrix $M=M_k$ is defined by

$M{e}_1=e_2,\dots ,M{e}_{k-1}=e_k$ and $M{e}_k=e_1+\dots +e_k$.

This matrix is an adjacency matrix for the directed graph on $k$ nodes $1,\dots ,5$ with edges
$1\to 2,\dots ,k-1\to k$ and $k\to 1,\dots ,k\to k$.

Here is an example for $k=5$:
Graph for k = 5

The powers of the adjacency matrix have a very useful interpretation, as explained in Wikipedia :
The $(i,j)$ entry in $M^n$ counts the number of paths of length $n$ to go from $j$ to $i$.

In particular, the trace counts the number of loops of length $n$ starting from any vertex.
(Caveat: two loops are considered different if their starting vertices are different, i.e. $1\to 2\to 3\to 1\ne 2\to 3\to 1\to 2$)
The question now becomes: How many loops of length $n$ exist in this graph?

The Automaton

From the graph we obtain a machine which produces non-zero binary numbers by labeling the edges:

$$\text{LABEL}[i\to i+1]=0,(i=1,...,k-1)$$
$$\text{LABEL}[k\to i]=1,(i=1,...,k)$$

Automaton for k = 5

To produce the binary number 00101 we use the loop $3\stackrel{0}{\to }4\stackrel{0}{\to }5\stackrel{1}{\to }4\stackrel{0}{\to }5\stackrel{1}{\to }3$

More examples:

00001: $1\stackrel{0}{\to }2\stackrel{0}{\to }3\stackrel{0}{\to }4\stackrel{0}{\to }5\stackrel{1}{\to }1$

1101: $5\stackrel{1}{\to }5\stackrel{1}{\to }4\stackrel{0}{\to }5\stackrel{1}{\to }5$

00100: $3\stackrel{0}{\to }4\stackrel{0}{\to }5\stackrel{1}{\to }1\stackrel{0}{\to }2\stackrel{0}{\to }3$

I think you can show by induction that every non-zero binary number of length $n$ is produced by a unique loop of length $n$ ($1\le n\le k$).
The number of loops is therefore the number of non-zero binary numbers on $n$ bits, which is $2^n-1$.