rt.representation theory - Can you find linear recurrence relation for dimensions of invariant tensors?

Let $V$ be a finite dimensional highest weight representation of a (semi)-simple Lie algebra. For each $nge 0$ take $a_n$ to be the dimension of the space of invariant tensors in $otimes^n V$.

In certain cases there is a formula for $a_n$. For example, for $V$ the two dimensional representation of $sl(2)$ we get $a_n=0$ if $n$ is odd and for $n$ even we get the ubiquitous Catalan numbers. In general I don't expect a formula but the sequence does satisfy a linear recurrence relation with polynomial coefficients (known as D-finite).

For example, for the seven dimensional representation of $G_2$ this sequence starts:
1, 0, 1, 1, 4, 10, 35, 120, 455, 1792, 7413, 31780, 140833, 641928, 3000361, 14338702, 69902535, 346939792, 1750071307, 8958993507, 46484716684, 244187539270, 1297395375129, 6965930587924
for more background see http://www.oeis.org/A059710

This satisfies the recurrence
$(n+5)(n+6)a_n=2(n-1)(2n+5)a_{n-1}+(n-1)(19n+18)a_{n-2}+ 14(n-1)(n-2)a_{n-3}$

Question How does one find these recurrence relations?

Then I also have a more challenging follow-up question. The space of invariant tensors in $otimes^n V$ also has an action of the symmetric group $S_n$ and so a Frobenius character which is a symmetric function of degree $n$.

Question How does one calculate these symmetric functions?

I know these can be calculated using plethysms individually. I am hoping for something along the lines of the first question.

Further remarks David's answer solves the problem theoretically but I want to make some remarks about the practicalities. This is in case anyone wants to experiment and also because I believe there is a more efficient method.

The $sl(2)$ example can easily be extended. For the $n$-dimensional representation $a_k$ is the coefficient of $ut^k$ in
$$frac{u-u^{-1}}{1-tleft(frac{u^n-u^{-n}}{u-u^{-1}}right)}$$
For the case $n=3$ see http://www.oeis.org/A005043 and
http://www.oeis.org/A099323
I am not aware of any references for $nge 4$. I don't know if these are algebraic.

The limitation of this method is that there is a sum over the Weyl group. This means it is impractical to implement this method for $E_8$. For the adjoint representation of $E_8$ the start of the sequence is
1 0 1 1 5 16 79 421 2674 19244 156612 1423028 14320350
(found using LiE)