I do believe it's dummy question, but I would be grateful if one explains me why following generating function is valid. I'm novice in the topic and intuitively I can't understand why it's true.
It's well known OGF with 1, 1, 1, …. is generating function for
$\frac{1}{(1-x)} = 1 + x^2 + x^3 + … + x^n = \sum_{i=0}^\infty x^i$
it's easily proved by
$A = 1 + x + x^2… = 1 + x(1 + x + x^2…) = 1 + x*A$
The question is how to validate it using the real numbers. Suppose we have $x = 10$ then
$\frac{1}{1 – 10} = \frac{1}{-9} = 1 + 10 + 100 + 1000… $ which doesn't seem to be true.
Could you please point me to the error in my conclusions?
Best Answer
The series $\sum_{k\ge 0}x^k$ converges if and only if $|x|<1$, so the only real numbers that you can meaningfully substitute into the equation
$$\frac1{1-x}=\sum_{k\ge 0}x^k$$
are those in the interval $(-1,1)$. But generating functions are formal power series; as such they are to be thought of as algebraic objects with an associated ‘arithmetic’, not as real- or complex-valued functions. As Herbert S. Wilf says in his book generatingfunctionology, ‘A generating function is a clothesline on which we hang up a sequence of numbers for display’. In most cases of interest, however, the power series actually does converge on some domain, and on that domain we can also treat it as an analytic object, the function that it represents on that domain. Outside that domain the formal operations on generating functions still make sense, but the series no longer represents the function. This turns out not to be a problem.
Chapter $2$ of generatingfunctionology starts with a brief introduction to formal power series; you can freely download the whole book here. Section $2.4$ then gives an outline of the analytic theory.