Skip to main content

Section Solutions for Chapter 8

Solutions to Exercise 8.1.2

8.1.2.1 First we rewrite the generating function as a sum of two parts:
\begin{equation*} \frac{1}{(1+2x)(2-x)}=\frac{A}{1+2x}+\frac{B}{2-x}=\frac{A(2-x)+B(1+2x)}{(1+2x)(2-x)}\text{.} \end{equation*}
Now the numerator gives \(\displaystyle 2A+B+(2B-A)x=1\) as polynomials. Hence we must have \(\displaystyle 2B-A=0\) and \(\displaystyle 2A+B=1\text{.}\) Combining these gives \(\displaystyle B=1/5\) and \(\displaystyle A=2/5\text{.}\) Thus the given generating function is equal to
\begin{equation*} \frac{2}{5}(1+2x)^{-1}+\frac{1}{5}(2-x)^{-1}=\frac{2}{5}(1+2x)^{-1}+\frac{1}{10}(1-\frac{1}{2}x)^{-1}\text{.} \end{equation*}

Using the Generalised Binomial Theorem, the coefficient of \(\displaystyle x^r\) in the first of these summands is \(\displaystyle \frac{2}{5}(-1)^r2^r\text{,}\) while the coefficient of \(\displaystyle x^r\) in the second summand is \(\displaystyle \frac{1}{10}\left(\frac{1}{2}\right)^r\text{.}\) Thus, the coefficient of \(\displaystyle x^r\) is \(\displaystyle \frac{2}{5}(-1)^r2^r+\frac{1}{10}\left(\frac{1}{2}\right)^r\text{.}\)

8.1.2.3 First we rewrite the generating function as a sum of three parts:
\begin{align*} \frac{1+2x}{(1-2x)(2+x)(1+x)}\amp= \frac{A}{1-2x}+\frac{B}{2+x}+\frac{C}{1+x}\\ \amp= \frac{A(2+x)(1+x)+B(1-2x)(1+x)+C(1-2x)(2+x)}{(1-2x)(2+x)(1+x)}\text{.} \end{align*}
Now the numerator gives
\begin{align*} \amp A(2+3x+x^2)+B(1-x-2x^2)+C(2-3x-2x^2)\amp\\ =\amp 2A+B+2C+(3A-B-3C)x+(A-2B-2C)x^2\amp =1+2x \end{align*}
as polynomials, so we have \(\displaystyle 2A+B+2C=1\text{,}\) \(\displaystyle 3A-B-3C=2\text{,}\) and \(\displaystyle A-2B-2C=0\text{.}\) Solving this gives \(\displaystyle C=-1/3\text{,}\) \(\displaystyle B=3/5\text{,}\) and \(\displaystyle A=8/15\text{.}\) Thus (taking a factor of \(\displaystyle 2\) out of the denominator of the second piece) the given generating function is equal to
\begin{equation*} \frac{8}{15}(1-2x)^{-1}+\frac{3}{10}(1+\frac{1}{2}x)^{-1}-\frac{1}{3}(1+x)^{-1}\text{.} \end{equation*}

Using the Generalised Binomial Theorem, the coefficient of \(\displaystyle x^r\) in the first of these summands is \(\displaystyle \frac{8}{15}2^r\text{;}\) the coefficient of \(\displaystyle x^r\) in the second summand is \(\displaystyle \frac{3}{10}(-1)^r\left(\frac{1}{2}\right)^r\text{;}\) and the coefficient of \(\displaystyle x^r\) in the third summand is \(\displaystyle -\frac{1}{3}(-1)^r\text{.}\) We conclude that the coefficient of \(\displaystyle x^r\) in this generating function is
\begin{equation*} \frac{8}{15}2^r+\frac{3}{10}(-1)^r\left(\frac{1}{2}\right)^r-\frac{1}{3}(-1)^r\text{.} \end{equation*}

Solutions to Exercise 8.2.3

