## dan815 one year ago expand x/(1-x-x^2) as a power series about the origin

1. ganeshie8

looks suspiciously related to fibonacci

2. anonymous

yeah, that is

3. ganeshie8
4. dan815

lol... someone needs to teach him how to hold a pen

5. dan815

|dw:1435870607209:dw|

6. Empty

let's say $f(x)=\sum_{n=0}^\infty a_n x^n$ then this means the difference quotient$\frac{f(x)-f(0)}{x}= \frac{f(x)-a_0}{x}=\sum_{n=0}^\infty a_{n+1}x^n$ This is taught at the very beginning of chapter 2 in generatingfunctionology which I'm glad you've just started reading, I'll stop here because I think this is sufficiently interesting. ;P

7. DanJS

hmm, free book , thanks

8. dan815

hmm interseting

9. dan815

u can carry this process for getting powerseries with index shifting higher and higher

10. dan815

|dw:1435871132463:dw|

11. dan815

oh my

12. dan815

did u get can equation for a powerseiries with k index shifted

13. dan815

interms of f(x) and f(0)s

14. Empty

hint: $$g(0)=a_1$$

15. Empty

remember you have to dived the whole difference by x, not just the second part

16. dan815

ya just noticed

17. dan815

|dw:1435871684516:dw|

18. dan815

|dw:1435871700596:dw|

19. dan815

i didnt work out that pattern, just thinking itd be nice if it was this

20. dan815

its gotta be this right

21. dan815

oh ya its kinda trivial hehe

22. dan815

so what can we do with this

23. Empty

Well guess you gotta read the book ;P

24. dan815

will come into stuff like descrete methods of representations for the derivatives

25. dan815

now that f(0) is popping up all over

26. dan815

cause for the contiuos version L{f'}=s*L{f}-f(0)

27. dan815

tell me or i will suspend u

28. anonymous

I would try separating the denominator into partial fractions, then rewriting until the components can be expressed as geometric sums.$1-x-x^2=-\left(x+\frac{1+\sqrt5}{2}\right)\left(x+\frac{1-\sqrt5}{2}\right)$ then $\frac{x}{1-x-x^2}=\frac{1-\sqrt5}{\sqrt5\left(2x+1-\sqrt5\right)}-\frac{1+\sqrt5}{\sqrt5\left(2x+1+\sqrt5\right)}$ or something like that...

29. anonymous

Actually, those $$\sqrt5$$s should be $$5$$s in the denominator.

30. anonymous

Just to add some more detail, the next step would be to do the following: $\frac{1}{ax-b}=-\frac{1}{\frac{1}{b}\left(1-abx\right)}=-b\sum_{k=0}^\infty (abx)^k$

31. anonymous

$$f(x)=\frac{x}{1-x-x^2}\$$1-x-x^2)f(x)=xlet \(f(x)=\sum_{n=0}^\infty a_n x^n$$ so$$f(x)-xf(x)-x^2 f(x)=x\\\sum_{n=0}^\infty a_n x^n-\sum_{n=1}^\infty a_{n-1} x^n-\sum_{n=2}^\infty a_{n-2} x^n=x\\a_0+a_1 x-a_0 x+\sum_{n=2}^\infty (a_n-a_{n-1}-a_{n-2}) x^n=x$$so it follows $$a_n=a_{n-1}+a_{n-2};\quad a_0=0, a_1=a_0+1=1$$ 32. anonymous ergo $$a_n=F_n$$ where $$F_n$$ is the n-th Fibonacci number where $$F_0=0$$ and so$$\frac{x}{1-x-x^2}=\sum_{n=0}^\infty F_n x^n=x+x^2+2x^3+3x^4+5x^5+\dots

33. anonymous

^^ by the way, this general rule works for all series whose generating functions are rational $$P(x)/Q(x)$$ -- they are defined by a linear recurrence

34. anonymous

and generating functions are great (especially in DSP when it comes to z-transforms and analyzing the behavior of systems on digital sequences of data)