I was looking up the derivations of Catalan numbers, and one derivation (probably the most famous) involves generating functions that leads to:

$$C(x) = \frac{1}{2} (1 - \sqrt{1-4x})$$

And then this square root piece gets processed via a Taylor series expansion.

I would never in a million years have been able to figure that out. What exactly does Taylor expansion do -- just provide a series that equals whatever arbitrary function you give it (assuming the function has a derivative)? How do I know this expansion is true? How do I derive it (as I constantly find that I fail to memorize it cold; I memorize better when I understand where it came from)? Is it exactly the same or just an approximation?

  • 2
    $\begingroup$ Is your question how to derive the Taylor series for $\sqrt{1-4x}$ or derive that the given series equals $\sqrt{1-4x}$? $\endgroup$
    – robjohn
    Jul 26, 2016 at 21:00
  • $\begingroup$ Maybe the Catalan stuff is distracting but it's just an example of a situation I'll encounter where someone said "Taylor expansion can allow us to proceed!" So I am trying to understand what Taylor expansion does, when it's appropriate to use it, how to derive it, etc. $\endgroup$
    – KaliMa
    Jul 26, 2016 at 21:02
  • $\begingroup$ For example I already know that you just apply this expansion to the function: en.wikipedia.org/wiki/Taylor_series#Definition $\endgroup$
    – KaliMa
    Jul 26, 2016 at 21:02
  • 1
    $\begingroup$ taylor expansion allows us to DEFINE a generating function in usual way $\endgroup$
    – tired
    Jul 26, 2016 at 21:05

2 Answers 2


We're not really in the world of functions any more. A generating function is not really something you plug a number into to get a number out of it — it is a "formal power series" where the important part of the structure is precisely that it has a sequence of coefficients, and you have the various arithmetic operations you perform on them.

There are ways to make sense of evaluating a formal power series at certain kinds of things. One sort of thing is that some power series really are "convergent" on some domain in the sense of calculus, and so you can use ideas about doing analysis with functions to study them. But that's not necessarily relevant here; it depends on how you want to do the calculations.

For a formal power series, that it equals its Taylor series is a triviality. If we have

$$ f(x) = \sum_{n=0}^\infty a_n x^n $$

Remember that this notation isn't necessarily viewed as actually defining a sum! The important thing is its sequence of coefficients. (although with the right tools from topology and/or abstract algebra we can view it as an actual infinite sum)

then by definition its derivative is

$$ f'(x) = \sum_{n=0}^\infty a_n n x^{n-1} = \sum_{n=0}^\infty a_{n+1} (n+1) x^n$$

and more generally its $k$-th derivative is

$$ f^{(k)}(x) = \sum_{n=0}^{\infty} a_{n+k} \frac{(n+k)!}{n!} x^n $$

For any power series it does make sense to define $f(0)$ to be the constant term. Thus,

$$ f^{(k)}(0) = k! a_k $$

and thus we have the identity

$$ f(x) = \sum_{n=0}^{\infty} \frac{f^{(n)}(0)}{n!} x^n $$

Here, when we write $\sqrt{1 - 4x}$, we don't mean that as a function, we mean that as a formal power series. It turns out any power series $f(x)$ with $f(0) > 0$ has a square root — that is, there is a unique power series $g(x)$ such that $g(0) > 0$ and $g(x)^2 = f(x)$.

Of course, we can show that the Taylor series for the function $\sqrt{1-4x}$ is satisfies this property, and so that Taylor series is the formal power series $\sqrt{1-4x}$.

Alternatively, we can show the derivative laws all still hold here, and compute

$$ \left( \sqrt{1 - 4x} \right)' = \frac{-2}{\sqrt{1-4x}} $$

and so forth.

  • $\begingroup$ $f'(x) = \sum_{n=0}^\infty a_n n x^{n-1} = \sum_{n=0}^\infty a_{n+1} (n+1) x^n$ -- sorry, what? How did you get from the middle expression to the right expression? $\endgroup$
    – KaliMa
    Jul 26, 2016 at 21:15
  • $\begingroup$ @KaliMa: Discard the $n=0$ term and substitute $n \mapsto n+1$ $\endgroup$
    – user14972
    Jul 26, 2016 at 21:15
  • $\begingroup$ Is this only done because $a_n n x^{n-1} = 0$ at $n=0$? $\endgroup$
    – KaliMa
    Jul 26, 2016 at 21:16
  • $\begingroup$ @KaliMa: You could skip the middle entirely; I only put it there to make the analogy with the usual derivative more clear. My whole post could be written somewhat better, but I'm feeling really sick, and I thought it still worth posting what I had written rather than hold onto it until I feel better. $\endgroup$
    – user14972
    Jul 26, 2016 at 21:18
  • 1
    $\begingroup$ @KaliMa In the context of combinatorics, discrete math, and power series, we define $0^0$ to be $1$. Note only does this mean we can write polynomials and power series uniformly with summation notation, but it is consistent with the combinatorial interpretation of $n^m$ as the number of functions from a size $m$ set to a size $n$ set (when $n=m=0$ there is precisely one function $\varnothing\to\varnothing$, called the empty function, where functions $X\to Y$ are defined as subsets of $X\times Y$ satisfying a certain property to be a function). $\endgroup$
    – anon
    Jul 26, 2016 at 22:10

