Not sure what I'm doing wrong with this recurrence problem

54 Views Asked by At

$r_{n} = 4r_{n-1} + 6r_{n-2} $

Using Generating Functions I have:

We have $ R(x)= \sum^{\infty}_{i=0}r_nx_n $ $R(x) = \sum_{i=0}^{\infty} r_nx_n $. Then we multiply the relation on both sides by $x_nx_n$. After I subbed in R(x)R(x) and subtracted the missing initial values ($r_0=1 $ $r_1=3$ $r_0=1 $ $r_1=3$) and did some algebra.Full Work

$R(x)[1 - 4x - 6x^2] = 1-x$

Solution Manual Says:

$R(x)[1 - x - 6x^2] = 1-x$

1

There are 1 best solutions below

1
On BEST ANSWER

$$\begin{align*} R(x) &= \sum_{n=0}^\infty r_n x^n \\ &= r_0 + r_1 x + \sum_{n=2}^\infty r_n x^n \\ &= r_0 + r_1 x + \sum_{n=2}^\infty 4r_{n-1} x^{n-1} x + 6r_{n-2} x^{n-2} x^2 \\ &= r_0 + r_1 x + 4x \sum_{n=1}^\infty r_n x^n + 6x^2 \sum_{n=0}^\infty r_n x^n \\ &= r_0 + r_1 x + 4x (R(x) - r_0) + 6x^2 R(x) \\ &= (6x^2 + 4x)R(x) + r_0 + (r_1 - 4r_0)x.\end{align*}$$ Therefore, $$R(x) = \frac{r_0 + (r_1 - 4r_0)x}{1 - 4x - 6x^2} = \frac{1-x}{1 - 4x - 6x^2}.$$ Your calculation is correct.

To see for certain that the book's answer is not correct, we can observe that the denominator $1-x-6x^2$ factors as $(1+2x)(1-3x)$, and therefore $$\frac{1-x}{1-x-6x^2} = \frac{3}{5}\cdot \frac{1}{1+2x} + \frac{2}{5} \cdot \frac{1}{1-3x}.$$ Then by computing the geometric series expansions, we find $$\frac{1-x}{1-x-6x^2} = \frac{1}{5} \sum_{n=0}^\infty \left( 3(-2)^n + 2(3^n) \right) x^n,$$ which would suggest that $$r_n = \frac{3(-2)^n + 2(3^n)}{5},$$ but this yields $$\{r_n\}_{n=0}^5 = \{1, 0, 6, 6, 42\},$$ which is obviously wrong: it should be $$\{r_n\}_{n=0}^5 = \{1, 3, 18, 90, 468\}.$$ I leave it to you to verify that your calculation is correct, using a similar method of finding the explicit formula from $R(x)$.