Find generating function of a sequence: $(1,1,2,2,2^2,2^2,2^3,2^3,...)$

Question

Find generating function of a sequence $(1,1,2,2,2^2,2^2,2^3,2^3,...)$

Is it necessary to always look for a sub-sequence, e.g. $(1,2,2^2,2^3,...)$?

This is a geometric sequence which generating function is $\frac{1}{1-2x}$

$\frac{1}{1-2x}=\sum\limits_{k=0}^{+\infty}(2x)^n=1+2x+2^2x^2+2^3x^3+...$

How to find generating function for this sequence using geometric sub-sequence?

Answer 1

Hint:

$$2^{0}+2^{0}x+2^{1}x^{2}+2^{1}x^{3}+2^{2}x^{4}+2^{2}x^{5}+2^3x^6+2^3x^7\cdots=$$$$\left[1+2x^{2}+\left(2x^{2}\right)^{2}+(2x^2)^3+\cdots\right]+x\left[1+2x^{2}+\left(2x^{2}\right)^{2}+(2x^2)^3+\cdots\right]$$

Answer 2

Let $(a_n)$ be the sequence you submitted to us. Let $A$ be the GF associated. We have :

$$A=\sum_{n=0}^{\infty}2^{\lfloor \frac{n}{2}\rfloor }X^n $$

now instead of summing over $n$ we sum over $k=\lfloor \frac{n}{2}\rfloor$ :

$$A=\sum_{k=0}^{\infty}2^{k}X^{2k}+2^{k}X^{2k+1} $$

Finally we divide the sum into two parts :

$$A=\sum_{k=0}^{\infty}2^{k}X^{2k}+\sum_{k=0}^{\infty}2^{k}X^{2k+1} $$

Can you relate this last formulation to what you have already recognize?