Discrete Mathematics Practice Exam — Free

Count directly by the number of professors on the committee, which can be 2, 3, 4 or 5; the cases are disjoint, so the sum rule applies. Within each case the professors and the students are chosen independently, so the product rule applies:

$$\binom{6}{2}\binom{8}{3} + \binom{6}{3}\binom{8}{2} + \binom{6}{4}\binom{8}{1} + \binom{6}{5}\binom{8}{0} = 15\cdot 56 + 20\cdot 28 + 15\cdot 8 + 6\cdot 1 = 840 + 560 + 120 + 6 = 1526.$$

A second route is complementary counting: all committees minus those with fewer than 2 professors (0 or 1):

$$\binom{14}{5} - \binom{8}{5} - \binom{6}{1}\binom{8}{4} = 2002 - 56 - 420 = 1526.$$

Both methods agree.

The tempting wrong answer is 1582, which is 2002 − 420: it subtracts the committees with exactly 1 professor but forgets the 56 all-student committees, which also violate the "at least 2" condition. The answer 1946 (2002 − 56) makes the opposite error, excluding only the all-student committees as if the condition were "at least 1 professor". The answer 840 counts only committees with exactly 2 professors and ignores the cases with 3, 4 or 5.

1526 committees (option B).

This is a linear homogeneous recurrence with constant coefficients, so look for solutions of the form $a_n = r^n$. Substituting gives $r^n = 5r^{n-1} - 6r^{n-2}$; dividing by $r^{n-2}$ yields the characteristic equation

$$r^2 - 5r + 6 = 0 \quad\Longrightarrow\quad (r - 2)(r - 3) = 0 \quad\Longrightarrow\quad r = 2 \text{ or } r = 3.$$

The roots are distinct, so the general solution is a combination of the two:

$$a_n = \alpha\cdot 2^n + \beta\cdot 3^n.$$

The initial conditions determine $\alpha$ and $\beta$:

$$n = 0:\ \alpha + \beta = 1, \qquad n = 1:\ 2\alpha + 3\beta = 4.$$

Subtracting twice the first equation from the second gives $\beta = 2$, and then $\alpha = -1$. Hence

$$a_n = 2\cdot 3^n - 2^n.$$

Comparing with the recurrence: the formula gives $a_2 = 18 - 4 = 14$ and $a_3 = 54 - 8 = 46$, while the recurrence gives $a_2 = 5(4) - 6(1) = 14$ and $a_3 = 5(14) - 6(4) = 46$. They match.

$a_n = 2\cdot 3^n - 2^n$ for all $n \ge 0$.

Let $P(n)$ be the statement $\displaystyle\sum_{i=1}^{n} (2i-1)^2 = \frac{n(2n-1)(2n+1)}{3}$.

Base case ($n = 1$). The left side is $1^2 = 1$. The right side is $\dfrac{1\cdot 1\cdot 3}{3} = 1$. So $P(1)$ is true.

Inductive step. Assume $P(k)$ holds for some integer $k \ge 1$ (the inductive hypothesis):

$$1^2 + 3^2 + \cdots + (2k-1)^2 = \frac{k(2k-1)(2k+1)}{3}.$$

We must show $P(k+1)$, whose right side is $\dfrac{(k+1)(2k+1)(2k+3)}{3}$ (replace $k$ by $k+1$: $2(k+1) - 1 = 2k+1$ and $2(k+1) + 1 = 2k+3$). The next odd number after $2k-1$ is $2k+1$, so the sum for $k+1$ is the sum for $k$ plus $(2k+1)^2$. Using the hypothesis,

$$\sum_{i=1}^{k+1} (2i-1)^2 = \frac{k(2k-1)(2k+1)}{3} + (2k+1)^2.$$

Factor out the common factor $(2k+1)$ and combine over 3:

$$= (2k+1)\left[\frac{k(2k-1)}{3} + (2k+1)\right] = (2k+1)\cdot\frac{2k^2 - k + 6k + 3}{3} = \frac{(2k+1)(2k^2 + 5k + 3)}{3}.$$

Since $2k^2 + 5k + 3 = (k+1)(2k+3)$ (expand: $2k^2 + 3k + 2k + 3$), this equals

$$\frac{(k+1)(2k+1)(2k+3)}{3},$$

which is exactly the right side of $P(k+1)$. Thus $P(k) \Rightarrow P(k+1)$.

Conclusion. By the principle of mathematical induction, $P(n)$ is true for every integer $n \ge 1$. (For instance, $n = 2$ gives $1+9 = 10$ on the left and $\dfrac{2\cdot 3\cdot 5}{3} = 10$ on the right.)

The identity $\displaystyle\sum_{i=1}^{n}(2i-1)^2 = \frac{n(2n-1)(2n+1)}{3}$ holds for all integers $n \ge 1$.