Prove that $\sum_{r=1}^n \frac 1{r}\binom{n}{r} = \sum_{r=1}^n \frac 1{r}(2^r - 1)$ 
Let $n$ be a nonnegative integer. Prove that $\sum\limits_{r=1}^n \dfrac 1{r}\dbinom{n}{r} = \sum\limits_{r=1}^n \dfrac 1{r}(2^r - 1)$.

One thing I have tried is to represent both $\binom{n}{r}$ and $2^r$ as sums of binomial coefficients, i.e. $\sum \binom{i}{r-1}$ and $\sum \binom{r}{i}$ respectively, but it does not seem to be helpful. I have also tried to use binomial identities but I do not see how they can be applied to the problem.
 A: $$\sum_{r=1}^n \frac{1}{r}\binom{n}{r}=\int_{0}^1\sum_{r=1}^n\binom{n}{r}x^{r-1}dx=\int_{0}^1\frac{(1+x)^r-1}{x}dx\\=\int_{0}^1\sum_{r=1}^n (1+x)^{r-1}dx\\=\sum_{r=1}^n \frac{2^r-1}{r}$$
A: Solution without using calculus:
$$\begin{align}
\sum_{r=1}^n\frac 1r\binom nr
&=\sum_{r=1}^n\frac 1r\sum_{k=r}^n\binom kr-\binom{k-1}r
\qquad\qquad\qquad\text{(*)}\\
&=\sum_{r=1}^n\frac 1r\sum_{k=r}^n\binom {k-1}{r-1}\\
&=\sum_{r=1}^n\sum_{k=r}^n\frac1k\binom kr\\
&=\sum_{k=1}^n\frac 1k\sum_{r=1}^k\binom kr\\
&=\sum_{k=1}^n\frac 1k(2^k-1)\\
&=\sum_{r=1}^n\frac 1r(2^r-1)\qquad\blacksquare
\end{align}$$
* by "untelescoping" $\binom nr$ and noting that $\binom {r-1}r=0$.
A: 
Just for seeing an elementary one:

