How do I find the generating function for the sequence $-2, 4, -8, 16, -32, 64, ...$

Question

I am trying to find the generating function for the sequence: $-2, 4, -8, 16, -32, 64, ...$ and I am not sure what the answer is.

I have colleagues who are saying that $g(x) = \frac{1}{(1+2x)}$ is the correct answer but based on my work below I believe $g(x) = \frac{-2x}{(1+2x)}$ is the correct answer. What is correct and how did you solve this problem?

---

My work

Recursive equation: \begin{cases} a_{1} = -2 \\ a_{n+1} = -2a_{n}, & n \geq 1 \end{cases}

$$ a_{n+1} = -2a_{n} $$

$$ a_{n+1}x^{n+1} = -2a_{n}x^{n+1} $$

$$ \sum_{n \geq 1} a_{n+1}x^{n+1} = \sum_{n \geq 1} -2a_{n}x^{n+1} $$

$$ \sum_{n \geq 2} a_{n}x^{n} = -2x\sum_{n \geq 1} a_{n}x^{n} $$

$$ \sum_{n \geq 1} a_{n}x^{n} - (\underbrace{-2x}_\text{$a_{1}x$}) = -2x\sum_{n \geq 1} a_{n}x^{n} $$

Let $S = \sum_{n \geq 1} a_{n}x^{n}$

$$ S + 2x = -2xS \implies S + 2xS = -2x \implies S(1 + 2x) = -2x $$

$$ S = \sum_{n \geq 1} a_{n}x^{n} = \frac{-2x}{(1+2x)} $$

Answer 1

Comment expanded to answer per request.

An infinite sequence is a list of numbers in particular order. The most common convention is index them by natural numbers $\mathbb{N} = \{0,1,\ldots\}$. If we call them $a_0, a_1,\ldots$, its OGF (ordindary generating function) is defined to be the formal power series: $$G(a_n; x) = \sum_{n=0}^\infty a_n x^n$$ The whole point of OGF is transform the sequence to a "function like object", and by manipulating the OGF, one hopefully extract useful information about the underlying sequence.

Since OGF is a tool, we are typically not that strict to insist indexing the sequence start at $n = 0$. Depends on application, sometimes it is more natural to start the sequence at $n = 1$.

As an example, if one want to study the number of ways of tiling a $2\times n$ rectangle by dominos. It will be more natural to directly use the height of the rectangle $n$ as index. So $n$ start at $1$ and $a_n$ is the number ways of tiling.

In that case, one can define the OCF as $$\tilde{G}(a_n;x) = \sum_{n=1}^\infty a_n x^n$$ As long as you inform others about your convention, everything will be fine.

For your sequence $-2,4,-8,\ldots$, its comes down to whether your sequence start at $n=0$ or $n=1$.

1. If you sequence start at $n=0$ (this is the default), the answer is $\frac{-2}{1+2x}$.
2. If your sequence start at $n=1$ (without any implicit $a_0$), the answer is $\frac{-2x}{1+2x}$.
3. In the case where sequence start at $n=1$ with an implicit/preferable $a_0 = 1{}^{\color{blue}{[1]}}$, the answer is $\frac{1}{1+2x}$. However, I don't see any reason one should assign $1$ to $a_0$.

Which one to use depends on how are you going to use your generating function. As a rule of thumb, pick one which make your life easier and inform others about your convention.

Note

• $\color{blue}{[1]}$ For a lot of problem where the natural choice of $n$ start at $1$, the expression can be simplified by an appropriate choice of $a_0$ (usually $0$ or $1$). In that case, you extend your sequence to include an extra $a_0$ and use OCF $G(\cdots)$ instead of $\tilde{G}(\cdots)$.