Find explicit formula for generating function

Question

I'm given the following recurrence:

$a_0 = 3, a_n = 2a_{n-1} - 7$ for $n \ge 1$.

I did the following steps:

$$A(x) = \sum_{n=0}^\infty a_nx^n$$

$$a_n = 2a_{n-1} - 7$$

$$\sum_{n=1}^\infty a_nx^n = 2\sum_{n=1}^\infty a_{n-1}x^n - 7\sum_{n=1}^\infty x^n$$

$$A(x) - a_0 = ?$$

Also I believe that $ 7\sum_{n=1}^\infty x^n = 7 \cdot (\frac{1}{1-x} - 1)$ Is that correct?

I'm not sure how to continue with the right side further. Could you provide me with further steps?

// EDIT

$$A(x) - 3 = 2xA(x) + 7 - \frac{7}{1-x}$$ $$A(x) - 10 + \frac{7}{1-x} = 2xA(x)$$

$$\require{cancel} \cancel{\frac{A(x)-10}{2x} + \frac{7}{2x(1-x)} = A(x)}$$

//EDIT2

$$(2x-1)A(x) = \frac{7}{1-x}-10$$ $$A(x) = \frac{10x-3}{(1-x)(2x-1)}$$

$$A(x) = \frac{10x-3}{1-x} * \frac{1}{2x-1}$$

Now I can calculate the explicit formula for $a_n$. Do I have to use the partial fractions or what are the steps now?

Answer 1

The goal is to be able to express every series either in the form:

• of a known power series, or
• as $\sum_{n=0}^\infty b_n x^n$ for some constants $b_n$ (and hopefully relate it to $A(x)$)

The best ways to handle this are through differentiation or various algebraic manipulations.

---

For example, consider the summation $$ \sum_{n=2}^\infty a_{n-2} x^n $$ provided $A(x) = \sum_{n=0}^\infty a_n x^n$. We would naturally want to rewrite this to use $a_n$ instead. Well, a reindexing shows $$ \sum_{n=2}^\infty a_{n-2} x^n = \sum_{n=0}^\infty a_{n} x^{n+2} $$ This seems vaguely correct, but that $n+2$ in the exponent isn't helpful. However... $$ \sum_{n=0}^\infty a_{n} x^{n+2} = x^2 \sum_{n=0}^\infty a_{n} x^{n} = x^2 A(x) $$

---

Another example: suppose we have the sum $$ \sum_{n=1}^\infty na_n x^{n-1} $$ This constant $n$ just screams a differentiation to me. We note that $$ \frac{d}{dx} a_n x^n = na_n x^{n-1} $$ so $$ \sum_{n=1}^\infty na_n x^{n-1} = \sum_{n=1}^\infty \frac{d}{dx} na_n x^{n-1} = \frac{d}{dx} \sum_{n=0}^\infty a_n x^n = A'(x) $$ Note that the $n=0$ term gets added back in, since it's a constant term.

---

$7\sum_{n=1}^\infty x^n = 7 \cdot (\frac{1}{1-x} - 1)$

This is correct. You're using the geometric series, after all: $$ \sum_{n=1}^\infty x^n = -1 + \sum_{n=0}^\infty x^n = -1 + \frac{1}{1-x} $$

Answer 2

It seems that you finished the recurrence relation part,but stuck in partial fractions. You found that $$A(x) = \frac{10x-3}{1-x} \times \frac{1}{2x-1}$$

Then, let try to write it using partial fractions decomposition from calculus class:

$$A(x) = \frac{10x-3}{1-x} \times \frac{1}{2x-1} = \frac{4}{2x-1}- \frac{7}{x-1}$$

$$[x^n]A(x)=[x^n] \bigg( \frac{7}{1-x}- \frac{4}{1-2x}\bigg)= (7\times 1^n) -(4 \times2^n)$$

Answer 3

I can't believe how complex the proffered solutions are for a recurrence that can literally be solved by inspection. What are you going to do when you have a $2^{nd}$-order recurrence with inhomogeneous terms such as $A^n$ and $n^2$? Anyway, here's the solution, which you can use to check your result.

Given

$$ a_n = 2a_{n-1} - 7,\quad a_0 = 3 $$

Assume

$$ a_n=f_n+b $$

Substituting in the above you see that

$$ \begin{align} &b=7;\\ &f_n=2f_{n-1}; f_0=a_0-b;\\ &a_n=-4\cdot2^n+7 \end{align} $$