<s>[INST] 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.
 [/INST] 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.
</s>