Suppose that A is a set of 2n
objects. Let Pn
denote the number of different ways that the objects in A may be “paired up” (the number of different partitions of A into 2-subsets).
// Assume n is a positive integer.
If n = 2, then A has four elements, A = {x1, x2, x3, x4}.
The three possible pairings are 1: x1
with x2
and x3
with x4;
2: x1
with x3
and x2
with x4;
3: x1
with x4
and x2
with x3:
// So P2
= 3
(a) Show that if n = 3 and A = {x1, x2, x3, x4, x5, x6}, there are 15 possible pairings by listing them all: 1. x1
with x2
and x3
with x4
and x5
with x6....
// So P3
= 15.
(b) Show that Pn
must satisfy the RE
(c) Use this recurrence equation and Mathematical Induction to prove
