Question

Prove the following statements with either induction, strong induction or proof by smallest counterexample. Prove that \(\sum_{k=1}^{n} k\left(\begin{array}{l}n \\ k\end{array}\right)=n 2^{n-1}\) for each natural number \(n\).

Short answer

The given statement is proven by mathematical induction.

Step-by-step solution

Base Case

Start by proving the statement for the base case n=1. Left Side (LS) = 1(1 choose 1) = 1, Right Side (RS) = 1*2^(1-1) = 1. LS = RS, thus the statement holds for n=1.

Inductive Hypothesis

Assume the statement is true for some arbitrary natural number k, i.e., sum from i=1 to k of i*(k choose i) equals k*2^(k-1). This is the inductive hypothesis.

Inductive Step

Prove that the statement holds for n=k+1. LS = sum from i=1 to k+1 of i*((k+1) choose i). By splitting the sum into two parts, one from i=1 to k, and another considering the term for i=k+1 separately, and using the inductive hypothesis on the first part, one gets that LS = (k+1)*2^k. Expand RS = (k+1)*2^(k+1-1) = (k+1)*2^k. LS = RS. This completes the inductive step.