# Recurrence relation question. Homework.

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?

• Do you know how to expand $1/(1-3x)$ in a series of powers of $x$? – Gerry Myerson Nov 10 '13 at 8:38
• @GerryMyerson Unfortunately no – Ogen Nov 10 '13 at 8:43
• Then drop that class before it's too late. See your teacher. Meanwhile, brush up on the formula for the sum of a geometric series. – Gerry Myerson Nov 10 '13 at 8:45
• @GerryMyerson Ive been doing this course for a whole semester, my final exam is in 5 days. Surely this can't be that hard to understand – Ogen Nov 10 '13 at 9:30
• @GerryMyerson Hi, I just finished my semester and wanted to let you know I got a B despite you telling me I should drop the course. – Ogen Dec 28 '13 at 2:36

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\;?$$

• I did some working and got 3^(n-1)? – Ogen Nov 10 '13 at 9:36
• @Clay: That’s right for $n\ge 1$, but not for $T(0)$. Can you see what $T(0)$ is? – Brian M. Scott Nov 10 '13 at 9:43
• should be 0, and T(1) should be 1 I think – Ogen Nov 10 '13 at 9:46
• @Clay: Yes, $T(0)=0$, because the constant term of the series expansion of $\frac{x}{1-3x}$ is $0$. And $T(1)=3^{1-1}=1$ from the general formula that applies when $n\ge 1$. – Brian M. Scott Nov 10 '13 at 9:49
• thanks for the help, you made this question a lot clearer =D – Ogen Nov 10 '13 at 9:52

Hint: Multiply the equation by $1-3x$.

$$\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$$