8.2.3.2 To use the method of partial fractions, we first factor the denominator:
\begin{equation*} 2x^2+x-1 = (2x - 1)(x + 1)\text{.} \end{equation*}
Now, write
\begin{align*} f(x) \amp =\frac{2+x}{2x^2+x-1} =\frac{2+x}{(2x - 1)(x + 1)} = \frac{A}{2x - 1} + \frac{B}{x + 1}\\ \amp = \frac{A(x+1) + B(2x-1)}{(2x - 1)(x + 1)} = \frac{(A-B) + (A+2B)x}{2x^2+x-1} \text{.} \end{align*}
Equating the coefficients in the numerators yields the two equations
\begin{equation*} A - B = 2, A + 2B = 1\text{.} \end{equation*}
Subtracting the second equation from the first tells us that \(\displaystyle -3B = 1\text{,}\) so \(\displaystyle B = -1/3\text{.}\) Then the first equation tells us that \(\displaystyle A = 2 - ({1}/{3}) = 5/3\text{.}\) So we have
\begin{equation*} f(x) = \frac{5/3}{2x - 1} - \frac{1/3}{x + 1} = -\frac{5/3}{1- 2x} - \frac{1/3}{1 + x}\text{.} \end{equation*}
The coefficient of \(\displaystyle x^r\) in \(\displaystyle 1/(1-x)\) is \(\displaystyle 1\text{,}\) so

  • the coefficient of \(\displaystyle x^r\) in \(\displaystyle 1/(1-2x)\) is \(\displaystyle 2^r\) (by replacing \(\displaystyle x\) with \(\displaystyle 2x\)), and

  • the coefficient of \(\displaystyle x^r\) in \(\displaystyle 1/(1+x)\) is \(\displaystyle (-1)^r\) (by replacing \(\displaystyle x\) with \(\displaystyle -x\))

Therefore, the coefficient of \(\displaystyle x^r\) in the generating function \(\displaystyle f(x)\) is
\begin{equation*} - \frac{5}{3}(2^r) - \frac{1}{3} (-1)^r\text{.} \end{equation*}

Solutions to Exercise 8.3.3

8.3.3.1 Let \(\displaystyle C(x) = \sum_{n=0}^\infty c_n x^n\) be the generating function of \(\displaystyle \{c_n\}\text{.}\) Then
\begin{align*} C(x) \amp = c_0 + c_1 x + c_2 x^2 + c_3 x^3 + c_4 x^4 + \cdots\\ xC(x) \amp = \qquad c_0x + c_1 x^2 + c_2 x^3 + c_3 x^4 + \cdots\\ x^2C(x) \amp = \qquad\qquad\ \ c_0x^2 + c_1 x^3 + c_2 x^4 + \cdots \end{align*}
so
\begin{align*} (1 - x - 2x^2) C(x) \amp = C(x) - x C(x) - 2 x^2 C(x)\\ \amp = c_0 + (c_1 - c_0) x + \sum_{n = 2}^\infty (c_n - c_{n-1} - 2 c_{n-2}) x^n\\ \amp = c_0 + (c_1 - c_0) x \text{,} \end{align*}
since (by the recurrence relation) we have \(\displaystyle c_n - c_{n-1} - 2 c_{n-2} = 0\) for \(\displaystyle n \ge 2\text{.}\) Therefore
\begin{equation*} C(x) = \frac{c_0 + (c_1 - c_0) x}{1 - x - 2x^2}\text{.} \end{equation*}
Since \(\displaystyle c_0 = 2\) and \(\displaystyle c_1 = 0\text{,}\) this means
\begin{equation*} C(x) = \frac{2 + (0 - 2) x}{1 - x - 2x^2} = \frac{2 - 2x}{(1 + x)(1 - 2x)}\text{.} \end{equation*}

We now use partial fractions. Write

\begin{gather*} \frac{2 - 2x}{(1 + x)(1 - 2x)} = \frac{A}{1 + x} + \frac{B}{1-2x} = \frac{A(1 - 2x) + B(1 + x)}{(1 + x)(1-2x)} = \frac{(A+B) + (B-2A)x}{(1 + x)(1-2x)} \text{.} \end{gather*}

Equating the coefficients in the numerators yields the equations

\begin{equation*} 2 = A + B, \qquad -2 = B - 2A\text{.} \end{equation*}

Subtracting the second equation from the first tells us that

\begin{equation*} 2 - (-2) = (A + B) - (B - 2A) = 3A\text{,} \end{equation*}

so \(\displaystyle A = 4/3\text{.}\) Then the second equation tells us that

\begin{equation*} B = 2A -2 = 2(4/3) - 2 = 2/3\text{.} \end{equation*}

So

\begin{equation*} C(x) = \frac{2 - 2x}{(1 + x)(1 - 2x)} = \frac{A}{1 + x} + \frac{B}{1-2x} = \frac{4/3}{1 + x} + \frac{2/3}{1-2x} = \frac{4}{3}\left( \frac{1}{1 + x} \right) + \frac{2}{3} \left( \frac{1}{1-2x} \right)\text{.} \end{equation*}

