I am trying to better understand generating functions and how they can be derived / manipulated / etc.
Right now I am operating on this identity, slightly modified from the answer here:
For a recurrence $u_n$ such that $u_{n+2}+au_{n+1} + bu_n = h(n)$, we have:
$$f(x) = \sum_{n=0}^{\infty}u_n x^n = \frac{u_0 + x \cdot(u_1 + au_0) + x^2 \cdot \sum_{n=0}^{\infty} h(n) x^n}{1 + ax + bx^2}$$
So for any generating function, you can decompose it into partial fractions and each piece can be solved by the above identity... but is this always true?
What about a generating function that has an irreducible denominator after applying partial fractions that does not fit the above?
For example
$$f(n) = \frac{1}{x^3-x-1}$$
which cannot be broken down further with partial fractions and also does not fit the above structure.