Good day,
I was solving this problem:
Show that $$\frac{\binom{n}{1}}{1} + \frac{\binom{n}{2}}{2} + \frac{\binom{n}{3}}{3} + \cdots + \frac{\binom{n}{n}}{n} = \sum_{r=1}^{n}\frac{2^r-1}{r}$$
I had already made some progress here, and we can prove using induction $$\int_{0}^{1}{\frac{(1 + x) ^ {n} - 1}{x}}dx = \sum_{r=1}^{n}\frac{2^r-1}{r}$$
But this seems too lengthy. Is there a shorter, more elementary solution?
Thanks
You need the two identities:
$\displaystyle {n-1\choose k} + {n-1\choose k-1} = {n\choose k}$ and $\displaystyle \binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1}$
Let $\displaystyle S_n = \sum_{r=1}^{n} \frac{1}{r}{\binom{n}{r}}$ and note that (by def.) $\displaystyle {n-1\choose n} =0. $
$\begin{aligned} \sum_{r=1}^{n} \frac{1}{r}{\binom{n}{r}} & = \sum_{r=1}^{n} \frac{1}{r}{n-1\choose r} + \sum_{r=1}^{n}\frac{1}{r}{n-1\choose r-1} \\& = \sum_{r=1}^{n-1} \frac{1}{r}{n-1\choose r} + \sum_{r=1}^{n}\frac{r}{r \cdot n}{n\choose r} \\& = \sum_{r=1}^{n-1} \frac{1}{r}{n-1\choose r} + \frac{1}{n}\sum_{r=1}^{n}{n\choose r} \\& = \sum_{r=1}^{n-1} \frac{1}{r}{n-1\choose r} + \frac{2^n-1}{n} \\& = \frac{2^n-1}{n} +S_{n-1}\end{aligned} $
Working with this recurrent relation, with $S_0 = 0$ we have:
$\begin{aligned} S_n & = \frac{2^n-1}{n}+S_{n-1} \\& = \frac{2^{n}-1}{n}+\frac{2^{n-1}-1}{n-1}+S_{n-2} \\& = \frac{2^{n}-1}{n}+\frac{2^{n-1}-1}{n-1} + \cdots + \frac{2^{1}-1}{1} +S_0 \\& = \sum_{r=1}^{n} \frac{2^r-1}{r}\end{aligned} $
Alternatively: you've shown that
$$\displaystyle \int_{0}^{1}{\frac{(1 + x) ^ {n} - 1}{x}}dx = \sum_{r=1}^{n}\frac{2^r-1}{r}$$
Since $\displaystyle (1+x)^n-1 = \sum_{r=1}^{n}x^r \binom{n}{r}$ we can write:
\begin{aligned} \sum_{r=1}^{n}\frac{2^r-1}{r} & = \int_{0}^{1}{\frac{(1 + x) ^ {n} - 1}{x}} \, \mathrm dx \\& = \int_{0}^{1}\frac{1}{x} \sum_{r=1}^{n} x^r \binom{n}r \, \mathrm dx \\& = \int_{0}^{1} \sum_{r=1}^{n} x^{r-1} \binom{n}r \, \mathrm dx \\& = \sum_{r=1}^{n} \int_{0}^{1}x^{r-1} \binom{n}r \, \mathrm dx \\& = \sum_{r=1}^{n} \frac{1}{r} \binom{n}r.\end{aligned}