It's one thing to start with a power series and then derive a formula for it. There are various tricks for doing that in the generating function literature, and I assume you've seen this in the derivation you mentioned for the Catalan numbers' generating function. But I'm guessing what you're really wondering about is the other way around: beginning with a function (say defined by an algebraic formula), how and why do we get a corresponding Taylor series? You can find the answer to this in a rigorous calculus or introductory analysis class, but I will give a breezy explanation here.

Derivatives measure instantaneous rate of change, which is why they are approximately equal to rates of change over small intervals. Specifically, we have

$$f'(x)\approx \frac{f(x+h)-f(x)}{h} ~~\implies~~ f(x+h)\approx f(x)+f'(x)h $$

for small values of $h$. Consider $x$ to be fixed. The above allows us to approximate $f(x+h)$ by a linear function of $h$. Linear functions are one of the simplest functions there are. We can view them as sitting at the bottom of a hierarchy of more and more complicated functions - namely polynomials, with complexity measured by degree. So to get a better approximation than linear or "1st order" one, the next step would be to get a "quadratic" or "2nd order" approximation.

Write $f(x+h)\approx f(x)+f'(x)h+\square h^2$. We may solve via L'Hôpital's rule:

$$\square=\lim_{h\to0}\frac{f(x+h)-f(x)-f'(x)h}{h^2}=\lim_{h\to0}\frac{f'(x+h)-f'(x)}{2h}=\frac{1}{2}f''(x). $$

See the "geometric interpretation" or "special case proof" sections on Wikipedia to understand why L'Hôpital's is intuitively true. Anyway, we conclude our second-order approximation is

$$f(x+h)\approx f(x)+f'(x)h+\frac{1}{2}f''(x)h^2.$$

If we proceed this way indefinitely, we can get polynomial approximations of arbitrary order, eventually resulting in the power series

$$\begin{array}{ll} f(x+h) & \stackrel{?}{=} f(x)+f'(x)h+\frac{1}{2}f''(x)h^2+\frac{1}{6}f'''(x)h^3+\cdots \\ & \displaystyle =\sum_{n=0}^\infty \frac{f^{(n)}(x)}{n!}h^n. \end{array} $$

For "nice" functions $f$, this is a true equality for sufficiently small $h$.

So what's the use of functions' having Taylor series? Well, we can approximate functions for one thing. How do you think computers can calculate things like $\sin(0.2)$ or $e^5$? Alongside other techniques, they employ power series expansions. We can also compare complicated functions' growth rates to each other in asymptotic analysis. Taylor series are also used to solve differential equations, called the Frobenius method. In any case, we know what to do with polynomials - we do algebra with them! - and in math we try to reduce new things to old things as much as possible.

What about actually calculating the Taylor series of a function defined by some algebraic formula? A lot of the time, calculating the general $n$th derivative of $f$ at a point is impractical. This is why it's often helpful to use certain manipulations to do so instead, and rely on memorizing the Taylor expansions of a certain set of "archetypical" functions like $\cos(x),\sin(x),\exp(x)$, etc. For instance, to find the Taylor series of $\frac{\sin(x) e^x}{1+x^2}$, one might multiply the Taylor series for $\sin(x)$, $e^x$ and $\frac{1}{1+x^2}$, and one would find the Taylor series of $\frac{1}{1+x^2}$ by plugging $-x^2$ in for $u$ into the geometric series $\frac{1}{1-u}=1+u+u^2+\cdots$ (itself a special case of a Taylor series).

In combinatorics, counting numbers are sometimes collected together as coefficients of some power series called a generating function. Fundamentally, they are abstract algebraic objects and treated "formally," so for instance $\sum_{n=0}^\infty n!x^n$ and $\sum_{n=0}^\infty n!^2x^n$ would be different bona fide formal power series even though they both induce the very trivial function with domain and range $\{0\}$. But sometimes, if the coefficients do not grow too quickly, the power series defines a function - indeed, it is the Taylor series of a function around $0$. In these situations there is a question of if the power series defines a function that can be described by a simple formula.

This is backwards from finding Taylor series expansions of functions defined by algebraic formulas - now we're trying to find algebraic formulas for functions defined by power series expansions. One can do this again by playing around the the series (rearranging terms, splitting them up into pieces, factoring things, etc.) and trying to identify archetypical functions' series expansions in the noise.

A more sophisticated tact is to set $f(x)$ equal to the series, then apply $\frac{d}{dx}$ to the taylor series expansion, which can be done term-by-term and thus only uses the power rule for derivatives, until we can determine that $f(x),f'(x),f''(x),\cdots$ satisfy some algebraic relation based off of their coefficients, possibly with other functions $g(x)$. This gives us a differential equation that $f(x)$ is a solution to, and so we can use techniques from differential equations to solve if we're lucky.

More about Taylor series can be read about in books or good lecture notes which cover calculus rigorously or introductory analysis, and more about generating functions can be read about in e.g. "generatingfunctionology" (freely available online) or other good combinatorics books I guess.


You must log in to answer this question.

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