3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Do you know how to expand $1/(1-3x)$ in a series of powers of $x$? $\endgroup$ – Gerry Myerson Nov 10 '13 at 8:38
  • $\begingroup$ @GerryMyerson Unfortunately no $\endgroup$ – Ogen Nov 10 '13 at 8:43
  • 4
    $\begingroup$ 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. $\endgroup$ – Gerry Myerson Nov 10 '13 at 8:45
  • $\begingroup$ @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 $\endgroup$ – Ogen Nov 10 '13 at 9:30
  • 1
    $\begingroup$ @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. $\endgroup$ – Ogen Dec 28 '13 at 2:36
5
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I did some working and got 3^(n-1)? $\endgroup$ – Ogen Nov 10 '13 at 9:36
  • 1
    $\begingroup$ @Clay: That’s right for $n\ge 1$, but not for $T(0)$. Can you see what $T(0)$ is? $\endgroup$ – Brian M. Scott Nov 10 '13 at 9:43
  • 1
    $\begingroup$ should be 0, and T(1) should be 1 I think $\endgroup$ – Ogen Nov 10 '13 at 9:46
  • 1
    $\begingroup$ @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$. $\endgroup$ – Brian M. Scott Nov 10 '13 at 9:49
  • $\begingroup$ thanks for the help, you made this question a lot clearer =D $\endgroup$ – Ogen Nov 10 '13 at 9:52
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.