Finding generating functions - how was this jump made?

Question

I'm going through examples of probability-generating functions in a book and am confused by the following example: $$1+2s+4s^2+...=\sum_{n=0}^\infty (2s)^n=(1-2s)^{-1}$$ I understand the summation but how did they infer that $\sum_{n=0}^\infty (2s)^n=(1-2s)^{-1}$?

Answer 1

You can write it as$$\sum_{n=0}^{\infty}(2s)^n=\lim_{N\to\infty}\sum_{n=0}^{N}(2s)^n.$$

Here, $$\sum_{n=0}^{N}(2s)^n=1+2s+\cdots+(2s)^N =\frac{1-(2s)^{N+1}}{1-2s}.$$

Hence, if $|2s|\lt 1,$ then we have $$\sum_{n=0}^{\infty}(2s)^n=\lim_{N\to\infty}\sum_{n=0}^{N}(2s)^n=\frac{1-0}{1-2s}=\frac{1}{1-2s}.$$

Answer 2

First assume that the sequence has an end.

Let $A = 1+2s+4s^2+...+(2s)^{n}$

Multiply by $2s$

$A\cdot 2s = 2s+4s^2+8s^3+...+(2s)^{n+1}$

Subtract the former from the latter:

$$A\cdot 2s - A = (2s)^{n+1} - 1$$

$$A( 2s - 1) = (2s)^{n+1} - 1$$

$$A= \frac{(2s)^{n+1} - 1}{( 2s - 1)}$$

When $n+1$ converges to infinity, $2s$ tends to $0$ iff $|2s|<1$

Which leaves us with:

$$A= \frac{- 1}{( 2s - 1)} = (1-2s)^{-1}$$

Answer 3

For $|x|<1$ we have $$ 1+x+x^2+\cdots=\frac{1}{1-x}. $$ Now put $x=2s$. Then for $|s|<\frac 12$ you get $$ 1+2s+(2s)^2+\cdots=\frac{1}{1-2s}. $$

Answer 4

For generating functions (or in other words, over the ring of formal power series), it is an identity that

$$\sum_{n=0}^{\infty} x^n = (1 - x)^{-1}$$

Your example is the above, with $x = 2s$.

---

(For real numbers $x$, the identity $\displaystyle \sum_{n=0}^{\infty} x^n = \frac{1}{1-x}$ holds for $|x| < 1$, and this identity is the "same", except that for generating functions you don't have to care about the range of $x$, because you're treating $x$ as a symbol rather than a real number.)

---

There are many ways to prove the identity.

One is to observe that $$(1-x)\sum_{n=0}^{\infty}x^n = \sum_{n=0}^{\infty}(x^n - x^{n+1}) = 1 + \sum_{n=1}^{\infty}x^n(1 - 1) = 1.$$ So $(1-x)$ and the sum, when multiplied, give $1$, so each is the inverse of the other.

You can also derive this inverse, via the definition of $A(x)^{-1}$ when $A$ is a generating function. The inverse of a generating function $A(x) = \sum_{n=0}^{\infty} a_n x^n$, with $a_0 \neq 0$, is defined as $B(x) = \sum_{n=0}^{\infty}b_nx^n$ such that $1 = A(x)B(x)$. Note that the product $A(x)B(x)$ is defined as $C(x) = \sum_{n=0}^{\infty} c_nx^n$ with $c_n = \sum_{k=0}^{n} a_kb_{n-k}$.

So in this case, with $A(x) = (1-x)$ so that $a_0 = 1$ and $a_1 = -1$, we want:

$$1 = c_0 = a_0b_0 = 1b_0 \implies b_0 = 1,$$

$$0 = c_1 = a_0b_1 + a_1b_0 = b_1 - 1 \implies b_1 = 1,$$

$$0 = c_2 = a_0b_2 + a_1b_1 + a_2b_0 = b_2 - 1 + 0 \implies b_2 = 1,$$

$$0 = c_3 = a_0b_3 + a_1b_2 + a_2b_1 + a_3b_0 = b_3 - 1 + 0 + 0 \implies b_3 = 1,$$

and similarly you can prove by induction that $b_n = 1$ for all $n$, giving that $B(x) = \sum_{n=0}^{\infty} 1x^n$, so

$$(1-x)^{-1} = \sum_{n=0}^{\infty} x^n.$$