# How to prove by induction (expressions in brackets are binomial coefficients)` `: `sum_(k=m)^n(n / k)(k / m)=(n / m)2^(n-m)`

*print*Print*list*Cite

### 1 Answer

You need to expand the left side sum, such that:

`sum_(k=m)^n C_n^k*C_k^m = C_n^m*C_m^m + C_n^(m+1)*C_(m+1)^m + ...+C_n^n*C_n^m`

`C_m^m = C_n^n = 1`

Evaluating the binomial coefficients, yields:

`C_n^m = (n!)/(m!(n-m)!)`

`C_n^(m+1)*C_(m+1)^m = [(n!)/((m+1)!(n-(m+1))!)]* [((m+1)!)/((m)!(n-(m+1))!)]`

Reducing like factors, yields:

`C_n^(m+1)*C_(m+1)^m = [(n!)/(m!)((n-(m+1))!)]`

`C_n^(m+2)*C_(m+2)^m = [(n!)/(m!)((n-(m+2))!)]`

......................

Replacing the results in the sum, yields:

`sum_(k=m)^n C_n^k*C_k^m = (n!)/(m!(n-m)!) + [(n!)/(m!)((n-(m+1))!)] + [(n!)/(m!)((n-(m+2))!)] + ... + (n!)/(m!(n-m)!) `

Factoring out ` (n!)/(m!)` , yields:

`sum_(k=m)^n C_n^k*C_k^m= (n!)/(m!)(1/((n-m)!) + 1/((n-(m+1))!) + 1/((n-(m+2))!) + ... + 1/((n-m)!))`

You need to evaluate the right side, such that:

`C_n^m = (n!)/(m!(n-m)!)`

`2^(n-m) = (1 + 1)^(n-m)`

Using Newton formula, yields:

`(1 + 1)^(n-m) = C_(n-m)^0 + C_(n-m)^1 + C_(n-m)^2 + .. + C_(n-m)^(n-m)`

`(1 + 1)^(n-m) = ((n-m)!)/(0!(n-m)!) + ((n-m)!)/(1!(n-(m+1))!) + ((n-m)!)/(2!(n-(m+2))!) + .. + ((n-m)!)/(0!(n-m)!)`

Factoring out `(n-m)! ` yields:

`(1 + 1)^(n-m) = (n-m)!(1/(0!(n-m)!) + 1/(1!(n-(m+1))!) + 1/(2!(n-(m+2))!) + .. + 1/(0!(n-m)!))`

Hence, evaluating the right side, yields:

`C_n^m*2^(n-m) = (n!)/(m!(n-m)!)*(n-m)!(1/(0!(n-m)!) + 1/(1!(n-(m+1))!) + 1/(2!(n-(m+2))!) + .. + 1/(0!(n-m)!))`

Reducing by` (n-m)!` yields:

`C_n^m*2^(n-m) = (n!)/(m!)(1/(0!(n-m)!) + 1/(1!(n-(m+1))!) + 1/(2!(n-(m+2))!) + .. + 1/(0!(n-m)!))`

Replacing the obtained results in the given equality, yields:

`(n!)/(m!)(1/((n-m)!) + 1/((n-(m+1))!) + 1/((n-(m+2))!) + ... + 1/((n-m)!)) = (n!)/(m!)(1/(0!(n-m)!) + 1/(1!(n-(m+1))!) + 1/(2!(n-(m+2))!) + .. + 1/(0!(n-m)!))`

Reducing by` (n!)/(m!) ` yields:

`(1/((n-m)!) + 1/((n-(m+1))!) + 1/((n-(m+2))!) + ... + 1/((n-m)!)) = (1/((n-m)!) + 1/((n-(m+1))!) + 1/((n-(m+2))!) + .. + 1/((n-m)!))`

**Hence, using binomial formula yields that the given equality, `sum_(k=m)^n C_n^k*C_k^m =C_n^m*2^(n-m)` holds.**

**Sources:**