Scribd
Upload
27 views4 pages

Generating Functions and Fibonacci Sequence

Easy

Uploaded by

Aanjaney Mishra
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
27 views4 pages

Generating Functions and Fibonacci Sequence

Easy

Uploaded by

Aanjaney Mishra
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

MIT 18.

211: COMBINATORIAL ANALYSIS

FELIX GOTTI

Lecture 15: Generating Functions I: Generalized Binomial Theorem


and Fibonacci Sequence
In this lectures we start our journey through the realm of generating functions.
Roughly speaking, a generating function is a formal Taylor series centered at 0, that
is, a formal Maclaurin series. In general, if a function f (x) is smooth enough at x = 0,
then its Maclaurin series can be written as follows:
∞
X f (n) (0) n
(0.1) x ,
n=0
n!

where f (n) (x) is the n-th derivative of f (x). We know from Calculus that the Maclaurin
series of the function (1 − x)−1 is
∞
1 X
(0.2) = xn .
1 − x n=0
The Maclaurin series of every polynomial function is itself. In particular, the Bino-
mial Theorem gives us an explicit formula for the Maclaurin series/polynomial of any
nonnegative integer power of the binomial 1 + x:
m  
m
X m n
(1 + x) = x .
n=0
n
But what if we want to compute the Maclaurin series of (1 + x)r when r is not a
nonnegative integer?

Generalized Binomial Theorem. The Generalized Binomial Theorem allows us to


express (1 + x)r as a Maclaurin series using a natural generalization of the binomial
coefficients. For any r ∈ R and n ∈ N0 , we set
 
r r(r − 1) · · · r − n + 1
(0.3) := .
n n!
Observe that when r ∈ N0 , we recover the standard formula for the binomial coeffi-
cients. We are now in a position to generalize the Binomial Theorem.
1
2 F. GOTTI

Theorem 1. For any r ∈ R,


∞  
r
X r n
(0.4) (1 + x) = x .
n=0
n

Proof. Set f (x) = (1 + x)r . For each n ∈ N0 , we see that f (n) (x) = (r)n (1 + x)r−n ,
and so f (n) (0)/n! = nr . Therefore the Maclaurin formula of f (x) is that one in the
right-hand side of (0.4). 
As an application of Theorem 1, we can generalize (0.2).
Example 2. Let us find the Maclaurin series of (1 − x)−m when m ∈ N. First, note
that for each n ∈ N0 ,
n−1
(−1)n
 
−m 1 Y
= (−m − i) = m(m + 1) · · · (m + n − 1)
n n! i=0 n!
 
n (m + n − 1)! n m+n−1
= (−1) = (−1) .
n!(m − 1)! m−1
Now in light of Theorem 1,
∞   ∞   ∞  
−m
X −m n X n m+n−1 n
X m+n−1
(1 + x) = x = (−1) x = (−x)n .
n=0
n n=0
m − 1 n=0
m − 1
Evaluating the previous identity at −x, we obtain that
∞  
−m
X m+n−1 n
(1 − x) = x .
n=0
m−1

Generating Function of a Sequence. P We can associate to any sequence (an )n≥0 of


real numbers the formal power series ∞ n=0 a n x n
. We call this P
formal power series the
(ordinary) generating function of the sequence (an )n≥0 . When ∞ n=0 an converges to a
function F (x) in some neighborhood of 0, we also call F (x) the (ordinary) generating
function of (an )n≥0 .
Example 3. The generating function of a sequence (an )n≥0 satisfying that an = 0 for
every n > d is the polynomial dn=0 an xn .
P

