I want to learn if there is any easier way to resolve generating equations.
Here is how I do it :
E.g. I have a recurrence $T_n-T_{n-1}-T_{n-3}=1.$
I calculated the generating function as $A(x)=\frac{1}{(1-x)(1-x-x^3)}$.
Now I need a formula from here, so that I can put a value of $n$ in that formula and the value of $T_n$.
For this, I assume, $A(x)=\frac{a_0}{1-x}+\frac{a_1}{b_1-x}+\frac{a_2}{b_2-x}+\frac{a_3}{b_3-x}$
Now, I equate $\frac{1}{(1-x)(1-x-x^3)} = \frac{a_0}{1-x}+\frac{a_1}{b_1-x}+\frac{a_2}{b_2-x}+\frac{a_3}{b_3-x}$
$(1-x)(b_1-x)(b_2-x)(b_3-x)=(1-x)(1-x-x^3)(a_0(b_1-x)(b_2-x)(b_3-x)+a_1(....)+a_2(....))$
Then break all those terms, and equate equal powers of x, then get 5 complicated equations from there, and do a lengthy calculation to get values of a and bs. Put them in the formula.
If there is a way to resolve generating equations in an easier way, please suggest, with details.
Note that finding $a$’s and $b$’s in
$$\frac{1}{(1-x)(1-x-x^3)} = \frac{a_0}{1-x}+\frac{a_1}{b_1-x}+\frac{a_2}{b_2-x}+\frac{a_3}{b_3-x}$$
is equivalent to performing fractional decomposition. Recognize that
$$1-x-x^3=(b_1-x)(b_2-x)(b_3-x)$$
Then, $b$’s are obtained first by solving the cubic equation analytically. (Two roots are complex numbers, though) Afterwards, $a$’s are evaluated with
$$a_0=\frac{1}{(b_1-1)(b_2-1)(b_3-1)}$$
$$a_k=\lim_{x\to b_k} \frac{b_k-x}{(1-x)(b_1-x)(b_2-x)(b_3-x)},\>\>\>k=1,2,3$$