Double summation

**fardeen_gen** · February 9th 2009, 06:37 AM

Find the value of:
∑∑ (i. nCj + j. nCi)
1≤ i < j ≤ n
NOTE: i. nCj is i multiplied by n choose j

**Opalg** · February 9th 2009, 10:20 AM

Originally Posted by fardeen_gen

Find the value of:
∑∑ (i. nCj + j. nCi)
1≤ i < j ≤ n
NOTE: i. nCj is i multiplied by n choose j

In that sum, each integer from 1 to n is multiplied by each binomial coefficient $\textstyle n\choose k$ (k going from 1 to n), except for the "diagonal" products $k{n\choose k}$ . So the sum is equal to $\sum_{i=1}^ni\sum_{j=1}^n{n\choose j} - \sum_{k=1}^nk{n\choose k}$ . But $\sum_{i=1}^ni = \tfrac12n(n+1)$ , $\sum_{j=1}^n{n\choose j} = 2^n-1$ and $\sum_{k=1}^nk{n\choose k} = 2^{n-1}n$ . Therefore $\mathop{\sum\sum}_{1\leqslant i<j\leqslant n}\left(i{n\choose j} + j{n\choose i}\right) = \tfrac12n(n+1)(2^n-1) - 2^{n-1}n = 2^{n-1}n^2 - \tfrac12n(n+1)$ .

Thread: Double summation - Binomial Theorem?

LinkBack

Thread Tools

Display

Double summation - Binomial Theorem?

Similar Math Help Forum Discussions

Double summation

double summation

double summation

Expectation with Double Summation

Search Tags