11
$\begingroup$

I understand that by definition, Fibonacci generating function is written as

$$F(x) = 0x^0 + 1x^1 + 1x^2 + 2x^3 + 3x^4 + \cdots$$

The deduction process (provided in the end) also looks good to me that

$$F(x) = \frac{x}{1 - x - x^2}$$

What I cannot understand is that in the original form,

$$F(1) = 0 + 1 + 1 + 2 + 3 + \cdots = \infty$$

yet, the closed form gives

$$F(1) = \frac{1}{1 - 1 - 1} = -1$$

Could someone help me understand what I've missed here? Thanks.

The deduction process is as below.

$$F(x)x^2 = 0x^2 + 1x^3 + 1x^4 + 2x^5 + 3x^6 + \cdots + F_{n-2}x^n + \cdots \tag{1}$$ $$F(x)x = 0x^1 + 1x^2 + 1x^3 + 2x^4 + 3x^5 + \cdots + F_{n-1}x^n + \cdots \tag{2}$$ $$F(x) = 0x^0 + 1x^1 + 1x^2 + 2x^3 + 3x^4 + \cdots + F_{n}x^n + \cdots \tag{3}$$

$(3)-(2)-(1)$ and we have

$$F(x)-F(x)x-F(x)x^2=F_0x^0+(F_1-F_0)x^1=x$$

Rearrange and we have

$$F(x)(1-x-x^2)=x$$ $$F(x)=\frac{x}{1-x-x^2}$$

I didn't find the deduction process depend on $x$ be in a certain range like $|x| < 1$.


Related: Does generating function always have a convergence domain?

$\endgroup$
9
  • 15
    $\begingroup$ The series is only valid in its domain of convergence and $x = 1$ is outside that domain. You see the same issue already with the geometric series $\frac{1}{1 - x} = 1 + x + x^2 + \dots $ and substituting $x = 2$, say. $\endgroup$ Commented Jun 14 at 5:23
  • 1
    $\begingroup$ But I didn't find the deduction process depend on x be in a certain range like |x| < 1. Could you please further clarify? I'm new to this kind of stuff. Sorry if it's a dumb question. $\endgroup$
    – Lingxi
    Commented Jun 14 at 5:44
  • 8
    $\begingroup$ The "deduction process" doesn't depend on anything, but just saying "the generating function is $x+x^2+2x^3+\dotsb$" does depend on $|x|$ being less than $(\sqrt5-1)/2$. Just because you can write down a power series, doesn't mean it converges for all values of $x$. The deduction process says that if the power series converges, then it equals $x/(1-x-x^2)$, but the deduction process doesn't tell you when the power series converges. $\endgroup$ Commented Jun 14 at 6:12
  • 2
    $\begingroup$ A formal power series uses $x^n$ as a placeholder for the $n^{th}$ term and the familiar notation of $x^n$ as indicating how the arithmetic works. The whole set-up can be formalised without the notion of convergence. However, if you start replacing $x$ by some real or complex number rather than using it as a placeholder, then issues of convergence have to be addressed. $\endgroup$ Commented Jun 14 at 6:14
  • 4
    $\begingroup$ Usually, we treat a generating function as a formal series for which questions of convergence are irrelevant – we don't worry about whether it converges for this or that value of $x$, we never have any reason to evaluate it, it just serves as a convenient way to do calculations with the sequence of coefficients. What did you hope to learn by computing $F(1)$? What meaning were you expecting to confer upon the result? $\endgroup$ Commented Jun 14 at 6:16

5 Answers 5

22
$\begingroup$

