## Worked Problems 11-14 from Appendix 3

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.

• Problem 11 This one is easily solvable by all three methods: a_k=7*a_(k-1) and a_0=5.
For example, by iteration, a_k=7(7a_(k-2))=7^2*a_(k-2)=...=7^j*a_(k-j)
for each j<k hence a_k=7^k*a_0=5*7^k for all 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.

• Problem 12 a_k=3*a_(k-1)+2 and a_0=1.

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).

• Problem 13 a_k=3*a_(k-1)+4^(k-1) and a_0=1.

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.

• Problem 14 a_k=5a_(k-1)-6a_(k-2) and a_0=6 and a_1=30.

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

`   and   `
0 = -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.