A Grammatical Interpretation of Horadam Sequences

The Horadam sequence {Hn(a,b;p,q)}n⩾0 has been widely studied in combinatorics and number theory. In this paper, we find that the context-free grammar G={x→px+y,y→qx} can be used to generate Horadam sequences. Using this grammar, we deduce several identities, including Cassini-like identities. Moreover, we investigate the relationship between two distinct Horadam sequences Hn(a,b;p,q) and Hn(c,d;p,q) with (a,b)≠(c,d) and provide an approach to derive identities, which can be illustrated by the Fibonacci and Lucas sequences as well as the two kinds of Chebyshev polynomials.