Using mathematical induction, prove...

MathematicsProperties of Binomial CoefficientsJEE Advanced 1989Moderate

Using mathematical induction, prove that $^{m} C_{0}^{n} C_{k} +^{m} C_{1}^{n} C_{k - 1} + .... +^{m} C_{k}^{n} C_{0} =^{(m + n)} C_{k}$ , where $m, n, k$ are positive integers, and $^{p} C_{q} = 0$ for $p < q$ .

Visualized Solution (English)

Understanding the Identity

The identity to prove is: $\sum_{r = 0}^{k}^{m} C_{r}^{n} C_{k - r} =^{m + n} C_{k}$
This is known as Vandermonde's Identity.
It represents picking $k$ items from two groups of size $m$ and $n$ .

Defining the Statement .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } P (m)

Let $P (m)$ be the statement: $\sum_{r = 0}^{k}^{m} C_{r}^{n} C_{k - r} =^{m + n} C_{k}$
We will use induction on the variable $m$ .

Base Case: .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } m = 1

For $m = 1$ , the LHS is: $\sum_{r = 0}^{k}^{1} C_{r}^{n} C_{k - r}$
Since $^{1} C_{r} = 0$ for $r > 1$ , the sum becomes: $^{1} C_{0}^{n} C_{k} +^{1} C_{1}^{n} C_{k - 1}$
Substituting values: $1 \cdot^{n} C_{k} + 1 \cdot^{n} C_{k - 1} =^{n} C_{k} +^{n} C_{k - 1}$

Verifying the Base Case

Using Pascal's Identity: $^{n} C_{k} +^{n} C_{k - 1} =^{n + 1} C_{k}$
The RHS for $m = 1$ is $^{1 + n} C_{k} =^{n + 1} C_{k}$
Since LHS = RHS, $P (1)$ is true.

Inductive Hypothesis

Assume $P (m)$ is true for some positive integer $m$ :
$\sum_{r = 0}^{k}^{m} C_{r}^{n} C_{k - r} =^{m + n} C_{k}$ (Inductive Hypothesis)

The Step for .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } m + 1

We need to show $P (m + 1)$ is true: $\sum_{r = 0}^{k}^{m + 1} C_{r}^{n} C_{k - r} =^{m + n + 1} C_{k}$
Using Pascal's Identity: $^{m + 1} C_{r} =^{m} C_{r} +^{m} C_{r - 1}$
The sum becomes: $\sum_{r = 0}^{k} (^{m} C_{r} +^{m} C_{r - 1})^{n} C_{k - r}$

Splitting the Summation

Distribute the sum:
$\sum_{r = 0}^{k}^{m} C_{r}^{n} C_{k - r} + \sum_{r = 0}^{k}^{m} C_{r - 1}^{n} C_{k - r}$

Applying the Hypothesis

From the hypothesis, the first sum is: $^{m + n} C_{k}$
For the second sum, let $j = r - 1$ . As $r$ goes from $0$ to $k$ , $j$ goes from $- 1$ to $k - 1$ .
Since $^{m} C_{- 1} = 0$ , the second sum is $\sum_{j = 0}^{k - 1}^{m} C_{j}^{n} C_{(k - 1) - j} =^{m + n} C_{k - 1}$

Final Combination

Combining the results: $^{m + n} C_{k} +^{m + n} C_{k - 1}$
Using Pascal's Identity again: $^{N} C_{R} +^{N} C_{R - 1} =^{N + 1} C_{R}$
Here $N = m + n$ and $R = k$ , so we get: $^{m + n + 1} C_{k}$
This matches the RHS of $P (m + 1)$ .

Conclusion & Takeaway

By the Principle of Mathematical Induction, the identity is true for all $m, n, k \in Z^{+}$ .
Key Takeaway: This identity allows us to split a selection process into cases based on two groups.
Next Challenge: Try proving this by comparing the coefficient of $x^{k}$ in $(1 + x)^{m} (1 + x)^{n}$ and $(1 + x)^{m + n}$ .

00:00 / 00:00

Conceptually Similar Problems

MathematicsProperties of Binomial CoefficientsJEE Advanced 1991Moderate

View in:English Hindi

