The Perrin sequence is defined by $a_0 = 3, a_1 = 0, a_2 = 2$ and $a_k = a_{k-2}+a_{k-3}$ for $k \ge 3$. The Padovan sequence is defined by $b_0 = 0, b_1=1, b_2=1$ and $b_k=b_{k-2}+b_{k-3}$ for $k\ge 3$.
Find generating functions in the form of rational functions for the Perrin sequence and the Padovan sequence.
I am a little bit confused about this question , any hint?
Denote the generating function for the Perrin sequence as $A(x) = \sum_{n=0}^\infty a_n x^n$, where $\{a_k\}_{k=0}^\infty$ is the Perrin sequence.
We get
$$\begin{align} A(x) &= \sum_{n=0}^\infty a_n x^n \\ &= \sum_{n=3}^\infty a_n x^n + a_2x^2+a_1x^1+a_0x^0\\ &= \sum_{n=3}^\infty \left(a_{n-2} + a_{n-3}\right)x^n+ a_2x^2+a_1x^1+a_0x^0\\ &=x^2\sum_{n=3}^\infty a_{n-2} x^{n-2}+x^3\sum_{n=3}^\infty a_{n-3} x^{n-3}+ a_2x^2+a_1x^1+a_0x^0\\ &=x^2(A(x)-a_0x^0)+x^3A(x)+ a_2x^2+a_1x^1+a_0x^0\\ \end{align}$$
Now, substitute the known initial conditions and solve for $A(x)$.
(The same procedure can be used also for the Padovan sequence, since they differ only in the initial conditions.)