Generating Functions · Linear Recurrence Relations

Lesson 1

Nikolai Chukhin · Alexander S. Kulikov

We will show how to solve linear recurrence relations using generating functions. Rewrite the definition of Fibonacci numbers as the following equation: \[F(n)-F(n-1)-F(n-2)=0 \ .\] Using simple manipulations (with the generating function \(\mathcal{F}(x)\) of the Fibonacci sequence), ensure that this equation zeros the coefficient at \(x^{n}\) for all \(n \in \mathbb{Z}_{\ge 2}\):

Thus, we obtain the generating function of Fibonacci numbers: \[\mathcal{F}(x)=\frac{x}{1-x-x^2}\ .\]