# Generating Functions

• Feb 12th 2010, 04:10 PM
pseudonym
Generating Functions

Find the generating functions for the following sequences, express them in a closed form, without infinite sums:

(i) 1,2,1,4,1,8,1,16,1,...

(ii)1,1,0,1,1,0,1,1,0,...

This is what I have so far:
(i)i've written it as 1 + 2^1*x^1 + (2x)^0 + 2^2*x^3 + (2x)^0 + 2^3*x^5 +...
if the sequence didnt have all the ones inbetween, I think i'd know how to do it, using differentiation on (1/(1-x)) multiplied by something. But I'm not sure how to incorporate the ones into the sequence...

• Feb 12th 2010, 05:46 PM
aliceinwonderland
Quote:

Originally Posted by pseudonym

Find the generating functions for the following sequences, express them in a closed form, without infinite sums:

(i) 1,2,1,4,1,8,1,16,1,...

(ii)1,1,0,1,1,0,1,1,0,...

This is what I have so far:
(i)i've written it as 1 + 2^1*x^1 + (2x)^0 + 2^2*x^3 + (2x)^0 + 2^3*x^5 +...
if the sequence didnt have all the ones inbetween, I think i'd know how to do it, using differentiation on (1/(1-x)) multiplied by something. But I'm not sure how to incorporate the ones into the sequence...

The generating function for (i) has the form $1 + 2x + x^2 + 4x^3 + x^4 \cdots$. It is the same thing with $(1 + x^2 + x^4 +....) + 2x(1 + 2x^2 + 4x^4 \cdots )$. Now consider the power series of $1/(1-x^2)$ and $1/(1-2x^2)$.
The second problem is similar. The generating function for (ii) has the form $1+x+x^3+x^4+x^6...= (1+x^3+x^6 \cdots)+x(1+x^3+x^6 \cdots)$. Now consider the power series of $1/(1-x^3)$.