From the generalized binomial theorem, we know:

  • The coefficient of \(\displaystyle x^n\) in \(\displaystyle \frac{1}{1+x} = (1 + x)^{-1}\) is

    \begin{equation*} \binom{-1}{n} = (-1)^n \binom{1 + n - 1}{n} = (-1)^n \binom{n}{n} = (-1)^n\text{.} \end{equation*}

  • The coefficient of \(\displaystyle x^n\) in \(\displaystyle \frac{1}{1 - 2x} = (1 - 2x)^{-1}\) is

    \begin{equation*} \binom{-1}{n} (-2)^n = (-1)^n \binom{1 + n - 1}{n} (-2)^n = (-1)^{2n} \binom{n}{n} 2^n = 2^n\text{.} \end{equation*}
Therefore \(\displaystyle c_n\text{,}\) the coefficient of \(\displaystyle x^n\) in \(\displaystyle C(x)\text{,}\) is \(\displaystyle \frac{4}{3} (-1)^n + \frac{2}{3} \cdot 2^n\text{.}\)

8.3.3.3 Let \(\displaystyle E(x) = \sum_{n=0}^\infty e_n x^n\) be the generating function of \(\displaystyle \{e_n\}\text{.}\) Then
\begin{align*} E(x) \amp = e_0 + e_1 x + e_2 x^2 + e_3 x^3 + e_4 x^4 + \cdots\\ xE(x) \amp = \qquad e_0x + e_1 x^2 + e_2 x^3 + e_3 x^4 + \cdots\\ \frac{1}{1-x} \amp = 1 \ \ + \ \ x + \ \ x^2 +\ \ \ x^3 + \ \ \ x^4 + \cdots \end{align*}
so
\begin{align*} (1 - 3x) E(x) + \frac{2}{1-x} \amp = E(x) - 3x E(x) + 2 \cdot \frac{1}{1-x}\\ \amp = (e_0 + 2) + \sum_{n = 1}^\infty (e_n - 3e_{n-1} + 2) x^n\\ \amp = (e_0 + 2) \text{,} \end{align*}
since (by the recurrence relation) we have \(\displaystyle e_n - 3e_{n-1} + 2 = 0\) for \(\displaystyle n \ge 1\text{.}\) Therefore
\begin{equation*} E(x) = \frac{\displaystyle (e_0 + 2) - \frac{2}{1-x} }{1 - 3x} = \frac{(e_0 + 2)(1-x) - 2 }{(1 - 3x)(1-x)}\text{.} \end{equation*}
Since \(\displaystyle e_0 = 2\text{,}\) this means
\begin{equation*} E(x) = \frac{(2 + 2)(1-x) - 2 }{(1 - 3x)(1-x)} = \frac{2 - 4x}{(1 - 3x)(1-x)}\text{.} \end{equation*}

We now use partial fractions. Write

\begin{gather*} \frac{2 - 4x}{(1 - 3x)(1-x)} = \frac{A}{1 - 3x} + \frac{B}{1-x} = \frac{A(1 - x) + B(1 - 3x)}{(1 - 3x)(1-x)} = \frac{(A+B) - (A + 3B)x}{(1 - 3x)(1-x)} \text{.} \end{gather*}

Equating the coefficients in the numerators yields the equations

\begin{equation*} 2 = A + B, \qquad -4 = -(A + 3B)\text{.} \end{equation*}

Adding the two equations tells us that \(\displaystyle 2 - 4 = (A + B) - (A + 3B)= -2B\text{,}\) so \(\displaystyle B = 1\text{.}\) Then the first equation tells us that \(\displaystyle A = 2 - B = 2 - 1 = 1\text{.}\) So

\begin{equation*} E(x) = \frac{2 - 4x}{(1 - 3x)(1-x)} = \frac{A}{1 - 3x} + \frac{B}{1-x} = \frac{1}{1 - 3x} + \frac{1}{1-x}\text{.} \end{equation*}

From the generalized binomial theorem, we know that the coefficient of \(\displaystyle x^n\) in \(\displaystyle \frac{1}{1- 3x}\) is \(\displaystyle 3^n\text{,}\) and the coefficient of \(\displaystyle x^n\) in \(\displaystyle \frac{1}{1- x}\) is \(\displaystyle 1\text{.}\) Therefore \(\displaystyle e_n\text{,}\) the coefficient of \(\displaystyle x^n\) in \(\displaystyle E(x)\text{,}\) is \(\displaystyle 3^n + 1\text{.}\)