A certain counting sequence $T(n)$ has generating function $$\frac{x}{1-3x}=\sum_{n=0}^{\infty}T(n)x^n.$$
(a) Derive a simple recurrence relation for $T(n)$.
(b) Give a simple explicit formula for $T(n)$.
I've only studied the fibonacci sequence in class in terms of recurrence relations but I cant see how it links to this question. Any resources that can help me do questions like these?
On
$$\frac{x}{1-3x}=\sum_{n=0}^{\infty}T(n)x^n.$$ $$\frac{x}{1-3x}=x\sum_{n=0}^{\infty}(3x)^n=\sum_{n=0}^{\infty}3^nx^{n+1}=\sum_{n=1}^{\infty}3^{n-1}x^{n}$$ $$\sum_{n=0}^{\infty}T(n)x^n=T(0)+\sum_{n=1}^{\infty}T(n)x^n$$ $$T(0)+\sum_{n=1}^{\infty}T(n)x^n=\sum_{n=1}^{\infty}3^{n-1}x^{n}$$ for $T(0)=0$ $$T(n)=3^{n-1},n>0$$
Robert Israel has already given a good hint for (a). You can also solve (a) by first solving (b) to get a closed form for $T(n)$ and then constructing a recurrence from that.
From the formula for the sum of a geometric series you should know that
$$\frac1{1-3x}=\sum_{n\ge 0}(3x)^n=\sum_{n\ge 0}3^nx^n\;,$$
so
$$\sum_{n\ge 0}T(n)x^n=\frac{x}{1-3x}=\ldots\;?$$