Using induction or otherwise, prove that for any non-negative integers $m, n, r$ and $k$ , $\sum_{m = 0}^{k} (n - m) \frac{( r + m )!}{m !} = \frac{( r + k + 1 )!}{k !} [\frac{n}{r + 1} - \frac{k}{r + 2}]$

MathematicsProperties of Binomial CoefficientsJEE Advanced 2000Moderate

View in:English Hindi

For any positive integer $m, n$ (with $n \geq m$ ), let $(m n) =^{n} C_{m}$ . Prove that $(m n) + (m n - 1) + (m n - 2) + .... + (m m) = (m + 1 n + 1)$ . Hence or otherwise, prove that $(m n) + 2 (m n - 1) + 3 (m n - 2) + .... + (n - m + 1) (m m) = (m + 2 n + 2)$ .

MathematicsProperties of Binomial CoefficientsJEE Advanced 1989Moderate

View in:English Hindi

Prove that $C_{0} - 2^{2} C_{1} + 3^{2} C_{2} - .... + (- 1)^{n} (n + 1)^{2} C_{n} = 0, n > 2$ , where $C_{r} =^{n} C_{r}$ .

MathematicsProperties of Binomial CoefficientsJEE Advanced 2003Moderate

View in:English Hindi

Prove that $2^{k} (0 n) (k n) - 2^{k - 1} (1 n) (k - 1 n - 1) + 2^{k - 2} (2 n) (k - 2 n - 2) - .... + (- 1)^{k} (k n) (0 n - k) = (k n)$

MathematicsProperties of Binomial CoefficientsJEE Advanced 1999Moderate

View in:English Hindi

Let $n$ be any positive integer. Prove that $\sum_{k = 0}^{m} \frac{( k 2 n - k )}{( n 2 n - k )} (2 n - 4 k + 1) 2^{n - 2 k} = \frac{( m n )}{( n - m 2 n - 2 m )} 2^{n - 2 m}$ for each non-negative integer $m \leq n$ .

MathematicsProperties of Binomial CoefficientsJEE Advanced 1984Moderate

View in:English Hindi

Given $s_{n} = 1 + q + q^{2} + .... + q^{n}$ ; $S_{n} = 1 + \frac{q + 1}{2} + (\frac{q + 1}{2})^{2} + .... + (\frac{q + 1}{2})^{n}, q \neq = 1$ Prove that $^{n + 1} C_{1} +^{n + 1} C_{2} s_{1} +^{n + 1} C_{3} s_{2} + .... +^{n + 1} C_{n + 1} s_{n} = 2^{n} S_{n}$

MathematicsProperties of Binomial CoefficientsJEE Advanced 1998Moderate

View in:English Hindi

Let $p$ be a prime and $m$ a positive integer. By mathematical induction on $m$ , or otherwise, prove that whenever $r$ is an integer such that $p$ does not divide $r$ , $p$ divides $^{m p} C_{r}$ .

MathematicsProperties of Binomial CoefficientsJEE Advanced 1983Easy

View in:English Hindi

If $(1 + x)^{n} = C_{0} + C_{1} x + C_{2} x^{2} + .... + C_{n} x^{n}$ then show that the sum of the products of the $C_{i}$ 's taken two at a time, represented by $\sum_{0 \leq i < j \leq n} C_{i} C_{j}$ is equal to $2^{2 n - 1} - \frac{( 2 n )!}{2 ( n ! ) ^{2}}$

MathematicsLinear InequalitiesJEE Advanced 1987Moderate

View in:English Hindi

Prove by mathematical induction that $\frac{( 2 n )!}{2 ^{2 n} ( n ! ) ^{2}} \leq \frac{1}{( 3 n + 1 ) ^{1/2}}$ for all positive integers $n$ .

MathematicsProperties of Binomial CoefficientsJEE Advanced 1979Moderate

View in:English Hindi

Given that $C_{1} + 2 C_{2} x + 3 C_{3} x^{2} + .... + 2 n C_{2 n} x^{2 n - 1} = 2 n (1 + x)^{2 n - 1}$ where $C_{r} = \frac{( 2 n )!}{r ! ( 2 n - r )!}, r = 0, 1, 2, ...., 2 n$ . Prove that $C_{1}^{2} - 2 C_{2}^{2} + 3 C_{3}^{2} - .... - 2 n C_{2 n}^{2} = (- 1)^{n} n^{n} C_{n}$ .