Using Pascal's rule we have:
$$\sum _{k=1}^{n}\binom{n}{k}\frac{1}{k}=\sum _{k=1}^{n}\binom{n-1}{k-1}\frac{1}{k}+\underbrace{\sum _{k=1}^{n}\binom{n-1}{k}\frac{1}{k}}_{(1)}$$$$=\sum _{k=1}^{n}\binom{n-1}{k-1}\frac{1}{k}+\underbrace{\sum _{k=1}^{n}\binom{n-2}{k-1}\frac{1}{k}+\sum _{k=1}^{n}\binom{n-2}{k}\frac{1}{k}}_{(1)}$$$$=\sum _{k=1}^{n}\binom{n-1}{k-1}\frac{1}{k}+\sum _{k=1}^{n}\binom{n-2}{k-1}\frac{1}{k}+\sum _{k=1}^{n}\binom{n-3}{k-1}\frac{1}{k}+\sum _{k=1}^{n}\binom{n-3}{k}\frac{1}{k}$$
On the other hand:
$$\sum _{k=1}^{n}\binom{n-r}{k-1}\frac{1}{k}=\frac{1}{n-r+1}\sum _{k=1}^{n}\binom{n-r+1}{k}$$$$=\frac{1}{n-r+1}\left[\color{red}{\sum _{k=0}^{n-r+1}\binom{n-r+1}{k}}+\sum _{k=n-r+2}^{n}\binom{n-r+1}{k}-1\right]$$$$=\frac{\color{red}{2^{n-r+1}}-1}{n-r+1}\tag{I}$$
Continuing this way:$$\sum _{k=1}^{n}\binom{n}{k}\frac{1}{k}=\sum _{k=1}^{n}\binom{n-1}{k-1}\frac{1}{k}+\sum _{k=1}^{n}\binom{n-2}{k-1}\frac{1}{k}+...+\sum _{k=1}^{n}\binom{n-(n-1)}{k-1}\frac{1}{k}+\color{blue}{\sum _{k=1}^{n}\binom{n-(n-1)}{k}\frac{1}{k}}$$
Using (I) implies:
$$=\sum_{k=0}^{n-2}\frac{2^{\left(n-k\right)}-1}{n-k}+\color{blue}{1}$$
Hence:
$$\sum _{k=1}^{n}\binom{n}{k}\frac{1}{k}=\sum_{k=0}^{n-2}\frac{2^{\left(n-k\right)}-1}{n-k}+\color{blue}{1}$$
Setting $n-k \mapsto k$ follows:
$$\bbox[5px,border:2px solid #00A000]{\sum _{k=1}^{n}\binom{n}{k}\frac{1}{k}=\sum_{k=1}^{n}\frac{2^{k}-1}{k}}$$
A: Another solution written for one of my classes.
We must prove that
\begin{equation}
\sum_{r=1}^{n}\dfrac{1}{r}\dbinom{n}{r}=\sum_{r=1}^{n}\dfrac{2^{r}-1}
{r}
\label{darij1.eq.1}
\tag{1}
\end{equation}
holds for each nonnegative integer $n$.
Here is a proof of \eqref{darij1.eq.1} by induction on $n$:
The base case (the case $n=0$) is trivial, since the equality \eqref{darij1.eq.1} boils down to $0=0$ in this case (recall that empty sums are $0$ by definition).
For the induction step, we fix some positive integer $m$, and we assume that
\eqref{darij1.eq.1} holds for $n=m-1$. We must now prove that
\eqref{darij1.eq.1} holds for $n=m$.
We recall the following basic facts:

*

*Sum of a row in Pascal's triangle: We have
\begin{equation}
\sum_{r=0}^{n}\dbinom{n}{r}=2^{n}\qquad\text{for each integer }n\geq
0.
\label{darij1.eq.2n}
\tag{2}
\end{equation}
(This follows from substituting $x=1$ and $y=1$ into the binomial formula
$\left(  x+y\right)  ^{n}=\sum\limits_{r=0}^{n}\dbinom{n}{r}x^{r}y^{n-r}$.)


*Absorption identity: We have
\begin{align}
\dfrac{n}{k}\dbinom{n-1}{k-1}=\dbinom{n}{k}\qquad\text{for any integers
}n\text{ and }k>0.
\end{align}
(This follows by recalling the definitions of the two binomial coefficients:
\begin{align*}
\dbinom{n}{k}  & =\dfrac{n\left(  n-1\right)  \left(  n-2\right)
\cdots\left(  n-k+1\right)  }{k!}\qquad\text{and}\\
\dbinom{n-1}{k-1}  & =\dfrac{\left(  n-1\right)  \left(  n-2\right)
\cdots\left(  n-k+1\right)  }{\left(  k-1\right)  !},
\end{align*}
and comparing the left and right hand sides.)


*Pascal recursion: We have
\begin{align}
\dbinom{n}{k}=\dbinom{n-1}{k-1}+\dbinom{n-1}{k}\qquad\text{for any integers
}n\text{ and }k>0.
\end{align}
Furthermore, recall that $\dbinom{n}{k}=0$ whenever $n$ is a nonnegative
integer and $k$ is an integer satisfying $k>n$. Applying this to $n=m-1$ and
$k=m$, we obtain $\dbinom{m-1}{m}=0$ (since $m-1$ is a nonnegative integer and
$m>m-1$).
However, the Pascal recursion yields that
\begin{align}
\dbinom{m}{r}=\dbinom{m-1}{r-1}+\dbinom{m-1}{r}
\end{align}
for each integer $r>0$. Thus,
\begin{align*}
& \sum_{r=1}^{m}\dfrac{1}{r}\underbrace{\dbinom{m}{r}}_{=\dbinom{m-1}
{r-1}+\dbinom{m-1}{r}}\\
& =\sum_{r=1}^{m}\dfrac{1}{r}\left(  \dbinom{m-1}{r-1}+\dbinom{m-1}{r}\right)
\\
& =\sum_{r=1}^{m}\dfrac{1}{m}\cdot\underbrace{\dfrac{m}{r}\dbinom{m-1}{r-1}
}_{\substack{=\dbinom{m}{r}\\\text{(by the absorption identity)}
}}+\underbrace{\sum_{r=1}^{m}\dfrac{1}{r}\dbinom{m-1}{r}}_{=\sum
\limits_{r=1}^{m-1}\dfrac{1}{r}\dbinom{m-1}{r}+\dfrac{1}{m}\dbinom{m-1}{m}}\\
& =\underbrace{\sum_{r=1}^{m}\dfrac{1}{m}\cdot\dbinom{m}{r}}_{=\dfrac{1}
{m}\sum\limits_{r=1}^{m}\dbinom{m}{r}}+\sum\limits_{r=1}^{m-1}\dfrac{1}
{r}\dbinom{m-1}{r}+\dfrac{1}{m}\underbrace{\dbinom{m-1}{m}}_{\substack{=0}}\\
& =\dfrac{1}{m}\underbrace{\sum\limits_{r=1}^{m}\dbinom{m}{r}}_{=\sum
\limits_{r=0}^{m}\dbinom{m}{r}-\dbinom{m}{0}}+\underbrace{\sum\limits_{r=1}
^{m-1}\dfrac{1}{r}\dbinom{m-1}{r}}_{\substack{=\sum\limits_{r=1}^{m-1}
\dfrac{2^{r}-1}{r}\\\text{(because we assumed }\\\text{that
\eqref{darij1.eq.1} holds for }n=m-1\text{)}}}+\underbrace{\dfrac{1}{m}0}
_{=0}\\
& =\dfrac{1}{m}\left(  \underbrace{\sum\limits_{r=0}^{m}\dbinom{m}{r}
}_{\substack{=2^{m}\\\text{(by \eqref{darij1.eq.2n})}}}-\underbrace{\dbinom
{m}{0}}_{=1}\right)  +\sum\limits_{r=1}^{m-1}\dfrac{2^{r}-1}{r}\\
& =\underbrace{\dfrac{1}{m}\left(  2^{m}-1\right)  }_{=\dfrac{2^{m}-1}{m}
}+\sum\limits_{r=1}^{m-1}\dfrac{2^{r}-1}{r}=\dfrac{2^{m}-1}{m}+\sum
\limits_{r=1}^{m-1}\dfrac{2^{r}-1}{r}\\
& =\sum\limits_{r=1}^{m}\dfrac{2^{r}-1}{r}.
\end{align*}
In other words, \eqref{darij1.eq.1} holds for $n=m$. This completes the
induction step. Thus, \eqref{darij1.eq.1} is proved by induction.
Remark: Another known identity analogous to \eqref{darij1.eq.1} is
\begin{equation}
\sum_{r=1}^{n}\dfrac{\left(-1\right)^{r-1}}{r}\dbinom{n}{r} = \sum_{r=1}^{n}\dfrac{1}{r} .
\label{darij1.eq.3}
\tag{3}
\end{equation}
It is a nice exercise to unite \eqref{darij1.eq.1} and \eqref{darij1.eq.3} under a common generalization.
