Recurrence Relations and Generating Functions: Problem and Solution I

Combinatorics Problems and Solutions - Section 4

This is a part of Mr. Stolyarov's compilation of Free Combinatorics Problems and Solutions.

The Recurrence Relation to be Solved:

h_n = 8h_n-1 - 16h_n-2 (n ≥ 2); h₀ = -1, h₁ = 0.

We want to use generating functions to find an explicit formula for the nth term in this recurrence relation. 

Source of problem: Brualdi, Richard A. Introductory Combinatorics. First Edition. 1977.

Solution by Mr. Stolyarov:

Let f(x) = h₀ + h₁x + h₂x² + ... + h_nxⁿ + ... be the generating function for h₀, h₁, h₂,..., h_n

Adding the three equations

f(x) = h₀ + h₁x + h₂x² + h₃x³ + ... + h_nxⁿ + ...

-8xf(x) = -8h₀x -8h₁x² -8h₂x³ + ... -8h_n-1xⁿ -8h_nxⁿ⁺¹ + ...

16x²f(x) = 16h₀x²+16h₁x³+...+ 16h_n-2xⁿ + ...

we get (1 -8x + 16x²)f(x) = h₀ + (h₁ -8h₀)x + (h₂ -8h₁ + 16h₀)x² + ... + (h_n -8h_n-1 + 16h_n-2)xⁿ + ....

Since h_n -8h_n-1 + 16h_n-2 = 0 for n ≥ 2, and since h₀ = -1 and h₁ = 0, this reduces to

(1 -8x + 16x²)f(x) = -1 + (0 - 8(-1))x = 8x - 1

Thus, f(x) = (8x -1)/(1 -8x + 16x²)

We note that (1 -8x + 16x²) = (1 - 4x)²

Thus, (8x -1)/(1 -8x + 16x²) = A/(1 - 4x) + B/(1 - 4x)²

(8x -1)/(1 -8x + 16x²) = A(1 - 4x)/(1 - 4x) ² + B/(1 - 4x)²

So -4xA + B + A = 8x - 1

We note that -4A, the coefficient of the x term, must equal 8. Thus, A = 8/-4 = A = -2

So B - 2 = -1 and thus B = -1 + 2 = B = 1.

Thus, f(x) = (8x -1)/(1 -8x + 16x²) = -2/(1 - 4x) + 1/(1 - 4x)².

Using the formula

1/(1 - rx)ⁿ = _k=0^∞Σ[C(n+k-1,k)r^kx^k], we find that

-2/(1 - 4x) = -2_k=0^∞Σ[4^kx^k] and

1/(1 - 4x)² = _k=0^∞Σ[(k +1)4^kx^k]

Thus, f(x) = -2_k=0^∞Σ[4^kx^k] + _k=0^∞Σ[(k +1)4^kx^k]

f(x) = _k=0^∞Σ[-2[4^kx^k] + (k +1)4^kx^k] = _k=0^∞Σ[(k -1)4^kx^k]

Since this is the generating function for h₀, h₁, h₂,..., h_n, we have

h_n = (n -1)4ⁿ

See more of Mr. Stolyarov's Free Combinatorics Problems and Solutions.