Determine the numeric function corresponding to the following generating functions G(x)=4x^2+1/(x+1)(2x+1)
Answers
Step-by-step explanation:
What will be the sequence generated by the generating function 4x/(1-x)2? d) 0, 1, 1, 3, 5, 8, 13,… Explanation: The sequence should be 0, 4, 8, 12, 16, 20,…for the generating function 4x/(1-x)2, when basic generating function: 1/(1-x). 8.
Answer:
If you take f(x)=1/(1 − x − x2) and expand it as a power series by long division, say,
then you get f(x)=1/(1−x−x2)=1+x+2x2 +3x3 +5x4 +8x5 +13x6 +···. It certainly
seems as though the coefficient of xn in the power series is the n-th Fibonacci number.
This is not difficult to prove directly, or using techniques discussed below. You can think
of the process of long division as generating the coefficients, so you might want to call
1/(1 − x − x2) the generating function for the Fibonacci numbers. The actual definition
of generating function is a bit more general. Since the closed form and the power series
represent the same function (within the circle of convergence), we will regard either one
as being the generating function.
Definition of generating function. The generating function for the sequence a0, a1,...
is defined to be the function f(x) = -
∞
n=0 anxn.
That is, the generating function for the sequence a0, a1,... is the function whose power
series representation has an as the coefficient of xn. We’ll call a0, a1,... the sequence
generated by f(x). We will not be concerned with matters of convergence, and instead
treat these as formal power series. Perhaps “symbolic” would be a better word than
formal.
When determining the sequence generated by a generating function, you will want to get
a formula for the n-the term (that is, for the coefficient of xn), rather than just computing
numerical values for the first few coefficients.
Useful facts.
• If x = 1 then 1+x+ x2 + ···+ xr = xr+1−1
x−1 (although it is often best not to do anything
with sums of only a few terms).
• 1
1−x =1+ x + x2 + ···.
Both of these facts can be proved by letting S be the sum, calculating xS − S, and doing
a little bit of algebra.
The second fact above says that 1
1−x is the generating function for the sequence 1, 1, 1, 1,....
It also lets you determine the sequence generated by many other functions. For example:
• 1
1−ax = 1+ a + a2x2 + a3x3 + ··· = -
∞
n=0 anxn. To see this, substitute y = ax
into the series expansion of 1
1−y
. Thus 1
1−ax is the generating function for the sequence
a0, a1, a2,.... The coefficient of xn is an.
1
1+ax = 1 − a + a2x2 − a3x3 + ··· = -
∞
n=0(−1)nanxn. To see this, substitute y = (−a)x
into the series expansion of 1
1−y
. Thus 1
1+ax is the generating function for the sequence
a0, −a1, a2,.... The coefficient of xn is (−a)n = (−1)nxn.
More useful facts.
• 1
1−x
k = -
∞
n=0 n+k−1
n
xn.
• 1
1−ax k = -
∞
n=0 n+k−1
n
anxn.
• 1
1+ax k = -
∞
n=0(−1)nn+k−1
n
anxn.
To see the first of these, consider the LHS, (1 + x + x2 + ···)k, multiplied out, but not
simplified, Each term is a product of k (possibly different) powers of x (remembering
that x0 = 1). By the rules of exponents, xn1 xn2 ··· xnk = xn1+n2+···+nk . Thus, after
simplifying, there is a term xn for every way of expressing n as a sum of k numbers each
of which is one of 0, 1, 2,.... That is, the number of terms xn equals the number of integer
solutions to n1 + n2 + ··· + nk = n, 0 ≤ ni, ∀i. We know that this number is n+k−1
k−1
(count using “bars and stars”).
To see the second fact, let y = ax in 1
1−y
k
. (This is the same idea as before.) To see the
third fact, let let y = −ax in 1
1−y
k
.
Multiplying a generating function by a constant multiplies every coefficient by that con-
stant. For example, 3
1+5x = 3 1
1+5x = 3(1 − 5x + 52x2 − 53x3 + ···)=3 − 3 · 5x + 3 · 52x2 −
3 · 53x3 + ··· = -
∞
n=0 3 · (−1)n5nxn. The coefficient of xn is 3 · (−1)n5n.
Multiplying a generating function by xk “shifts” the coefficients by k. This has the effect
of introducing k zeros at the start of the sequence generated. For example,
x
1+7x
4 = x4 1
1+7x
4
= x4 -
∞
n=0(−1)nn+4−1
n
7nxn
= -
∞
n=0(−1)nn+4−1
3
7nxn+4
= -
∞
t=4(−1)t−4t−1
3
7t−4xt
.
(Let t = n + 4 in the second last sum. If n = 0 then t = 4, so that gives the lower limit
for the sum. If n → ∞, so does t, which gives the upper limit. And n = t − 4.) Since
(−1)t−4 = (−1)t
, the last sum equals: -
∞
t=4(−1)t
t−1
3
7t−4xt
. The coefficient of xt is zero
if t < 4, and (−1)t
t−1
3
7t−4 if t ≥ 4.