2

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?

Oleg
  • 123
  • 4
    The error is not in the conclusion, but in the question. One does not validate the identity using the real numbers. Why should one? But if one insists, one should use real numbers for which the series converges. As long as $|x|\lt1$, you're golden. – Gerry Myerson Oct 28 '13 at 12:13
  • 1
    Gerry, thank you very much. Now it's clear. Could you please post your comment as answer so I can accept it? – Oleg Oct 28 '13 at 12:21
  • Just an observation I find cute: for $|x| > 1$, by letting $y=1/x$, we have $\frac{1}{1-x} = \frac{1/x}{1/x - 1} = -\frac{y}{1 - y} = -y - y^2 - y^3 - y^4 - \dots$. And indeed $-\frac19 = \frac{1}{1-10} = -\frac{1}{10} - \frac{1}{10^2} - \frac{1}{10^3} - \dots$. So the generating function does have some bearing even in the case when $|x| > 1$; it's just not what you get by plugging it in directly (which you can't because it's not in the radius of convergence). – ShreevatsaR Mar 14 '14 at 04:34

1 Answers1

7

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.

Brian M. Scott
  • 616,228