Combinatorics

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

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{.}\) Nowand

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

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

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{.}\) ◾

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