2
$\begingroup$

(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}$?

$\endgroup$
  • 1
    $\begingroup$ Your edits have invalidated the answers you've already gotten. That's bad form. It'd be best to go back to the version of the question people were answering, and ask a new question that goes in the direction you want. $\endgroup$ – Teepeemm Apr 24 '15 at 0:50
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

$$\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+.....)$$

$\endgroup$
  • $\begingroup$ Thanks I had just submitted an edit to the problem before seeing that people had already replied. It seems we had a similar line of thought. $\endgroup$ – A is for Ambition Apr 23 '15 at 22:46
  • $\begingroup$ Hi, please check my edit. I would like to know how to find the reverse case. $\endgroup$ – A is for Ambition Apr 23 '15 at 22:50
  • $\begingroup$ @AisforAmbition ok, $\endgroup$ – E.H.E Apr 23 '15 at 22:52
3
$\begingroup$

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$

$\endgroup$
  • 1
    $\begingroup$ Very nice use of that identity, which I had forgotten. $\endgroup$ – marty cohen Apr 23 '15 at 22:55
0
$\begingroup$

$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

$\endgroup$
0
$\begingroup$

$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}$$

$\endgroup$
-1
$\begingroup$

$$x\left(\frac{1}{1-(x+x^3)}\right)$$ will do it.

$\endgroup$
  • 2
    $\begingroup$ Somehow, I don't think that helps much. $\endgroup$ – marty cohen Apr 23 '15 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.