In going from $$F(x) = x + x^2 + 2x^3 + 3x^4 + \cdots + F_n x^n + \cdots \tag{1}$$ to the form $$F(x) = \frac{x}{1-x-x^2}, \tag{2}$$ where $F_n$ is the $n^{\rm th}$ Fibonacci number satisfying the recursion $$F_{n+1} = F_n + F_{n-1}, \quad F_0 = 0, \quad F_1 = 1, \tag{3}$$ how does one proceed? One way is to write $$x F(x) = x^2 + x^3 + 2x^4 + \cdots + F_{n-1} x^n + F_n x^{n+1} + \cdots, \tag{4}$$ hence $$\begin{align} F(x) + x F(x) &= x + 2x^2 + 3x^3 + \cdots + (F_n + F_{n-1})x^n + (F_{n+1} + F_n)x^{n+1} + \cdots \\ &= x + 2x^2 + 3x^3 + \cdots + F_{n+1} x^n + F_{n+2} x^{n+1} + \cdots \\ &= \frac{1}{x}(x^2 + 2x^3 + 3x^4 + \cdots + F_{n+1} x^{n+1} + \cdots ) \\ &= \frac{1}{x}(-x + F(x)) \\ &= -1 + \frac{F(x)}{x}. \tag{5} \end{align}$$ Thus $$\left( \frac{1}{x} - 1 - x \right) F(x) = 1, \tag{6}$$ from which $(2)$ directly follows. Now you might look at this proof and think that at no step did we require $x$ to be within some radius of convergence. But in fact, we did! It's just hidden (or some would say, overlooked). The key is in the use of the ellipses "$\cdots$." To see why, let's modify the proof slightly by considering a series of generalized functions, which we will define as $$G_n(x) = x + x^2 + 2x^3 + \cdots + F_n x^n. \tag{7}$$ Here, $G_n$ is a polynomial of degree $n$, whose coefficients are the Fibonacci numbers. What happens when we try to work with $G_n$ instead of $F$? The same steps as before give us $$x G_n(x) = x^2 + x^3 + 2x^3 + \cdots + F_{n-1} x^n + F_n x^{n+1}, \tag{8}$$ but now, $$G_n(x) + x G_n(x) = x + 2x^2 + 3x^3 + \cdots + F_{n+1} x^n \color{red}{+ F_n x^{n+1}}, \tag{9}$$ because unlike with the infinite series of $F$, the degree $n+1$ term from $x G_n(x)$ does not have a corresponding term in $G_n(x)$ of the same degree to add together. Then $$\begin{align} (1+x)G_n(x) &= \frac{1}{x}\left(x^2 + 2x^3 + 3x^4 + \cdots + F_n x^n\right) + F_{n+1} x^n + F_n x^{n+1} \\ &= \frac{1}{x}(-x + G_n(x)) + F_{n+1} x^n + F_n x^{n+1}. \tag{10} \end{align}$$ Now this time, if we solve for $G_n(x)$, we obtain $$G_n(x) = \frac{x}{1-x-x^2} \left(1 - F_{n+1} x^n - F_n x^{n+1}\right). \tag{11}$$ In the limit as $n \to \infty$, the term in parentheses should tend toward $1$, since $\lim_{n \to \infty} G_n(x) = F(x)$. But is this always the case? Well, if we require $1 - F_{n+1} x^n - F_n x^{n+1} \to 1$, that would mean we need $$\lim_{n \to \infty} F_{n+1} x^n + F_n x^{n+1} = 0. \tag{12}$$ But if we were to select, say, $x = 1$, then this would mean $$\lim_{n \to \infty} F_{n+1} + F_n = \lim_{n \to \infty} F_{n+1} = 0,$$ which is of course false. So for such a choice of $x$, the equivalence of $(1)$ and $(2)$ does not hold, because we have shown that in the limit, the sequence of functions $G_n$ evaluated at this point does not converge. Moreover, our work provides a criterion $(12)$ for all $x$ for which we can say that $(1)$ and $(2)$ are equivalent, for if $(12)$ is true, then $(11)$ tends to $(2)$ as $n \to \infty$.

It turns out that $(12)$ implies that $$|x| < \frac{-1 + \sqrt{5}}{2}.$$ A proof is not in the scope of this discussion, but the reader is welcome to attempt one as an exercise. It is not a coincidence that the boundary of this interval is one of the roots of $1-x-x^2$ of the denominator in $(2)$.

$\endgroup$
5
  • 2
    $\begingroup$ Your answer is informative and inspiring. Can I also reason like if $F(x)$ does not converge, $F(x) + xF(x)$ becomes addition of two infinite numbers and that is not meaningful? So one condition for the deduction to hold is that $F(x)$ converges to some finite number? $\endgroup$
    – Lingxi
    Commented Jun 14 at 8:35
  • $\begingroup$ @Lingxi Yes, that is generally correct. $\endgroup$
    – heropup
    Commented Jun 14 at 16:07
  • 1
    $\begingroup$ It might be interesting to note that if you consider $G(x) = \sum_{n=0}^\infty F_n x^n$ as a member of the ring of formal power series $\mathbb{R}[[x]]$, then a very similar argument shows $(1 - x - x^2) G(x) = x$. (And in general, any power series with a nonzero constant coefficient is a unit of this ring, i.e. it has a multiplicative inverse; so it makes sense to say $G(x) = \frac{x}{1 - x - x^2}$ in this ring.) $\endgroup$ Commented Jun 14 at 16:32
  • 3
    $\begingroup$ @Lingxi You seem to be ignoring the essential remark that generating "functions" are not really functions but rather formal power series (which makes the above answer mostly irrelevant). The equality $\,x/(1-x-x^2) = \sum f_k x^k\,$ denotes an equality of formal power series, i.e. both sides have equal coef's of $\,x^k,\,$ just like for formal polynomials (vs. polynomial functions). Similarly rational "functions" are not functions but, rather, fractions of formal polynomials. $\ \ $ $\endgroup$ Commented Jun 14 at 23:50
  • $\begingroup$ @BillDubuque After some meditation, I finally seem to get around this. Could you please expand on the comment, elaborate a little bit more, and post as an answer? I really would like to accept the answer that is most on spot. $\endgroup$
    – Lingxi
    Commented Jun 15 at 3:28
3
$\begingroup$

Your deduction process shows that when $$F(x)=\sum_{n\ge0}F_nx^n$$ is considered as a formal power series, $$(1-X-X^2)F(X)=X\in\Bbb Z[[X]].$$ If, instead, you consider $F(x)$ as a power series, its radius of convergence is $$R=\varphi^{-1}$$ and you can reinterpret your deduction process as a proof that $$\forall x\in(-R,R)\quad(1-x-x^2)F(x)=x\in\Bbb R.$$ (Incidentally, this is also a corollary of the previous equality of formal power series.)

