JEE Advanced 2003

LEVELJEE Main

Animated Solution for Mathematics - Binomial Theorem: 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)$

Q: Wait, why do we reject the direct factorial expansion? Can't we just expand everything and cancel?

You absolutely can! Expanding $\binom{n}{r} \binom{n-r}{k-r}$ into factorials will eventually lead you to the same result. However, in JEE Advanced, time is your most precious resource. Using the combinatorial identity $\binom{n}{r} \binom{n-r}{k-r} = \binom{n}{k} \binom{k}{r}$ is not just a shortcut; it is a powerful tool that reveals the underlying symmetry of the problem, reducing a messy algebraic nightmare into a simple, elegant step.

Q: Is there a physical intuition for why $(2-1)^k$ appears at the end?

Yes! The Binomial Theorem states that $(x+y)^k = \sum_{r=0}^k \binom{k}{r} x^{k-r} y^r$. When you factor out $\binom{n}{k}$, you are left with a sum that perfectly matches this expansion with $x=2$ and $y=-1$. The $(2-1)^k$ is simply the result of evaluating this expansion. It is the mathematical 'closing of the loop' that confirms your derivation is correct.

Progressive Hints

Hint 1

Hint 1: The Spark. Look at the structure of the series. It is an alternating sum of products of two binomial coefficients. The key is to examine the general term

T_{r} = (- 1)^{r} 2^{k - r} (r n) (k - r n - r)

. Notice that the index

r

appears in both binomial coefficients, which makes direct summation difficult. You need to decouple these terms.

Hint 2

Hint 2: The Arsenal. Use the combinatorial identity

(r n) (k - r n - r) = (k n) (r k)

. This identity represents the 'Committee Selection' logic: choosing

r

items from

n

and then

k - r

from the remaining

n - r

is equivalent to choosing

k

items from

n

first, and then selecting

r

of those

k

to be a special subgroup.

Hint 3

Hint 3: The Execution. Substitute the identity from Hint 2 into your summation. You will find that

(k n)

is independent of the summation index

r

and can be factored out. The remaining sum will then take the form of the Binomial Theorem expansion for

(x + y)^{k}

, where

x = 2

and

y = - 1

Visualized Solution

Analyzing the Alternating Series

We are given an alternating series with binomial coefficients and powers of two.
LHS: $2^{k} (0 n) (k n) - 2^{k - 1} (1 n) (k - 1 n - 1) + \dots + (- 1)^{k} (k n) (0 n - k)$
Our goal is to prove that this entire expression simplifies beautifully to just $(k n)$ .

Finding the General Term $T_{r}$

Let's observe the $(r + 1)$ -th term of the series.
The sign is $(- 1)^{r}$ , starting with positive for $r = 0$ .
The power of $2$ is $2^{k - r}$ .
The binomial coefficients are $(r n)$ and $(k - r n - r)$ .
Thus, the general term is: $T_{r} = (- 1)^{r} 2^{k - r} (r n) (k - r n - r)$

Writing LHS in Summation Notation

We can now write the entire LHS as a single summation.
$L H S = \sum_{r = 0}^{k} T_{r}$
$L H S = \sum_{r = 0}^{k} (- 1)^{r} 2^{k - r} (r n) (k - r n - r)$

The Double Binomial Obstacle

The term $(r n) (k - r n - r)$ has $r$ in both factors.
This coupling prevents us from factoring out terms independent of $r$ .
We need to transform this product into a form where one of the binomial coefficients is independent of $r$ .

The Subset Selection Identity

We use the identity: $(r n) (k - r n - r) = (k n) (r k)$
Combinatorial Meaning:
LHS: Choose $r$ elements from $n$ , then choose $k - r$ from the remaining $n - r$ .
RHS: Choose $k$ elements from $n$ first, then choose $r$ from those $k$ .

The Equivalent Selection Path

Alternatively, we can select the group of $k$ elements first.
Number of ways to choose $k$ from $n$ : $(k n)$
From these $k$ elements, choose $r$ to be colored red: $(r k)$
Both paths yield the exact same final configuration!

Algebraic Verification of the Identity

