By considering the expansion of \((1+x)^n\) where \(n\) is a positive integer, or otherwise, show that:
- \(\dbinom{n}{0}+\dbinom{n}{1}+\dbinom{n}{2}+\dotsb+\dbinom{n}{n}=2^n\);
To answer part (i), we put \(x=1\) into \(\eqref{eq:1}\), which tells us that \[ 2^n=\sum_{k=0}^n\dbinom{n}{k}. \]
By considering the expansion of \((1+x)^n\) where \(n\) is a positive integer, or otherwise, show that:
- \(\dbinom{n}{1}+2\dbinom{n}{2}+3\dbinom{n}{3}+\dotsb+n\dbinom{n}{n}=n2^{n-1}\);
Let’s start by using the expansion. This time we want \[\sum_{k=1}^n k\dbinom{n}{k}.\]
We know that \(\dbinom{n}{k} = \dfrac{n!}{(n-k)!k!}\) so let’s try rearranging this expression to something more helpful.
We can rewrite \(\dfrac{n!}{(n-k)!k!}\) as \(\dfrac{n!}{k\times(n-k)!(k-1)!}=\dfrac{1}{k}\times \dfrac{n!}{(n-k)!(k-1)!}\).
This is helpful because we could substitute it for the binomial terms and then the \(k\) in the summation will cancel, but at the moment the rest isn’t very helpful, so let’s have another play!
Using the very common “trick” of adding and subtracting the same value we can rearrange \(\dfrac{n!}{(n-k)!(k-1)!}=\dfrac{n!}{((n-1)-(k-1))!(k-1)!}\) which is very helpful because the denominator now looks like it comes from a binomial coefficient, and we know we can just separate out the \(n\) in the numerator as we did before with \(k\) thus giving us \(\dbinom{n}{k}=\dfrac{n}{k}\times \dbinom{n-1}{k-1}\).
We can now rewrite \[\sum_{k=1}^n k\dbinom{n}{k} = \sum_{k=1}^n k \dfrac{n}{k}\dbinom{n-1}{k-1}=\sum_{k=1}^n n\dbinom{n-1}{k-1}=n\sum_{k=1}^n \dbinom{n-1}{k-1}.\]
Comparing to part (i) \[\sum_{k=0}^n\dbinom{n}{k}=2^n\] we note that we want \(k\) to run through from \(1\) to \(n\) which means \(k-1\) runs from \(0\) to \(n-1\) so we can use the result from (i) if we change the summation to finish at \(n-1\)
Note that we know \(n \ge 1\) and this time \(k\) runs from \(1\) to \(n\) so \(n-1\) and \(k-1\) do not cause any issues.
\[n\sum_{k=1}^n \dbinom{n-1}{k-1}=n\sum_{k=0}^{n-1}\dbinom{n-1}{k}=n2^{(n-1)}\]
- \(\dbinom{n}{0}+\dfrac{1}{2}\dbinom{n}{1}+\dfrac{1}{3}\dbinom{n}{2}+\dotsb+\dfrac{1}{n+1}\dbinom{n}{n}=\dfrac{1}{n+1}(2^{n+1}-1)\);
Let’s continue to work through using manipulations of the binomial coefficients.
This time we note that we are asked for \[\begin{equation}\sum_{k=0}^n \dfrac{1}{k+1} \dbinom{n}{k}. \label{eq:2} \end{equation}\]We would like to pull out a factor of \(k+1\) to cancel in \(\eqref{eq:2}\). So we write \[ \frac{n!}{(n-k)!k!}=(k+1)\frac{n!}{(n-k)!(k+1)!}, \] and to make this of the right form, we write \[ (k+1)\frac{n!}{(n-k)!(k+1)!}=\frac{k+1}{n+1}\frac{(n+1)!}{(n-k)!(k+1)!}=\frac{k+1}{n+1}{n+1\choose k+1}. \] Using this in \(\eqref{eq:2}\), we have \[ \sum_{k=0}^n\frac{1}{k+1}\dbinom{n}{k}=\sum_{k=0}^n\frac{1}{n+1}{n+1\choose k+1}=\frac{1}{n+1}\sum_{k=1}^{n+1}{n+1\choose k}. \] This is really close to being able to apply part (i), but \(k\) starts at \(1\) in the sum rather than \(0\). Since \({n+1\choose 0}=1\), we run the sum from \(0\) but compensate by subtracting \(1\), that is, \[ \frac{1}{n+1}\sum_{k=1}^{n+1}{n+1\choose k}=\frac{1}{n+1}\left(\sum_{k=0}^{n+1}{n+1\choose k}-1\right). \] So we can now apply (i), and we find that \[ \sum_{k=0}^n\frac{1}{k+1}\dbinom{n}{k}=\frac{1}{n+1}(2^{n+1}-1), \] as required.
- \(\dbinom{n}{1}+2^2\dbinom{n}{2}+3^2\dbinom{n}{3}+\dotsb+n^2\dbinom{n}{n}=n(n+1)2^{n-2}\).
We can straight away apply that \(\dbinom{n}{k}=\dfrac{n}{k}\dbinom{n-1}{k-1}\), as we deduced in part (ii), to find that \[ \sum_{k=1}^nk^2\dbinom{n}{k}=\sum_{k=1}^n nk\dbinom{n-1}{k-1}=n\sum_{k=0}^{n-1} (k+1)\dbinom{n-1}{k}. \] We are really close to being able to apply (ii) again, but we have \(k+1\) and not \(k\) as the coefficient of \(\binom{n-1}{k}\). However, we can write \[ n\sum_{k=0}^{n-1}(k+1){n-1\choose k}=n\sum_{k=0}^{n-1}\left(k{n-1\choose k}+{n-1\choose k}\right). \] Now the first term we can find from part (ii) (\(k\) runs from zero rather than one, but the first term is zero anyway), and moreover we can find the second term by part (i). Therefore, we have that \[ \sum_{k=1}^nk^2\dbinom{n}{k}=n((n-1)2^{n-2}+2^{n-1})=n2^{n-2}(n-1+2)=n(n+1)2^{n-2}, \] as required.