Example 4. It follows from (0.2) that (1 − x)−1 is the generating function of the
constant sequence all whose terms equal 1.
Example 5. For each m∈ N, we have seen in Example 2 that the generating function
of the sequence m+n−1
m−1 n≥0
is (1 − x)−m .
We can actually use generating functions to find explicit formulas for linear recur-
rence relations. The following example illustrates how to do this.
COMBINATORIAL ANALYSIS 3
Example 6. Consider the sequence (an )n≥0 recurrently defined as follows: P a0 = 2 and
an+1 = 5an for every n ∈ N0 . Let us find a closed formula for
Pa∞n . Let F (x) =P ∞ n=0 an x
n
n ∞ n
be the generating
P∞ function of the sequence (an )n≥0
P∞. Sincen n=0 an+1 x = n=0 5an x ,
n
P ∞ n+1
we see that n=1 an x = n=0 an+1 x = 5x n=0 an x and, therefore,
∞
X ∞
X
n
F (x) = 2 + an x = 2 + 5x an xn = 2 + 5xF (x).
n=1 n=0

Hence F (x) = 2(1 − 5x)−1 , and so


∞ ∞ ∞
X
n 2 X
n
X
an x = F (x) = =2 (5x) = 2 · 5n xn ,
n=0
1 − 5x n=0 n=0

from which we can obtain the desired explicit formula for an , namely, an = 2 · 5n for
every n ∈ N0 .

Recall that the Fibonacci sequence is defined by the recurrence Fn+1 = Fn + Fn−1 ,
where F0 = 0 and F1 = 1. Let us conclude this lecture providing an explicit formula
for the Fibonacci numbers.

Example 7. Let F (x) be the generating function of the Fibonacci sequence. Then
∞
X ∞
X ∞
X
n+1 n 2
F (x) − x = Fn+1 x =x Fn x + x Fn−1 xn−1 = xF (x) + x2 F (x).
n=1 n=1 n=1

Solving for F (x), we obtain that


 
x A B
F (x) = − 2 =− + ,
x +x−1 x−α x−β
for some A, B ∈ R, where α and β are the real roots of x2 + x − 1. From x =
α β
A(x − β) + B(x − α), we can readily deduce that A = α−β and B = β−α . Thus,
A B 1  x −1 1  x −1
F (x) = + = 1− + 1−
α−x β−x α−β α β−α β
∞ ∞ ∞
1 X x n  1 X x n X α−n
   β −n  n
= + = + x .
α − β n=0 α β − α n=0 β n=0
α−β β−α
√ √
−1+ 5 −1− 5
Taking α = 2
and β = ,
we obtain the following explicit formula:
2
√ √
1  2 n 1  2 n 1  1 + 5 n 1  1 − 5 n
Fn = √ √ −√ √ =√ −√ .
5 −1 + 5 5 −1 − 5 5 2 5 2
4 F. GOTTI

Practice Exercises
Exercise 1. Consider the sequence (an )n≥0 satisfying that a0 = 3 and an+1 = 5an + 7n
for every n ∈ N0 . Find an explicit formula for an .

Exercise 2. Find a closed form for the generating function of the sequence (n2 )n≥0 .

Department of Mathematics, MIT, Cambridge, MA 02139


Email address: fgotti@[Link]

Common questions

Powered by AI

Generating functions simplify the computation of sequences like the binomial coefficients by transforming combinatorial problems into algebraic problems. They allow for systematic expansion, manipulation, and evaluation using power series, which can significantly reduce complexity. Generating functions tie together otherwise separate concepts such as coefficients and recursion, and help in unifying disparate elements of combinatorial identities into a single framework, facilitating easier computation and formulation of complex identities .

The generating function for the Fibonacci sequence \((F_n)\) is derived by setting \(F(x) = \sum_{n=0}^{\infty} F_n x^n\). Using the recurrence \(F_{n+1} = F_n + F_{n-1}\), we manipulate the series to obtain \(F(x) = \frac{x}{x^2 + x - 1}\). By expressing \(x^2 + x - 1\) in terms of its roots \(\alpha = \frac{-1 + \sqrt{5}}{2}\) and \(\beta = \frac{-1 - \sqrt{5}}{2}\), the function becomes: \(F(x) = \frac{1}{\sqrt{5}}\left(\frac{1}{1 - \frac{x}{\alpha}} - \frac{1}{1 - \frac{x}{\beta}}\right)\), leading to the explicit formula \(F_n = \frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right)\).

