|
|||||
|
|
A combinatorial interpretation of the recurrence fn+1 = 6fn − fn−1 |
|
| Authors: | E. Barcucci S. Brunetti A. Del Lungo F. Del Ristoro |
| Affiliation: | Dipartimento di Sistemi e Informatica, Universita di Firenza, Via Lombroso 6/17, I-50134, Firenze, Italy |
| Abstract: | 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 L we give a direct combinatorial proof of the recurrence. |
| Keywords: | NSW numbers Recurrence relation Combinatorial interpretation Regular language |
| 本文献已被 ScienceDirect 等数据库收录！ | |