These problems have 3 parts. Give the generating function, SUM(a_k x^k : k=0...), a name, some g(x) and using the recurrence relation and initial conditions express g(x) as some function like (using 2 and 5 for example) [c+dx]/(1-2x)(1-5x) .
Next we use some simple algebra and solving 2 equations in two unknowns ideas to express this function in the form A/(1-sx)
+B/(1-tx) = [A(1-tx) + B(1-sx)] / (1-sx)(1-tx) which we set equal to [c+dx]/(1-2x)(1-5x) and then, using just the numerators, we solve for A,B.
Finally we realize that 1/(1-sx) is just SUM( 2^k x^k : k=0...)
, hence
g(x) = SUM( (A*2^k + B5^k) x^k : k=0...), which
just
means that a_k = A*2^k + B*5^k for every k.
Let us use a generating function approach now. We set G(x)=SUM(a_k x^k : k=0... )
. The recurrence relation holds for k>0 so we take out the
0-th term, use the recurrence relation, and then
see how it can simplify:
G(x) = 5 + SUM( a_k * x^k : k = 1 ...) =
5 + SUM( (7a_(k-1)) * x^k : k=1... ) =
5 + SUM( 7a_(k-1) * x^k : k=1...)
There's the standard step of factoring out the x, the constant, and
then reindexing
G(x) = 5 + 7x * SUM( a_k * x^k : k = 0...) = 5 + 7x * G(x)
hence G(x) - 7x * G(x) = 5 or G(x) * (1 - 7x) = 5.
Finally we see that G(x) = 5 / (1-7x).
Now we have a nice closed form for G(x) and we must try to recognize it as a known function. Our tool is that 1/(1-bx) = SUM( b^k x^k : k=0...) which we know from Chapter 1.
So we have that
SUM(a_k * x : k=0...) = G(x) = 5 * 1/(1-7x) = 5* SUM( 7^k x^k :k = 0...),
hence equating powers of x for every k, we have that a_k = 5*7^k for every k.
Set H(x)=SUM(a_k * x^k : k=0...) and again observe that
H(x) = 1 + SUM(a_k x^k : k=1...) = 1 + SUM( (3*a_(k-1)+2) * x^k : k=1...)
=
1 + SUM(3a_(k-1) * x^k : k= 1...) + SUM(2*x^k : k=1...)
So
H(x) = 1 + 3x * SUM( a_k * x^k : k=0...) + 2x * SUM( x^k : k=0...)
Hence, H(x) = 1 + 3x * H(x) + 2x * ( 1/(1-x) ),
H(x)(1-3x) = 1 + 2x/(1-x)= [(1-x) + 2x]/(1-x), because
1 = (1-x)/(1-x)
H(x) = (1/(1-3x)) * [1+x]/(1-x) = [1+x]/(1-3x)(1-x),
this completes part
1.
Now set A/1-3x + B/1-x = [A(1-x) + B(1-3x)]/(1-3x)*(1-x) equal to [1+x]/(1-3x)(1-x), which just requires setting the numerators equal. Thus
(A+B) + (-A-3B)x = 1 + x which means that
A+B=1 and -A-3B=1. From the first we see that B=1-A which we can substitute into the second: -A-3(1-A)=2A-3=1 , hence A=2 and B=-1. Thus, completing part 2:
H(x) = 2/1-3x
+(-1)/1-x.
Finally, part 3, we have that
SUM(a_k x^k : k=0...) = H(x) =
= 2*SUM(3^k x^k : k=0...) - SUM( x^k : k=0...) = SUM( (2*3^k - 1) x^k : k= 0...)
, which means
a_k = 2 * 3^k - 1 for all k.
We can check our answer: k=0 seems OK, and also try the recurrence
relation
a_k = 2 * 3^k - 1 versus 3*a_(k-1)+2 = 3* [ 2*3^(k-1)-1] + 2 = 2 * 3^k - 3 + 2 (Good).
Set g(x)=SUM(a_k * x^k : k=0...) and as usual:
g(x) = 1 + SUM( (3a_(k-1)+4^(k-1)) * x^k : k=1...)
breaking up as:
g(x) = 1 + 3x * SUM( a_k * x^k : k=0...) + x * SUM( 4^k * x^k : k=0...)
Then g(x) = 1 + 3x * g(x) + x /(1-4x) = 3x * g(x) + [(1-4x) + x]/(1-4x)
and g(x) * (1-3x) = [1-3x]/(1-4x).
Now it is suspicious, but, g(x) = [1-3x]/(1-3x)*(1-4x) = 1/(1-4x).
So it seems g(x) is just SUM( 4^k x^k : k=0...), and thus a_k = 4^k, Oh, it works.
This one will be tougher because it has degree two (but it is homogeneous so we can check our result with Section 5.2 technique).
Let G(x) be the generating function and observe that
G(x) = 6 + 30*x + SUM( (5a_(k-1)-6a_(k-2)) * x^k : k=2...).
Then G(x) = 6 + 30x + 5x * SUM( a_k x^k : k=0...) - 6x^2 *
SUM( a_k x^k : k=0...)
(Added 12/12/96: Careful with the first terms (I wasn't))
the term SUM( 5 a_(k-1) x^k : k=2...) is missing the a_0 term, so we must add and subtract to the RHS the value 5a_0 x^1 (i.e. k=1). Since a_0=6 this luckily is just that 30x term that's hanging around doing nothing. So it just disappears.
Hence G(x) = 6 + 5x G(x) - 6x^2 G(x), i.e. G(x) (1-5x+6x^2) = 6 .
Which means G(x) = 6 /(1-3x)(1-2x) since it factored.
Part 2 is just as before: Set this equal to A/1-3x + B/1-2x and solve for A,B. We get:
6 = A+B
and0 = -2A - 3B, A= 18, B=-12, thus
a_k = 18 * 3^k + (-12) * 2^k.
We'd better check our answer: a_0 = 18 * 3^0 - 12 * 2^0 = 18-12 =
6
a_1 = 18 * 3 - 12 * 2 = 54 - 24 = 30 (so far so good)
for n> 1, a_n = 18 * 3^n - 12 * 2^n
and we need to see if this equals 5a_(n-1)-6a_(n-2) =
5 [ 18 * 3^(n-1) - 12 * 2^(n-1) ] - 6 [ 18 * 3^(n-2) - 12 * 2^(n-2) ]
Collect the 3's and the 2's together
= [5*18*3*3^(n-2) - 6*18*3^(n-2)] - [5*12*2*2^(n-2) - 6*12*2^(n-2)]
= 18*3^(n-2)*[5*3-6] - 12*2^(n-2)*[5*2 - 6] = 18*3^(n-2)*[9] - 12*2^(n-2)*[4]
= 18 * 3^(n-2) * 3^2 - 12 * 2^(n-2) * 2^2 = 18 * 3^n - 12 * 2^n
Yes, it works.