Given   $a_n = (n^2 + 1) 3^n,$ find a recurrence relation $a_n + p a_{n+1} + q a_{n+2} + r a_{n+3} = 0.$ Hence evaluate $\sum_{n\geq0} a_n x^n.$
1. Given the sequence \(a_n = (n^2 + 1) 3^n\), we need to find a recurrence relation of the form \(a_n + p a_{n+1} + q a_{n+2} + r a_{n+3} = 0\).

2. First, compute \(a_{n+1}\), \(a_{n+2}\), and \(a_{n+3}\):
   \[
   a_{n+1} = ((n+1)^2 + 1) 3^{n+1} = (n^2 + 2n + 2) 3^{n+1}
   \]
   \[
   a_{n+2} = ((n+2)^2 + 1) 3^{n+2} = (n^2 + 4n + 5) 3^{n+2}
   \]
   \[
   a_{n+3} = ((n+3)^2 + 1) 3^{n+3} = (n^2 + 6n + 10) 3^{n+3}
   \]

3. Next, find the differences:
   \[
   a_{n+1} - 3a_n = (n^2 + 2n + 2) 3^{n+1} - 3(n^2 + 1) 3^n = (2n + 1) 3^{n+1}
   \]
   \[
   a_{n+2} - 3a_{n+1} = (n^2 + 4n + 5) 3^{n+2} - 3(n^2 + 2n + 2) 3^{n+1} = (2n + 3) 3^{n+2}
   \]

4. Subtract the two differences:
   \[
   (a_{n+2} - 3a_{n+1}) - 3(a_{n+1} - 3a_n) = (2n + 3) 3^{n+2} - 3(2n + 1) 3^{n+1}
   \]
   \[
   a_{n+2} - 6a_{n+1} + 9a_n = 2 \cdot 3^{n+2}
   \]

5. Compute the next difference:
   \[
   a_{n+3} - 6a_{n+2} + 9a_{n+1} = (n^2 + 6n + 10) 3^{n+3} - 6(n^2 + 4n + 5) 3^{n+2} + 9(n^2 + 2n + 2) 3^{n+1}
   \]
   \[
   = 2 \cdot 3^{n+3}
   \]

6. Combine the results:
   \[
   a_{n+3} - 6a_{n+2} + 9a_{n+1} = 2 \cdot 3^{n+3} = 3(a_{n+2} - 6a_{n+1} + 9a_n)
   \]
   \[
   27a_n = a_{n+3} - 9a_{n+2} + 27a_{n+1}
   \]
   \[
   a_n + (-1)a_{n+1} + \left(\frac{1}{3}\right)a_{n+2} + \left(-\frac{1}{27}\right)a_{n+3} = 0
   \]

7. Define the generating function \(f(x) = \sum_{n=0}^{\infty} a_n x^n\). The radius of convergence is \(1/3\).

8. Using the recurrence relation:
   \[
   \sum_{n=0}^{\infty} \left(a_n x^{n+3} + (-1) a_{n+1} x^{n+3} + \left(\frac{1}{3}\right) a_{n+2} x^{n+3} + \left(-\frac{1}{27}\right) a_{n+3} x^{n+3}\right) = 0
   \]

9. Simplify the series:
   \[
   x^3 f(x) - x^2 (f(x) - a_0) + \left(\frac{x f(x)}{3} - \frac{x}{3} - 2x^2\right) - \left(\frac{f(x)}{27} - \frac{1}{27} - \frac{2x}{9} - \frac{5x^2}{3}\right) = 0
   \]

10. Combine terms:
    \[
    f(x)(27x^3 - 27x^2 + 9x - 1) = -18x^2 + 3x - 1
    \]
    \[
    f(x) = \frac{1 - 3x + 18x^2}{1 - 9x + 27x^2 - 27x^3}
    \]

The final answer is \(\boxed{\frac{1 - 3x + 18x^2}{1 - 9x + 27x^2 - 27x^3}}\).