2

I was given a sequence (0, 0, 1, 2, 4, 8, 16). I am tasked with finding the generating function. So far I have reached this point: A(x) = x^2 + 2x^3 + 4x^4 + 8x^5 + 16x^6 + ... -xA(x) = x^2 + x^3 + x^4 + x^5 + x^6 + ...

A(x) - xA(x) = x^3 + 3x^4 + 7x^5 + 15x^6 Any input on where to go from here would be appreciated.

StarCute
  • 165
  • 1
    Try factoring an x^2 out of A(x) and see if something seems familiar – Tim Nov 19 '13 at 19:52
  • I assume you know how to handle a geometric series? – Mike Nov 19 '13 at 20:56
  • @Mike I wouldn't assume that =p – StarCute Nov 19 '13 at 21:10
  • @Tim You're right it does look familiar. It looks like the sum of an infinite geometric series. However, the one difference in this problem compared to others I have done is that each constant seems to be increasing by a multiple of two and I am unsure how to proceed. – StarCute Nov 19 '13 at 21:35

1 Answers1

1

Well, like I mentioned in my comment, you have a geometric series. You can find the formula here. Basically, you were on the right track, but the ratio between terms is $2x$. Try multiplying $A(x)$ by $2x$ and subtracting.

Mike
  • 13,318
  • Ahh.. Gotcha! I'm left with A(x) - 2xA(x) = x^2. When I take out an A(x) I get A(x)(1 - 2x) = x^2. When I divide both sides by (1-2x) I get x^2/(1-2x). Thanks! – StarCute Nov 20 '13 at 01:11