But for every real number $x\ge R$, we have $F(x)=\infty$ (as you noticed for $x=1$), and following your deduction process step by step, what you get is only $$(x+x^2)F(x)+x=F(x),$$ which means nothing more than $(x+x^2)\infty+x=\infty$. For instance with $x=1$: $$2\cdot\infty+1=\infty$$ is correct, but it is foolish to derive from it that the indeterminate form $2\cdot\infty-\infty$ equals $-1$.

$\endgroup$
2
$\begingroup$

The statement

$$F(x) = x + x^2 + 2x^3 + 3x^4 + \cdots + F_n x^n + \cdots \tag{1}$$

is understood to mean

$$F(x) = lim_{k \rightarrow \infty} \sum_{n=0}{k} F_n x^n$$

So simply to treat the generating function as a valid function (as opposed to a formal power series) is to assert that it converges, which requires that $x$ be in the radius of convergence. Even if we treat $\infty$ as being a valid value for a series to converge to, we still run into a problem.

In heropup's answer, they go from

$$F(x) + x F(x)=-1 + \frac{F(x)}{x}.$$ and then immediately go to $$\left( \frac{1}{x} - 1 - x \right) F(x) = 1$$

as if that clearly follows. And yet there are quite a few algebraic steps between those statements. We would add 1 to both sides. Then we would cancel out the -1 and 1. Then we would subtract $F(x)+xF(x)$ to both sides. And then we would cancel out the $F(x)+xF(x)$ and $-(F(x)+xF(x))$.

And here is where the problem lies. For even if we were treating $\infty$ as being a valid limit, the normal laws of algebra do NOT apply to it. $\infty-\infty$ is NOT zero, it's undefined. So we can't cancel $F(x)+xF(x)$ and $-(F(x)+xF(x))$ unless we have shown that $F(x)$ is finite.

$\endgroup$
1
$\begingroup$

There are already answers to my question as is. Yet, after reading through the many good comments and the related question Does generating function always have a convergence domain?, I learned something more beyond the original question. So I post my own answer here, hoping that it gives you a more comprehensive view of this topic.

Let's begin with the infinite power series $F(x)=\sum_{n\to\infty}{F_nx^n}$. Depending on how you interpret it, as either a regular or formal power series, different hypotheses and manipulation rules apply.

In the case of regular series, regular manipulation rules apply where operands of addition, subtraction, etc., must be finite numbers. E.g., the identity $x-(x-1)=1$ only holds when $x$ is a finite number. Hence in the original question, the deduction is only valid when $F(x)$ converges for some $x$. Ignore the trivial case of $x=0$ which is not useful here and then $F(x)$ must have a non-zero radius of convergence domain for the deduction to hold. Since $1$ is not within the convergence domain, the deduction is invalid for $x=1$ and hence the "contradiction".

In the case of formal regular series, another set of manipulation rules apply that does not require convergence of $F(x)$. The deduction holds regardless. The "contradiction" is then caused by the attempt to evaluate $F(x)$ in a regular sense which is invalid in the field of formal power series.

As a mathematical tool to analyze infinite series, generating functions like $F(x)$ in general are to be dealt with as a formal power series. In this sense, I asked the wrong question with the implication of treating $F(x)$ as a regular power series.


I'm not a math major. Feel free to correct if anything is imprecise or wrong.

$\endgroup$
1
$\begingroup$

Let's recall that a sequence is represented by its generating function in the sense that its elements appear as the coefficients inside the Taylor series of the said function. Yet, Taylor series are not guaranteed to converge everywhere $-$ we are usually interested in working with generating functions in the neighbourhood of the origin only. In consequence, the identity $\sum_{n\ge0} F_nx^n = \frac{x}{1-x-x^2}$ is not true for all $x$ (a priori).

Moreover, when deriving this identity, you couldn't be sure that the deduction steps held for all $x$, because the quantity $\sum_{n\ge0} F_nx^n$ might not be defined, what you understood by noticing that $F(1) = \infty$. In other words, even if you didn't invoke a restriction on the domain of $F$ in the process, it cannot be ensured to be valid for every values of $x$, since its reason might apply to a non-existing object $F$.

Finally, it is to be noted that the radius of converge of Taylor series corresponds to the distance between its base point and the nearest singularity (in the complex plane). In the present case, singularities are characterized by the equation $x^2-x-1 = 0$, whose smallest root is given by $\frac{1-\sqrt{5}}{2}$. Consequently, all our manipulations make sense only within the range $|x| < \left|\frac{1-\sqrt{5}}{2}\right|$ (and $1$ doesn't belong to this domain by the way).

$\endgroup$
1
  • $\begingroup$ @GerryMyerson You're right, thank you. Now corrected. $\endgroup$
    – Abezhiko
    Commented Jun 15 at 17:47

Not the answer you're looking for? Browse other questions tagged .