Counting - Hoang Anh Duc - MIM - HUS - VNU

Work 20.

$$\begin{gather*} \text{Prove that } \forall n \geq 0 \text{, the sum of the elements} \quad \\[5pt] \text{in the } n \text{-th row in a Pascal triangle is} \quad \\[10pt] \sum_{i=0}^n C_n^i = 2^n \quad \end{gather*}$$

Block

• Solution:

$$\begin{align} & \text{We prove the proposition with induction:} \quad \\[5pt] & \text{Basis step: } n = 0 \implies \sum_{i=0}^n C_n^i = C_0^0 = \frac{0!}{0!0!} = 2^0 \quad \\[5pt] & \text{Induction step: Let } k \text{ be an integer such that } k > 0 \text{ and} \quad \\[5pt] & \text{for all } L \mid 0 \leq L \leq k \text{ where } L \text{ indicates a row in the Pascal} \quad \\[5pt] & \text{triangle } I \text{ such that when } L \in I \text{, the formula stands true:} \quad \\[5pt] & \sum_{i=0}^k C_k^i = C_k^0 + C_k^1 + \ldots + C_k^k = 2^k \quad (IH) \quad \\[5pt] & \text{We need to show that: } \sum_{i=0}^{k+1} C_{k+1}^i = 2^{k+1} \quad \\[5pt] & \text{By Pascal's Identity: } \sum_{i=0}^{k+1} C_{k+1}^i = \sum_{i=0}^{k+1} \left( C_k^i + C_k^{i-1} \right) \quad \\[5pt] & = \left( \sum_{i=0}^k C_k^i \right) + \left( \sum_{i=1}^{k+1} C_k^{i-1} \right) = \left( \sum_{i=0}^k C_k^i \right) + \left( \sum_{i=0}^k C_k^i \right) \quad \\[5pt] & = 2 \times \sum_{i=0}^k C_k^i \overset{IH}{\mathrel{=}} 2 \times 2^k = 2^{k+1} \quad \\[5pt] & \text{Therefore, by mathematical induction:} \quad \\[5pt] & \sum_{i=0}^n C_n^i = 2^n, \forall n \geq 0 \mid n \in \mathbb{N} \quad \end{align}$$

Block

Work 23.

$$\begin{align} & \text{Find the coefficient of} \quad \\[5pt] & (a) \quad x^7 \text{ in the expansion of } (1 + x)^{11} \quad \\[5pt] & (b) \quad x^9 \text{ in the expansion of } (2 - x)^{19} \quad \\[8pt] & (c) \quad x^k \text{ in the expansion of } \left(1 + \frac{1}{x} \right)^{100} \quad \end{align}$$

Block

• (a) $\quad x^7 \text{ in the expansion of } (1 + x)^{11}$

$$\begin{align} & \text{By the binomial theorem, the general term is:} \quad \\[5pt] & C_{11}^r \cdot 1^{11-r} \cdot x^r = C_{11}^r \cdot x^r \quad \\[5pt] & \text{To find the coefficient of } x^7 \text{, we set } r = 7: \quad \\[5pt] & C_{11}^7 = 330 = \text{Coefficient of } x^7 \quad \end{align}$$

Block

• (b) $\quad x^9 \text{ in the expansion of } (2 - x)^{19}$

$$\begin{align} & \text{By the binomial theorem, the general term is:} \quad \\[5pt] & C_{19}^r \cdot 2^{19-r} \cdot (-x)^r = C_{11}^r \cdot 2^{19-r} \cdot (-1)^r \cdot x^r \quad \\[5pt] & \text{To find the coefficient of } x^9 \text{, we set } r = 9: \quad \\[5pt] & C_{19}^9 \cdot 2^{19-9} \cdot (-1)^9 = -94 \space 595 \space 072 = \text{Coefficient of } x^9 \quad \end{align}$$

Block

• (c) $\quad x^k \text{ in the expansion of } \left(1 + \frac{1}{x} \right)^{100}$

$$\begin{align} & \text{By the binomial theorem, the general term is:} \quad \\[5pt] & C_{100}^r \cdot 1^{100-r} \cdot \left(\frac{1}{x}\right)^r = C_{100}^r \cdot x^{-r} \quad \\[5pt] & \text{To find the coefficient of } x^k \text{, we set } -r = k \text{ or } r = -k: \quad \\[5pt] & C_{100}^{-k} \cdot x^k \text{, we see that for the proposition to hold, then } k \leq 0 \quad \\[5pt] & \text{Therefore, } C_{100}^{-k} = \text{Coefficient of } x^k, k \leq 0 \quad \end{align}$$

Block

Work 27.

$$\begin{gather*} \text{Directly count all the integer solutions to the equation} \quad \\[5pt] x_1 + x_2 + x_3 = 11 \text{ that satisfy } 0 \leq x_1 \leq 2, x_2 \geq 0 \quad \\[5pt] \text{and } x_3 \geq 0 \text{ by considering all} \quad \\[5pt] \text{cases of } x_1 = 0, x_1 = 1, x_1 = 2 \quad \end{gather*}$$

Block

• Solution:

Case 1: x_1 = 0 => 0 + x_2 + x_3 = 11
There are C_{1}^{11 + 1 - 1} = 11 solutions

Case 2: x_1 = 1 => 1 + x_2 + x_3 = 11
There are C_{1}^{10 + 1 - 1} = 10 solutions

Case 3: x_1 = 2 => 2 + x_2 + x_3 = 11
There are C_{1}^{9 + 1 - 1} = 9 solutions

=> There are 9 + 10 + 11 = 30 solutions

Work 29.

$$\begin{align} & \text{Find the coefficient of} \quad \\[5pt] & (a) \quad x^3 \text{ in the expansion of } (1 - x)^{-2} \quad \\[5pt] & (b) \quad x^n \text{ in the expansion of } (1 + x)^{-4} \quad \\[8pt] & (c) \quad x^n \text{ in the expansion of } \frac{1 + x}{(1 - 2x)^5} \quad \end{align}$$

Block

• Prerequisites: Generalized Binomial Theorem:

$$\begin{gather*} \text{For any real number } m \text{ and } \lvert x \rvert < 1 \quad \\[5pt] (1 + x)^m = \sum_{k=0}^\infty \binom{m}{k} \cdot x^k \quad \\[5pt] = \sum_{k=0}^\infty \frac{m(m-1)(m-2) \ldots (m-k+1)}{k!} x^k \quad \end{gather*}$$

Block

• (a) $\quad x^3 \text{ in the expansion of } (1 - x)^{-2}$

$$\begin{align} & (1-x)^{-2} = \sum_{k=0}^\infty \binom{-2}{k} \cdot (-x)^k \quad \\[5pt] & \text{The general term is:} \quad \\[5pt] & \binom{-2}{k} \cdot (-x)^k = \binom{-2}{k} \cdot (-1)^k \cdot x^k \quad \\[5pt] & \text{To find the coefficient of } x^3 \text{, we set } k = 3: \quad \\[5pt] & \binom{-2}{3} \cdot (-1)^3 = 4 = \text{Coefficient of } x^3 \quad \end{align}$$

Block

• (b) $\quad x^n \text{ in the expansion of } (1 + x)^{-4}$

$$\begin{align} & (1+x)^{-4} = \sum_{k=0}^\infty \binom{-4}{k} \cdot x^k \quad \\[5pt] & \text{The coefficient of } x^n \text{ corresponds to } k = n \quad \\[5pt] & \binom{-4}{n} = \frac{(-4)(-5)\ldots(-4-n+1)}{n!} \quad \\[5pt] & \qquad \quad = \frac{(-1)^n\cdot 4\cdot 5\ldots(3+n)}{n!} \quad \\[5pt] & \qquad \quad = (-1)^n \cdot \frac{(4+n-1)!}{n!3!} \quad \end{align}$$

Block

• (c) $\quad x^n \text{ in the expansion of } \frac{1 + x}{(1 - 2x)^5}$

• Step 1: Expansion of $(1-2x)^{-5}$

$$\begin{align} & (1-2x)^{-5} = \sum_{k=0}^\infty \binom{-5}{k} \cdot (-2x)^k \quad \\[5pt] & = \sum_{k=0}^\infty \binom{-5}{k} \cdot (-2)^k \cdot x^k \quad \\[5pt] & \text{The general term is:} \quad \\[5pt] & \binom{-5}{k} \cdot (-2)^k \cdot x^k \quad \end{align}$$

Block

• Step 2: Combine the expressions

$$\begin{align} & \text{We have to multiply the expansions} \quad \\[5pt] & \text{of } (1+x) \text{ and } (1-2x)^{-5} \quad \\[5pt] & \text{The general expression for the coefficient of } x^n: \quad \\[5pt] & \binom{-5}{n} \cdot (-2)^n + \binom{-5}{n-1} \cdot (-2)^{n-1} \end{align}$$

Block

Work 30.

$$\begin{gather*} \text{Use a generating function to count all the} \quad \\[5pt] \text{integer solutions to the equation} \quad \\[5pt] x_1 + x_2 + x_3 = 11 \text{ that satisfy } \quad \\[5pt] 0 \leq x_1 \leq 2, x_2 \geq 0, x_3 \geq 0 \quad \end{gather*}$$

Block

• Solution:

$$\begin{align} & \text{For } x_1 \text{ the generating function is} \quad \\[5pt] & \qquad \qquad 1 + x + x^2 \quad \\[5pt] & \text{For } x_2, x_3 \text{ the generating function is} \quad \\[5pt] & \qquad \qquad \frac{1}{1-x} \quad \\[5pt] & \text{Thus the complete generating function is} \quad \\[5pt] & G(x) = (1 + x + x^2) \frac{1}{(1 - x)^2} \quad \\[5pt] & \text{We need to find the coefficient of } x^{11} \quad \\[5pt] & \text{We have: } \frac{1}{(1 - x)^2} = \sum_{n=0}^\infty (n+1)x^n \quad \\[5pt] & G(x) = (1 + x + x^2) \times \left(\sum_{n=0}^\infty (n+1)x^n \right) \quad \\[5pt] & G(x) = \sum_{n=0}^\infty (n+1)x^n + x \cdot \sum_{n=0}^\infty (n+1)x^n + x^2 \cdot \sum_{n=0}^\infty (n+1)x^n \quad \\[5pt] & G(x) = \sum_{n=0}^\infty (n+1)x^n + \sum_{n=0}^\infty (n+1)x^{n+1} + \sum_{n=0}^\infty (n+1)x^{n+2} \quad \\[5pt] & \text{For the coefficient of } x^{11} \text{, we have:} \quad \\[5pt] & 12 + 11 + 10 = 33 = \text{coefficient of } x^{11} \quad \\[5pt] & \text{So there are 33 solutions to the equation } x_1 + x_2 + x_3 = 11 \quad \\[5pt] & \text{that satisfy } 0 \leq x_1 \leq 2, x_2 \geq 0, x_3 \geq 0 \quad \end{align}$$

Block

• References:
  • Mathstackexchange - Work 20 Complement