A combinatorial interpretation of the recurrence fn+1 = 6fn − fn−1

Bonin et al. (1993) recalled an open problem related to the recurrence relation verified by NSW numbers. The recurrence relation is the following: fn+1 = 6fn − fn−1, with f1 = 1 and f2 = 7, and no combinatorial interpretation seems to be known. In this note, we define a regular language L whose number of words having length n is equal to fn+1. Then, by using ℒ we give a direct combinatorial proof of the recurrence.