Generating functions on recursive

70 Views Asked by At

We have a recursive sequence, defined by $r_0 = r_1 = 0$, and

$$r_n = 7r_{n-1} + 4r_{n-2} + n + 1,\quad \text{for } n\geq 2.$$

Express the generating function of this sequence as a quotient of polynomials or products of polynomials.

I have written the sequence

$$R(x) = r_0(0)+r_1(x)+r_2(x^2)+.....+r_n(x^n)+...$$ $$2xR(x)= 2r(0)x+2r(1)x^2+....+2r(n-1)x^n$$

but then what? In other examples, the instructor solved for Fibonacci and he gets nearly the same sequence after summing up, but I couldn't figure out this case.

1

There are 1 best solutions below

0
On BEST ANSWER

Indeed, begin by letting

$$R(x) = r_0 + r_1 x + r_2 x^2 + \dots = \sum _{n \ge 0} r_n x^n$$

be a formal series.

Notice that

$$R(x) = \underbrace{r_0} _{=0} + \underbrace{r_1} _{=0} x + \sum _{n \ge 2} \big( 7 r_{n-1} + 4 r_{n-2} + (n+1) \big) x^n = \\ \sum _{m \ge 1} 7 r_m x^{m+1} + \sum _{p \ge 0} 4 r_p x^{p+2} + \sum _{k \ge 3} k x^{k-1} = \\ 7x \big( R(x) - \underbrace{r_0} _{=0} \big) + 4x^2 R(x) + \sum _{k \ge 3} (x^k)' = \\ 7x R(x) + 4x^2 R(x) + \left( \sum _{k \ge 3} x^k \right) ' = \\ (7x + 4x^2) R(x) + \left( \frac 1 {1-x} - 1 - x - x^2 \right) ' = \\ (7x + 4x^2) R(x) + \frac 1 {(1-x)^2} - 1 - 2x ,$$

which implies that

$$(4x^2 + 7x - 1) R(x) = 1 + 2x - \frac 1 {(1-x)^2} = \frac {2x^3 - 3x^2} {(1-x)^2} , $$

whence one finally gets

$$R(x) = \frac {2x^3 - 3x^2} {(4x^2 + 7x - 1) (1-x)^2} .$$