Generating functions encapsulate entire sequences into algebraic expressions, allowing us to manipulate and combine power series in ways that mirror combinatorial operations. For instance, by equating two series expansions, or using algebraic operations on generating functions, one can derive identities involving binomial coefficients. For example, the generating function for \(\binom{m+n-1}{m-1}\) is \((1-x)^{-m}\), and expanding it using the binomial theorem reveals and proves identities involving summations over binomial coefficients quickly .

A formal power series can represent a sequence \((a_n)_{n \ge 0}\) as an infinite series \(\sum_{n=0}^{\infty} a_n x^n\). For constant sequences, such as the sequence where all terms are 1, the generating function is \((1-x)^{-1}\). For a sequence \((a_n)\) where \(a_n = 0\) for \(n > d\), the generating function is a polynomial \(\sum_{n=0}^{d} a_n x^n\).

The Generalized Binomial Theorem defines the coefficients \(\binom{r}{n}\) as \(\frac{r(r-1)...(r-n+1)}{n!}\). When \(r\) is a nonnegative integer, this definition coincides with the standard binomial coefficients \(\binom{m}{n}\) for \(m \ge n\). This is because in the case of \(r = m\), the factors reduce naturally to \(m!\), which cancels out in the denominator, reproducing the familiar binomial formula .

The roots of the polynomial \(x^2 + x - 1\) are crucial in deriving the Fibonacci sequence's generating function. These roots, \(\alpha = \frac{-1 + \sqrt{5}}{2}\) and \(\beta = \frac{-1 - \sqrt{5}}{2}\), are used to decompose the generating function \(\frac{x}{x^2+x-1}\) into partial fractions. These partial fractions directly lead to Binet's formula: \(F_n = \frac{1}{\sqrt{5}}\left(\alpha^n - \beta^n\right)\). This process illustrates how generating functions can reveal underlying algebraic structures of sequences, connecting them to classical results like Binet's formula .

To derive explicit formulas for linear recurrence sequences using generating functions, we express each term of the sequence as coefficients in a power series. This is converted into an equation by comparing the series representation of the recurrence relation. Solving the resulting equation provides the generating function in a closed form. For example, a sequence defined by \(a_0 = 2\) and \(a_{n+1} = 5a_n\) yields the generating function \(F(x) = \sum_{n=0}^{\infty} a_n x^n = \frac{2}{1-5x}\), leading to the explicit formula \(a_n = 2 \times 5^n\).

The Generalized Binomial Theorem extends the traditional binomial theorem to any real number \(r\). It allows expressing \((1 + x)^r\) as an infinite series: \((1 + x)^r = \sum_{n=0}^{\infty} \binom{r}{n} x^n\), where \(\binom{r}{n} = \frac{r(r-1)...(r-n+1)}{n!}\). This reduces to the standard binomial coefficients when \(r\) is a nonnegative integer .

Generating functions can be used to solve linear recurrence relations by transforming the recurrence into an equation involving power series. For a sequence \((a_n)_{n \ge 0}\) defined by a recurrence like \(a_{n+1} = c a_n + f(n)\), the generating function \(F(x) = \sum_{n=0}^{\infty} a_n x^n\) transforms the recurrence into a more manageable algebraic equation. Solving this algebraic equation typically involves expressing \(F(x)\) as a closed form or series, which can then be used to derive a formula for \(a_n\). For example, a sequence defined as \(a_0 = 2\) and \(a_{n+1} = 5a_n\) leads to the generating function \(F(x) = \frac{2}{1-5x}\), providing \(a_n = 2 \cdot 5^n\).

Finding the generating function for \((n^2)_{n \ge 0}\) involves recognizing the series as a second-degree polynomial in terms of \(n\). General techniques include using known generating functions and calculus operations to manipulate series. Starting with the known generating function for the constant sequence, \((1-x)^{-2}\) for \(n\), differentiating with respect to \(x\) gives \(\sum n x^{n-1}\), which is adjusted to handle \(n^2\) by further operations like multiplication by \(x\) and additional manipulation. This results in a generating function that encapsulates the desired sequence in a closed form .

You might also like