  Two $k$-ary Fibonacci recurrences are $a_k(n) = a_k(n-1) + k \cdot a_k(n-2)$
and $b_k(n) = k \cdot b_k(n-1) + b_k(n-2)$. We provide a simple proof that
$a_k(n)$ is the number of $k$-regular words over $[n] = \{1,2,\ldots,n\}$ that
avoid patterns $\{121, 123, 132, 213\}$ when using base cases $a_k(0) = a_k(1)
= 1$ for any $k \geq 1$. This was previously proven by Kuba and Panholzer in
the context of Wilf-equivalence for restricted Stirling permutations, and it
creates Simion and Schmidt's classic result on the Fibonacci sequence when
$k=1$, and the Jacobsthal sequence when $k=2$. We complement this theorem by
proving that $b_k(n)$ is the number of $k$-regular words over $[n]$ that avoid
$\{122, 213\}$ with $b_k(0) = b_k(1) = 1$ for any~$k \geq 2$. Finally, we
conjecture that $|Av^{2}_{n}(\underline{121}, 123, 132, 213)| = a_1(n)^2$ for
$n \geq 0$. That is, vincularizing the Stirling pattern in Kuba and Panholzer's
Jacobsthal result gives the Fibonacci-squared numbers.
