Combinatorial or Probabilistic proof of the identity $\sum_{k=0}^n \binom{n}{k}\frac{1}{k+1} = \frac{2^{n+1}-1}{n+1}$ While teaching Combinatorics to first year students, I like to discuss several ways to prove each identity involving binomial coefficients.
For instance, one can show that $\sum_{k=0}^nk \binom{n}{k} = n2^{n-1}$ by: 1) replacing $k \binom{n}{k}$ with $n \binom{n-1}{k-1}$; 2) differentiation the binomial identity; 3) counting the number of pairs $(x,A)$ such that $x \in A \subseteq [n]$.
To deal with the related identity $\sum_{k=0}^n \binom{n}{k}\frac{1}{k+1} = \frac{2^{n+1}-1}{n+1}$, one could easily adjust the first two approaches from the previous paragraph: 1) replace $\binom{n}{k}\frac{1}{k+1}$ with $\binom{n+1}{k+1}\frac{1}{n+1}$; 2) integrate the binomial identity. However, it took me a while to come up with a combinatorial or probabilistic proof of this identity.
To be honest, I almost gave up and decided to ask for help here, but found the solution while typing this question. Nevertheless, I think it's still worth posting since it was not easy for me to find the desired argument either in my head or on google and math.stackexchange and since someone else might find it helpful.
I agree that my arguments might be not quite comprehensible for some first year students. So, if you see an easier or more intuitive solution, feel free to post it here!
 A: Both sides of the identity are just the expected number of subsets $A \subseteq [n]$ such that $\max_{i \in A}\sigma(i) < \sigma(n+1)$ in a random permutation $\sigma$ of $[n+1]$ counted in two different ways.
To be more precise (and to avoid mentioning the notions of probability theory, which confuse first year students sometimes), let us denote by $N$ the number of pairs $(\sigma, A)$, where $A$ is a subset of $[n]:=\{1,\dots,n\}$, $\sigma$ is an element of $S_{n+1}$, i.e. a permutation of $[n+1]$, and $\max_{i \in A}\sigma(i) < \sigma(n+1)$.
One the one hand, observe that
\begin{align}
N = & \ \sum_{A \subseteq [n]} \#\left\{ \sigma \in S_{n+1} : \max_{i \in A}\sigma(i) < \sigma(n+1) \right\} \\
= \sum_{k=0}^{n}&\sum_{\substack{A \subseteq [n] \\ |A|=k}} \#\left\{ \sigma \in S_{n+1} : \max_{i \in A}\sigma(i) < \sigma(n+1) \right\} = \sum_{k=0}^{n} \binom{n}{k}\frac{(n+1)!}{k+1}
\end{align}
since there are $\binom{n}{k}$ ways to fix a $k$-element $A\subseteq [n]$ and for each of them, there are $\frac{(n+1)!}{k+1}$ ways to choose $\sigma \in S_{n+1}$ with the desired property.
On the other hand, note that
\begin{align}
N = \sum_{\sigma \in S_{n+1}}\ &\#\left\{ A \subseteq [n] : \max_{i \in A}\sigma(i) < \sigma(n+1) \right\} \\
= \sum_{m=1}^{n+1}\sum_{\substack{\sigma \in S_{n+1} \\ \sigma(n+1)=m}}\!\! &\#\left\{ A \subseteq [n] : \max_{i \in A}\sigma(i) < \sigma(n+1) \right\} = \sum_{m=1}^{n+1} n! \cdot 2^{m-1} = n! \cdot (2^{n+1}-1)
\end{align}
since given $m \in [n+1]$, there are $n!$ ways to fix $\sigma \in S_{n+1}$ such that $\sigma(n+1)=m$ and for each of them, there are $2^{m-1}$ ways to choose $A \subseteq [n]$ with the desired property.
Dividing both the expressions for $N$ found above by $(n+1)!$, we obtain the desired identity.
Remark 1. One can prove more general identity in the same vain. Given $x \in \mathbb{R}$, consider a random variable $f$ defined by the equation
$$f(\sigma)= \sum_{\substack{A \subseteq [n] \\ \max_{i \in A}\sigma(i) < \sigma(n+1)}} x^{|A|+1}$$
for a permutation $\sigma \in S_{n+1}$ chosen uniformly at random. Similar to how we handled the $x=1$ case above, one can count the expectation of $f$ in two straightforward ways to conclude that
$$ \sum_{k=0}^{n} \binom{n}{k}\frac{x^{k+1}}{k+1} = \mbox{E}[f] = \sum_{m=1}^{n+1} \frac{x(1+x)^{m-1}}{n+1} = \frac{(1+x)^{n+1}-1}{n+1}.$$
Of course there are many simpler non-combinatorial ways to prove this identity.
Remark 2. In is known than any $k+1$ elements of $[n+1]$ lie on the same cycle in a random permutation of $[n+1]$ with probability $\frac{1}{k+1}$. Therefore, if one finds it more comprehensible, there would be no harm to any of the arguments above in replacing all the '$\max_{i \in A}\sigma(i) < \sigma(n+1)$' conditions with '$A$ and $n+1$ lie on the same cycle in $\sigma$'.
