Proof by induction that I'm stumped on.

Question

$$\sum \limits_{k=1}^{n}k(_k^n)=n2^{n-1} $$

I'm trying to solve this by induction but I have no idea where to start and induction was not taught very well so I'm trying to get it cleared up in any way possible.

Answer 1

Let $S=\{a_1, a_2, \dots, a_n\}$. Number of $k$-subsets is equal to $C_n^k$. Number of elements in $k$-subsets is equal to $kC_n^k$. Total $\sum \limits_{k=1}^{n}kC_n^k$.

But on the other hand, it is equal to $n2^{n-1}$ (because each $k$-set we can complete to $n$-set adding $(n-k)$ elements. After this process we have $2^n$ $n$-subsets but each set meets twice. So, $\dfrac{n2^n}{2}=n2^{n-1}$). We get $\sum \limits_{k=1}^{n}kC_n^k=n2^{n-1}.$ It was a combinatorial proof.

Let's go to inductional proof.

We see that for $n=1$ it's true. Let it be true for $n-1$. Then we have $\sum \limits_{k=1}^{n-1}kC_{n-1}^{k}=(n-1)2^{n-2}$.

Now we will prove for $n$. Here we will use this property of binomial coefficients: $C_n^k=C_{n-1}^k+C_{n-1}^{k-1}$.

$$\sum \limits_{k=1}^{n}kC_n^k=\sum \limits_{k=1}^{n}kC_{n-1}^{k}+\sum \limits_{k=1}^{n}kC_{n-1}^{k-1}=(n-1)2^{n-2}+\sum \limits_{k=1}^{n}((k-1)+1)C_{n-1}^{k-1}=(n-1)2^{n-2}+\sum \limits_{k=1}^{n}(k-1)C_{n-1}^{k-1}+\sum\limits_{k=1}^{n}C_{n-1}^{k-1}=(n-1)2^{n-2}+(n-1)2^{n-2}+2^{n-1}=n2^{n-1}.$$ Q.E.D.

Answer 2

Actually quite nice, if you remember your binomial coefficients, basic summation manipulation, and Pascal's identity: $$ \binom{n + 1}{k} = \binom{n}{k} + \binom{n}{k - 1} $$ Base: $n = 1$ is trivial

Induction: We will compute the left hand side for $n + 1$, and reach the corresponding right hand side. \begin{align} \sum_{1 \le k \le n + 1} k \binom{n + 1}{k} &= \sum_{1 \le k \le n + 1} k \left( \binom{n}{k} + \binom{n}{k - 1} \right) \\ &= \sum_{1 \le k \le n + 1} k \binom{n}{k} + \sum_{1 \le k \le n + 1} k \binom{n}{k - 1} \\ &= \sum_{1 \le k \le n} k \binom{n}{k} + \sum_{0 \le k \le n} (k + 1) \binom{n}{k} \\ &= n 2^{n - 1} + 1 \cdot \binom{n}{0} + \sum_{1 \le k \le n} k \binom{n}{k} + \sum_{1 \le k \le n} \binom{n}{k} \\ &= n 2^{n - 1} + 1 + n 2^{n - 1} + 2^n - 1 \\ &= (n + 1) 2^n \end{align} This is the claim for $n + 1$.

I didn't write down where the induction hypothesis is used (twice), and where I'm using that $$ \sum_{0 \le k \le n} \binom{n}{k} = (1 + 1)^n = 2^n $$ The LaTeX here is sadly underpowered for this.

Answer 3

A completely different track to prove the identity is to use generating functions. Note that: $$ \sum_{1 \le k \le n} \binom{n}{k} z^k = (1 + z)^n - 1 $$ To get a factor $k$ multiplying the binomial coefficient, differentiate the above polynomial: $$ z \frac{\mathrm{d}}{\mathrm{d} z} ((1 + z)^n - 1) = n z (1 + z)^{n - 1} = \sum_{1 \le k \le n} k \binom{n}{k} z^k $$ Evaluate at $z = 1$ to get: $$ \sum_{1 \le k \le n} k \binom{n}{k} = n 2^{n - 1} $$ Computing: $$ \sum_{1 \le k \le n} k^2 \binom{n}{k} $$ is left as an exercise.