Let's verify this algebraically using factorials:
$(r n) (k - r n - r) = \frac{n !}{r ! ( n - r )!} \cdot \frac{( n - r )!}{( k - r )! ( n - k )!}$
Cancel $(n - r)!$ from numerator and denominator:
$= \frac{n !}{r ! ( k - r )! ( n - k )!}$
Multiply and divide by $k!$ :
$= \frac{n !}{k ! ( n - k )!} \cdot \frac{k !}{r ! ( k - r )!} = (k n) (r k)$

Substituting the Decoupled Identity

Substitute $(r n) (k - r n - r) = (k n) (r k)$ back into our summation:
$L H S = \sum_{r = 0}^{k} (- 1)^{r} 2^{k - r} [(k n) (r k)]$

Factoring out $(k n)$

Since $(k n)$ is independent of the summation index $r$ , we can pull it outside the summation:
$L H S = (k n) \sum_{r = 0}^{k} (r k) 2^{k - r} (- 1)^{r}$

Matching with the Binomial Theorem

Recall the standard Binomial Theorem expansion:
$(x + y)^{k} = \sum_{r = 0}^{k} (r k) x^{k - r} y^{r}$
Comparing this with our summation:
Let $x = 2$ and $y = - 1$ .
Thus, $\sum_{r = 0}^{k} (r k) 2^{k - r} (- 1)^{r} = (2 - 1)^{k}$

The Final Q.E.D.

Substitute the simplified sum back into the LHS expression:
$L H S = (k n) (2 - 1)^{k}$
Since $2 - 1 = 1$ , we have:
$L H S = (k n) (1)^{k} = (k n)$
This is exactly equal to the RHS. Hence Proved!

00:00 / 00:00

The Sigma Insight: Properties of Binomial Coefficients

Solution Diagram

Analyzing the Setup

The series provided is:

2^{k} (0 n) (k n) - 2^{k - 1} (1 n) (k - 1 n - 1) + \dots + (- 1)^{k} (k n) (0 n - k)

This expression appears intimidating, but in the context of JEE Advanced, such complexity is often a mask for hidden elegance. We must peel back this mask by identifying the general term of the series.

The Detective Work

By observing the pattern, we define the

(r + 1)

-th term as:

T_{r} = (- 1)^{r} 2^{k - r} (r n) (k - r n - r)

The alternating sign

(- 1)^{r}

is evident, the power of two

2^{k - r}

is decreasing, and the product of binomial coefficients

(r n) (k - r n - r)

is our primary focus. Because

r

is coupled within both binomial coefficients, we must decouple them to simplify the summation.

The Combinatorial Insight

We utilize the 'Committee Selection' identity. Suppose we have

n

students and need to form a committee of

k

students, while simultaneously assigning

r

of those

k

students to a special task.

Method A involves choosing

r

students from the

n

total, then choosing the remaining

k - r

students from the

n - r

remaining students, yielding

(r n) (k - r n - r)

. Method B involves choosing the entire committee of

k

students from the

n

total first, then choosing the

r

special students from that group of

k

, yielding

(k n) (r k)

Since both methods count the same selection process, they are equivalent:

(r n) (k - r n - r) = (k n) (r k)

The Algebraic Elegance

Now, we substitute this identity back into our summation:

L H S = r = 0 \sum k (- 1)^{r} 2^{k - r} (k n) (r k)

Because

(k n)

does not depend on

r

, we can pull it out of the summation entirely:

L H S = (k n) r = 0 \sum k (r k) 2^{k - r} (- 1)^{r}

The remaining sum is the exact expansion of

(2 - 1)^{k}

according to the Binomial Theorem. Since

2 - 1 = 1

, the entire sum collapses to

1^{k}

, which is simply

1

Final Result

We are left with:

L H S = (k n) \times 1 = (k n)

The intimidating series is simply a complex representation of $(k n)$ . Remember, in mathematics, the most complex problems often yield to the most elegant insights.

Common Traps & FAQs

Wait, why do we reject the direct factorial expansion? Can't we just expand everything and cancel?

You absolutely can! Expanding

(r n) (k - r n - r)

into factorials will eventually lead you to the same result. However, in JEE Advanced, time is your most precious resource. Using the combinatorial identity

(r n) (k - r n - r) = (k n) (r k)

is not just a shortcut; it is a powerful tool that reveals the underlying symmetry of the problem, reducing a messy algebraic nightmare into a simple, elegant step.

