Solutions for Chapter 9

Section Solutions for Chapter 9

Solutions to Exercise 9.1.3

9.1.3.2 To prove Proposition 9.1.2 requires strong induction, since the recursive relation calls on two previous terms. Thus, two base cases are required.

9.1.3.3 The formula from Proposition 9.1.2 gives

$\begin{align*} D_5\amp= 5!\left(\frac{(-1)^0}{0!}+\frac{(-1)^1}{1!}+\frac{(-1)^2}{2!}+\frac{(-1)^3}{3!}+\frac{(-1)^4}{4!}+\frac{(-1)^5}{5!}\right)\\ \amp= 120\left(1-1+\frac{1}{2}-\frac{1}{6}+\frac{1}{24}-\frac{1}{120}\right)\\ \amp= 60-20+5-1=44\text{.} \end{align*}$

9.1.3.4 The initial conditions are

$\displaystyle D_1=0$ and

$\displaystyle D_2=1\text{.}$ The recursive relation

$\displaystyle D_n=(n-1)(D_{n-1}+D_{n-2})$ for

$\displaystyle n \ge 3$ gives

$\displaystyle D_3=2(D_2+D_1)=2(1+0)=2\text{.}$ Now

$\begin{equation*} D_4=3(D_3+D_2)=3(2+1)=9\text{,} \end{equation*}$

and

$\begin{equation*} D_5=4(D_4+D_3)=4(9+2)=4(11)=44\text{.} \end{equation*}$

Solutions to Exercise 9.2.3

9.2.3.1 Proof. Base case:

$\displaystyle n=0\text{.}$ We have

$\displaystyle c_0=1$ (by definition) and

$\displaystyle 1>0\text{,}$ so

$\displaystyle c_0>0\text{.}$

Inductive step: We begin with the inductive hypothesis. We will require strong induction. Let $\displaystyle k \ge 0$ be arbitrary, and suppose that the inequality holds for every $\displaystyle j$ with $\displaystyle 0 \le j \le k\text{;}$ that is, assume that for every such $\displaystyle j\text{,}$ $\displaystyle c_j>0\text{.}$

Now we want to deduce that $\displaystyle c_{k+1}>0\text{.}$ Using the recursive relation, we have

$\begin{equation*} c_{k+1}=\sum_{i=0}^kc_ic_{(k+1)-i-1}=\sum_{i=0}^kc_ic_{k-i}\text{.} \end{equation*}$

Using the inductive hypothesis, we have $\displaystyle c_j>0$ for every $\displaystyle j$ such that $\displaystyle 0 \le j \le k\text{.}$ Putting these together gives that $\displaystyle c_{k+1}$ is a sum of $\displaystyle k+1$ terms where each term has the form $\displaystyle c_ic_{k-i}$ with $\displaystyle 0 \le i \le k\text{.}$ Since $\displaystyle 0 \le k-i \le k\text{,}$ we see that $\displaystyle c_i>0$ and $\displaystyle c_{k-i}>0$ so that $\displaystyle c_ic_{k-i}>0\text{.}$ Hence

$\begin{equation*} c_{k+1}=\sum_{i=0}^k c_ic_{k-i}>0\text{.} \end{equation*}$

This completes the proof of the inductive step.

By the Principle of Mathematical Induction,

$\displaystyle c_n > 0$ for every

$\displaystyle n \ge 0\text{.}$ ◾

Solutions to Exercise 9.3.6

9.3.6.1

$\begin{align*} B_4=\sum_{k=1}^4 \binom{3}{k-1}B_{4-k}\amp= \binom{3}{0}B_3+\binom{3}{1}B_2+\binom{3}{2}B_1+\binom{3}{3}B_0\\ \amp= 5+3(2)+3(1)+1(1)=15\text{.} \end{align*}$

9.3.6.3 If

$\displaystyle b_i=(i+1)!/2$ then the expanded exponential generating function for this sequence is

$\begin{equation*} \sum_{i=0}^\infty\frac{b_ix^i}{i!}=\sum_{i=0}^\infty\frac{(i+1)!x^i}{2i!}=\sum_{i=0}^\infty(i+1)x^i/2\text{.} \end{equation*}$

This is

$\begin{equation*} \frac{1}{2}\sum_{i=0}^\infty (i+1)x^{i}=\frac{1}{2}\left(\sum_{i=0}^\infty (i+1)x^i\right)=\frac{1}{2(1-x)^2}\text{.} \end{equation*}$