Two k-ary Fibonacci recurrences are aₖ (n) = aₖ (n-1) + k aₖ (n-2) and bₖ (n) = k bₖ (n-1) + bₖ (n-2). We provide a simple proof that aₖ (n) is the number of k-regular words over n = \1, 2, , n\ that avoid patterns \121, 123, 132, 213\ when using base cases aₖ (0) = aₖ (1) = 1 for any k 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ₖ (n) is the number of k-regular words over n that avoid \122, 213\ with bₖ (0) = bₖ (1) = 1 for any~k 2. Finally, we conjecture that |Av^2₍ (121, 123, 132, 213) | = a₁ (n) ² for n 0. That is, vincularizing the Stirling pattern in Kuba and Panholzer's Jacobsthal result gives the Fibonacci-squared numbers. 20 pages, submitted to special journal issue for Permutation Patterns 2023 (PP23) in DMTCS
Downing et al. (Tue,) studied this question.