How to Find the Function of a Given Power Series? (Please see edit below; I originally asked how to find a power series expansion of a given function, but I now wanted to know how to do the reverse case.)
Can someone please explain how to find the power series expansion of the function in the title? Also, how would you do it in the reverse case? That is, given the power series expansion, how can you deduce the function $\frac{x}{1-x-x^3}$?
I've also rewritten the function as $$\frac{x}{1-x-x^3} = x \cdot \frac{1}{1-x(1-x^2)}$$ which is of the form of the Maclaurin series $\frac{1}{1-x} = 1+x+x^2+x^3+\ldots$
So the series expansion would then be $$x \cdot (1+(x-x^3)+(x-x^3)^2+(x-x^3)^3+\ldots)$$
However, expanding this to find the simplified power series expansion becomes complicated. According to WolframAlpha (link: http://www.wolframalpha.com/input/?i=power+series+of+x%2F%281-x-x%5E3%29) it eventually works out to $$x+x^2+x^3+2x^4+3x^5+4x^6+6x^7+9x^8+13x^9+19x^{10} +\ldots$$ which is a function defined recursively by $f_n = f_{n-1} + f_{n-3}$ for all $n\gt 3$ with the initial condition that $f_1=f_2=f_3=1$
Appreciate any and all help!
Thanks for reading,
A

Edit: I actually want to find the reverse of the original question. Given the recursively defined function (see above) $$x+x^2+x^3+2x^4+3x^5+4x^6+6x^7+9x^8+13x^9+19x^{10} +\ldots ,$$ how can I show that the function of this power series expansion is $\frac{x}{1-x-x^3}$?

 A: $$\frac{1}{1-x}=1+x+x^2+x^3+x^4+...$$
$$x(\frac{1}{1-(x+x^3)})=x(1+(x+x^3)+(x+x^3)^2+(x+x^3)^3+.....)$$
A: To answer both your old and your new question at the very same time, we can consider a surprising relationship between power series and recurrence relations through generating functions. As a simple example, consider representing $\frac{1}{1-x}$ as a power series. In particular, we want to discover an $f_n$ such that
$$\frac{1}{1-x}=f_0+f_1x+f_2x^2+f_3x^3+\ldots$$
How do we do it? It proves pretty easy; let's multiply both sides by $(1-x)$ to obtain:
$$1=(1-x)(f_0+f_1x+f_2x^2+f_3x^3+\ldots)$$
Now, if we distribute the $(1-x)$ over the infinite sum, we get:
$$\begin{align}1=f_0 &+ f_1x + f_2x^2 + f_3x^3+f_4x^4+\ldots\\& -f_0x-f_1x^2-f_2x^3-f_3x^4-\ldots \end{align}$$
and doing the subtractions in each column, we get to the equation:
$$1=f_0+(f_1-f_0)x+(f_2-f_1)x^2+(f_3-f_2)x^3+\ldots$$
What's clear here? Well, every coefficient of $x$ has to be $0$ - so we get that $f_1-f_0$ and $f_2-f_1$ and $f_3-f_2$ must all be zero. In other words, $f_{n+1}=f_n$. Then, the constant term, $f_0$, must be $1$. Hence $f$ is defined as:
$$f_0=1$$
$$f_{n+1}=f_n.$$
That's a very simple recurrence relation, solved as $f_n=1$ meaning
$$\frac{1}{1-x-x^2}=1+x+x^2+x^3+\ldots$$

Okay, that's pretty cool, but let's try something harder, like setting
$$\frac{1}{1-x-x^2}=f_0+f_1x+f_2x^2+f_3x^3+\ldots$$
Now, if we multiply through by $(1-x-x^2)$ and expand like before, we get
$$\begin{align}1=f_0&+f_1x+f_2x^2+f_3x^3+\ldots\\&-f_0x-f_1x^2-f_2x^3-\ldots\\ &\qquad\,-f_0x^2-f_1x^3-\ldots\end{align}$$
and gathering terms again we get:
$$1=f_0+(f_1-f_0)x+(f_2-f_1-f_0)x^2+(f_3-f_2-f_1)x^3+\ldots+(f_{n+2}-f_{n+1}-f_n)x^{n+2}+\ldots$$
where we see again that $f_0=1$ and that $f_1-f_0$ is zero, hence $f_1=1$. Then, for higher terms we get that the coefficient of $x^{n+2}$ must be zero, hence
$$f_{n+2}-f_{n+1}-f_n=0$$
$$f_{n+2}=f_{n+1}+f_n$$
Oh hey, that's the Fibonacci sequence, so we get the identity
$$\frac{1}{1-x-x^2}=1+1x+2x^2+3x^3+5x^4+8x^5+13x^6+\ldots$$
Your equation will work the same way: Multiply through by the denominator, gather like terms, and then equate the coefficients on the left with those on the right. You will discover exactly the recurrence you found.
A: It's actually not so difficult. Using:
$$\frac{1}{1-x-y}=\sum_{n,m\ge 0}{n + m\choose n}x^ny^m$$
You get
$$\frac{x}{1-x-x^3}=x\cdot\frac{1}{1-x-x^3}=x\cdot \sum_{n,m\ge 0}{n + m\choose n}x^n(x^3)^m=\sum_{n,m\ge 0}{n + m\choose n}x^{n+3m+1}$$
And after a last manipulation you can get a formal power series of the classical form $\sum a_nx^n$
A: $x = (1-x-x^3) x + (x^2 + x^4)$
$x^2 + x^4 = (1-x-x^3) * x^2 + (x^3 + x^4 + x^5)$
$(x^3 + x^4 + x^5) = (1-x-x^3) * x^3 + (2*x^2+x^5 + x^6)$
$(2*x^2+x^5 + x^6) = (1-x-x^3) * 2x^4 + (x^5+3*x^6+x^7)$ then
$\frac{x}{1-x-x^3} = 1 + x + x^2 + x^3 + 2x^4 +\frac{(x^5+3*x^6+x^7)}{1-x-x^3}$
if you continue you all the coefficients of power series
A: $f_{n+3}=f_{n+2}+f_{n}; n\geq 1$ then $\sum^{\infty}_{n=1}f_{n+3}x^n = \sum^{\infty}_{n=1}f_{n+2}x^n+\sum^{\infty}_{n=1}f_{n}x^n$ with $f(x)=\sum^{\infty}_{n=1}f_{n}x^n$ then $\frac{f(x)-f_1x-f_2x^2-f_3x^3}{x^3}= \frac{f(x)-f_1x-f_2x^2}{x^2}+f(x)$ then
$$\frac{f(x)-x-x^2-x^3}{x^3}= \frac{f(x)-x-x^2}{x^2}+f(x)$$ then
$$f(x)= \frac{x}{1-x-x^3}$$
A: $$x\left(\frac{1}{1-(x+x^3)}\right)$$ will do it.
