EDIT: Ok, silly me. There is an obvious closed form summation which somehow escaped me. Nonetheless, I would appreciate comments on deriving a characteristic polynomial from the generating function.
Consider the following power series:
$$1 + 5x + 9x^2 + 13x^3 + 17x^4 + \dots $$
Is there a way to express this as a single power series in sigma notation (i.e. with no more than one sigma symbol)? If so, how?
Normally this sort of thing would be elementary. So, for example, I know that given the power series $1 + 2x + 3x^2 + \dots$ we could express it equivalently as $\sum_{n=1} ^{\infty}nx^{n - 1}$
In this case it's no so straight forward, since the pattern of coefficients depends on the coefficients of previous terms. We could of course write it as it as the sum of two power series:
$$ \sum_{n=0} ^{\infty}(2n)x^{n} + \sum_{n=0} ^{\infty}(2n+1)x^{n} $$
But my aim is to express it as a single power series (if possible).
My attempt so far:
Note that $9x^2 = 2x(5x) - x^2(1) \space$ and $ \space 13x^3 = 2x(9x^2) - x^2(5x). \space$ So in general,
$$a_i = 2xa_{i-1} - x^2a_{i-2}$$ ...the relation of coefficients therefore being $1 = 2x - x^2$ or $1 - 2x + x^2 = 0$.
Neow call the original power series $$S = 1 + 5x + 9x^2 + 13x^3 + \dots $$.
Summing $S -2xS + x^2S$ gives us,
$$ S(1 - 2x + x^2) = 1 + 3x \Longrightarrow S = \frac{1 + 3x}{1 - 2x + x^2} $$
So we at least have a closed form of the series via the generating function.
Which brings me to the post Generating functions with power series which I've meagerly attempted to follow in order to generate the desired result.
Except I'm not too familiar with characteristic polynomials. (I thought a characteristic polynomial required a square matrix?). Earlier, we derived $1 - 2x + x^2$ from the pattern of coefficients in order to derive the generating function. The book I'm working out of calls this the "scale of relation" of the series. How is this related to the characteristic polynomial (if at all)?
In the top answer to the linked post, the generating function $\frac{1}{1 - 2x - x^2}$ ends up with a general term that would imply the sum is $ \sum_{n=0} ^{\infty} \left( \frac{2 + \sqrt{2}}{4}(1 + \sqrt{2}^n) + \frac{2 - \sqrt{2}}{3}(1 - \sqrt{2}^n) \right)$ (I'm guessing the final sigma sum form of our series would look somewhat similar).
In our case, however, the denominator of the generating function is $1 - 2x + x^2 = (1-x)^2$, so the only root is $1$. It's unclear to me how to adapt the $a_0 = A + B$ technique used in that answer to derive the general term of our series.
Even if I've overlooked an easy way to write the original series as a single sum, I would appreciate details in deriving a characteristic polynomial in this case.
Also, is it at all correct to say that a generating function has a characteristic polynomial, or is that a property of the expressions in the numerator and denominator only?
Thanks for any help.
