A Context-Free Grammar Associated with Fibonacci and Lucas Sequences

Abstract

We introduce a context-free grammar G=s⟶s+d,d⟶s to generate Fibonacci and Lucas sequences. By applying the grammar G, we give a grammatical proof of the Binet formula. Besides, we use the grammar G to provide a unified approach to prove several binomial convolutions about Fibonacci and Lucas numbers, which were given by Hoggatt, Carlitz, and Church. Meanwhile, we also obtain some new binomial convolutions.