<s>[INST] Find generating functions for the Perrin and Padovan sequences 
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?
 [/INST] 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.)
</s>