How do I know when to use the identity

(r n) (k - r n - r) = (k n) (r k)

This is a classic 'trap' pattern. Whenever you see a product of two binomial coefficients where the indices are 'linked' (like

r

appearing in both the upper and lower indices), you should immediately suspect that this identity will help you decouple the variables. It is the go-to move for simplifying sums involving products of binomial coefficients.

Is there a physical intuition for why

(2 - 1)^{k}

appears at the end?

Yes! The Binomial Theorem states that

(x + y)^{k} = \sum_{r = 0}^{k} (r k) x^{k - r} y^{r}

. When you factor out

(k n)

, you are left with a sum that perfectly matches this expansion with

x = 2

and

y = - 1

. The

(2 - 1)^{k}

is simply the result of evaluating this expansion. It is the mathematical 'closing of the loop' that confirms your derivation is correct.

Animated Solution for Mathematics - Binomial Theorem: 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)$

Visualized Solution

Analyzing the Alternating Series

Finding the General Term $T_{r}$

Writing LHS in Summation Notation

The Double Binomial Obstacle

The Subset Selection Identity

The Equivalent Selection Path

Algebraic Verification of the Identity

Substituting the Decoupled Identity

Factoring out $(k n)$

Matching with the Binomial Theorem

The Final Q.E.D.

The Sigma Insight: Properties of Binomial Coefficients

Analyzing the Setup

The Detective Work

The Combinatorial Insight

The Algebraic Elegance

Final Result

Similar Questions

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)$ .

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$ .

For $2 \leq r \leq n$ , $(r n) + 2 (r - 1 n) + (r - 2 n) =$

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$ .

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}$ .

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}]$

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}$ .

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}}$

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}$

The value of $(0 30) (10 30) - (1 30) (11 30) + (2 30) (12 30) - .... + (20 30) (30 30)$ is

Visualized Solution

Analyzing the Alternating Series

Finding the General Term .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } Tr​

Writing LHS in Summation Notation

The Double Binomial Obstacle

The Subset Selection Identity

The Equivalent Selection Path

Algebraic Verification of the Identity

Substituting the Decoupled Identity

Factoring out .math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } (kn​)

Matching with the Binomial Theorem

The Final Q.E.D.

The Sigma Insight: Properties of Binomial Coefficients

Analyzing the Setup

The Detective Work

The Combinatorial Insight

The Algebraic Elegance

Final Result

Similar Questions

.math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } Let n be any positive integer. Prove that ∑k=0m​(n2n−k​)(k2n−k​)​(2n−4k+1)2n−2k=(n−m2n−2m​)(mn​)​2n−2m for each non-negative integer m≤n.

.math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } For 2≤r≤n, (rn​)+2(r−1n​)+(r−2n​)=

.math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } Using mathematical induction, prove that mC0n​Ck​+mC1n​Ck−1​+....+mCkn​C0​=(m+n)Ck​, where m,n,k are positive integers, and pCq​=0 for p<q.

.math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } Prove that C0​−22C1​+32C2​−....+(−1)n(n+1)2Cn​=0,n>2, where Cr​=nCr​.

.math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } Using induction or otherwise, prove that for any non-negative integers m,n,r and k, ∑m=0k​(n−m)m!(r+m)!​=k!(r+k+1)!​[r+1n​−r+2k​]

.math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } Given sn​=1+q+q2+....+qn; Sn​=1+2q+1​+(2q+1​)2+....+(2q+1​)n,q=1 Prove that n+1C1​+n+1C2​s1​+n+1C3​s2​+....+n+1Cn+1​sn​=2nSn​

.math-text-wrapper .katex { font-size: 1.05em !important; } .math-text-wrapper .katex-display { margin: 1rem 0 !important; } The value of (030​)(1030​)−(130​)(1130​)+(230​)(1230​)−....+(2030​)(3030​) is

Finding the General Term $T_{r}$

Factoring out $(k n)$

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$ .

For $2 \leq r \leq n$ , $(r n) + 2 (r - 1 n) + (r - 2 n) =$

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$ .

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}$ .

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}]$

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}$

The value of $(0 30) (10 30) - (1 30) (11 30) + (2 30) (12 30) - .... + (20 30) (30 30)$ is