Determine a generating function for the Lucas Sequence

Question

I have been answering questions on how to find a sequence given a generating function, however I am unsure as to how to proceed given a sequence to find the generating function. The sequence in question is the Lucas sequence (1, 3, 4, 7, 11,...). I thought to try trial and error but that seems tedious. Is there a formula or certain steps I should follow?

Answer 1

The key when finding the generating function (or more loosely describing the generating function) is to leverage what you know about the sequence.

In the case of the Lucas sequence, we know that $$ L_0 = 1, \qquad L_1 = 3, \qquad L_n = L_{n-1} + L_{n-2} \quad n \geq 2 $$ Let's focus on that last bit of information for now. To write that the equality holds for all $n$ using generating functions, I might say that $$ \sum_{n \geq 2}L_n x^n = \sum_{n \geq 2}(L_{n-1} + L_{n-2})x^n $$ The key now is to write each side in terms of the generating function $L(x) = \sum_{n \geq 0} L_n x^n$. For example, I could rewrite the left side as $$ \sum_{n \geq 2}L_{n-1}x^n + \sum_{n \geq 2}L_{n-2}x^n = \\ x\sum_{n \geq 2}L_{n-1}x^{n-1} + x^2\sum_{n \geq 2}L_{n-2}x^{n-2} = \\ x\sum_{k \geq 1}L_{k}x^{k} + x^2\sum_{k \geq 0}L_{k}x^{k} = \\ x\left(\sum_{k \geq 0}L_{k}x^{k} - L_0x^0\right) + x^2\sum_{k \geq 0}L_{k}x^{k} =\\ x(L(x) - 1) + x^2L(x) $$ How could you rewrite the right side? Use the resulting equation to solve for $L(x)$.