Recurrence relation question. Homework.

Question

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 08:38
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 08: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 09:30
It's easy to understand --- if you have any familiarity with power series. But if you have no idea how to expand $1/(1-3x)$ in a power series, you don't have a snowball's chance of getting generating functions. Please, talk to your teacher. — Gerry Myerson, Nov 10 '13 at 11:35
@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 02:36

score 5 · Accepted Answer · answered Nov 10 '13 at 09:32

5

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

answered Nov 10 '13 at 09:32

Brian M. Scott

616,228

1

I did some working and got 3^(n-1)? – Ogen Nov 10 '13 at 09:36
1

@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 09:43
1

should be 0, and T(1) should be 1 I think – Ogen Nov 10 '13 at 09:46
1

@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 09:49
thanks for the help, you made this question a lot clearer =D – Ogen Nov 10 '13 at 09:52
@Clay: You’re welcome; glad to have been of use. – Brian M. Scott Nov 10 '13 at 09:53

score 3 · Answer 2 · answered Nov 10 '13 at 08:39

3

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

answered Nov 10 '13 at 08:39

Robert Israel

448,999

score 0 · Answer 3 · answered Nov 10 '13 at 10:06

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

Recurrence relation question. Homework.

3 Answers3