Let's solve **Question 2** step-by-step: --- ## Problem Show that: \[ \binom{n}{k} \cdot \binom{k}{m} = \binom{n}{m} \cdot \binom{n-m}{k-m} \] for integers \( n \geq k \geq m \geq \). --- ## Step 1: Write Binomial Coefficient in Factorial Form Recall: \[ \binom{n}{k} = \frac{n!}{k!(n-k)!} \] So, \[ \binom{n}{k} \cdot \binom{k}{m} = \frac{n!}{k!(n-k)!} \cdot \frac{k!}{m!(k-m)!} \] --- ## Step 2: Simplify the Left Side Notice \( k! \) cancels: \[ = \frac{n!}{m!(k-m)!(n-k)!} \] --- ## Step 3: Write and Expand the Right Side Now, the right side: \[ \binom{n}{m} \cdot \binom{n-m}{k-m} \] \[ \binom{n}{m} = \frac{n!}{m!(n-m)!} \] \[ \binom{n-m}{k-m} = \frac{(n-m)!}{(k-m)!((n-m)-(k-m))!} = \frac{(n-m)!}{(k-m)!(n-k)!} \] Multiply: \[ = \frac{n!}{m!(n-m)!} \cdot \frac{(n-m)!}{(k-m)!(n-k)!} \] Again, \( (n-m)! \) cancels: \[ = \frac{n!}{m!(k-m)!(n-k)!} \] --- ## Step 4: Conclude Both sides are equal: \[ \boxed{ \binom{n}{k} \cdot \binom{k}{m} = \binom{n}{m} \cdot \binom{n-m}{k-m} } \] --- ## Explanation This identity is sometimes called the **binomial coefficient multiplication rule**. Intuitively, it says that: - If you select \( k \) objects from \( n \), and then \( m \) from those \( k \), it's the same as selecting \( m \) from \( n \), and then \( k-m \) from the remaining \( n-m \). --- ### Final Answer \[ \boxed{ \binom{n}{k} \cdot \binom{k}{m} = \binom{n}{m} \cdot \binom{n-m}{k-m} } \]

# Solutions to Exercises 1-12 ## Exercise 1: Proofs and Conclusions ### (a) Prove that the sum of an odd number and an odd number is even. - **Assumptions**: Let \( a \) and \( b \) be odd numbers. - **Desired Conclusion**: \( a + b \) is even. - **Proof**: An odd number can be expressed as \( 2k + 1 \) for some integer \( k \). Therefore, \( a = 2m + 1 \) and \( b = 2n + 1 \). \[ a + b = (2m + 1) + (2n + 1) = 2(m + n + 1) \] Thus, \( a + b \) is even. ### (b) Prove that for any real number \( z \), if \( 3 < z < 5 \) then \( [12z] = 12 \). - **Assumptions**: \( z \) is real and \( 3 < z < 5 \). - **Desired Conclusion**: \( [12z] = 12 \). - **Proof**: Since \( 3 < z < 5 \), we have \( 36 < 12z < 60 \). Therefore, \( 12 \) is the only integer in this range. ### (c) Prove (by contraposition) that for all integers \( x \) and \( y \), if \( z + y \) is odd, then \( x \neq y \). - **Assumptions**: Assume \( x = y \). - **Desired Conclusion**: \( z + y \) is even. - **Proof**: If \( x = y \), then \( z + y \) can be expressed as \( z + x \), which is even if \( z \) is even. ### (d) Show that if two integers have opposite parity, then their sum is odd. - **Assumptions**: \( a \) is even and \( b \) is odd, or vice versa. - **Desired Conclusion**: \( a + b \) is odd. - **Proof**: An even integer can be written as \( 2m \) and an odd integer as \( 2n + 1 \). \[ a + b = 2m + (2n + 1) = 2(m + n) + 1 \] Thus, \( a + b \) is odd. ### (e) Prove that an integer \( z \) is odd if and only if \( z^2 \) is odd. - **Assumptions**: \( z \) is odd. - **Desired Conclusion**: \( z^2 \) is odd. - **Proof**: If \( z = 2k + 1 \), \[ z^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1 \] Thus, \( z^2 \) is odd. ### (f) Let \( A \) and \( B \) be sets. Show that \( A \cap (B - A) = \emptyset \). - **Assumptions**: Let \( x \in A \cap (B - A) \). - **Desired Conclusion**: \( x \) must be in both \( A \) and \( B - A \), which is a contradiction. - **Proof**: If \( x \in B - A \), then \( x \notin A \). Thus, \( A \cap (B - A) = \emptyset \). ## Exercise 2: Binomial Coefficient Identity ### Problem Statement Show that: \[ \binom{n}{k} \cdot \binom{k}{m} = \binom{n}{m} \cdot \binom{n-m}{k-m} \] ### Step-by-Step Solution 1. **Left Side**: \[ \binom{n}{k} \cdot \binom{k}{m} = \frac{n!}{k!(n-k)!} \cdot \frac{k!}{m!(k-m)!} = \frac{n!}{m!(k-m)!(n-k)!} \] 2. **Right Side**: \[ \binom{n}{m} \cdot \binom{n-m}{k-m} = \frac{n!}{m!(n-m)!} \cdot \frac{(n-m)!}{(k-m)!(n-k)!} = \frac{n!}{m!(k-m)!(n-k)!} \] 3. **Conclusion**: Both sides are equal: \[ \boxed{\binom{n}{k} \cdot \binom{k}{m} = \binom{n}{m} \cdot \binom{n-m}{k-m}} \] ## Exercise 3: Rewrite the Binomial Theorem The Binomial Theorem can be expressed as: \[ (x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k} \] ## Exercise 4: Coefficient of \( x^2y^3 \) in \( (x + y)^5 \) - Using the binomial theorem, \[ \binom{5}{2} = 10 \quad (\text{for } x^2y^3) \] - The coefficient is \( 10 \). ## Exercise 5: Show that \( \binom{n}{n} = 1 \) - There is exactly one way to choose all \( n \) objects from \( n \). ## Exercise 6: Prove \( \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \) - **Algebraic Proof**: Using factorials, \[ \frac{n!}{k!(n-k)!} = \frac{(n-1)!}{(k-1)!(n-k)!} + \frac{(n-1)!}{k!(n-k-1)!} \] ## Exercise 7: Show that \( 2 \binom{n}{2} = n(n-1) \) - **Proof**: \( 2 \cdot \frac{n(n-1)}{2} = n(n-1) \). ## Exercise 8: Prove the sum of coefficients in \( (2z + 3)^n \) equals \( 5^n \) - Substitute \( z=1 \) in \( (2z + 3)^n \): \[ (2 \cdot 1 + 3)^n = 5^n \] ## Exercise 9: Show that if \( A \subseteq B \) and \( B \subseteq C \), then \( A \subseteq C \) - **Proof**: If \( x \in A \), then \( x \in B \) and hence \( x \in C \). ## Exercise 10: Prove \( A \cap B = B \cap A \) - **Proof**: By definition of intersection, both sides contain the same elements. ## Exercise 11: Show \( A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \) - **Proof**: If \( x \in A \cap (B \cup C) \), \( x \) must be in both \( A \) and either \( B \) or \( C \). ## Exercise 12: Show \( (A - B) \cup (A \cap B) = A \) - **Proof**: Any element \( x \in A \) is either in \( A - B \) or \( A \cap B \). --- This concludes the step-by-step solutions for Exercises 1-12.