The average of reciprocal binomials This question is motivated by the MO problem here. Perhaps it is not that difficult. 

Question. Here is an cute formula. 
  $$\frac1n\sum_{k=0}^{n-1}\frac1{\binom{n-1}k}=\sum_{k=1}^n\frac1{k2^{n-k}}.$$
  I've one justification along the lines of Wilf-Zeilberger (see below). Can you provide an alternative proof? Or, any reference?

The claim amounts to $a_n=b_n$ where
$$a_n:=\sum_{k=0}^{n-1}\frac{2^n}{n\binom{n-1}k} \qquad \text{and} \qquad
b_n:=\sum_{k=1}^n\frac{2^k}k.$$
Define $F(n,k):=\frac{2^n}{n\binom{n-1}k}$ and $\,G(n,k)=-\frac{2^n}{(n+1)\binom{n}k}$. Then, it is routinely checked that 
$$F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k),\tag1$$ 
for instance by dividing through with $F(n,k)$ and simplifying. Summing (1) over $0\leq k\leq n-1$:
\begin{align}
\sum_{k=0}^{n-1}F(n+1,k)-\sum_{k=0}^{n-1}F(n,k)
&=a_{n+1}-\frac{2^{n+1}}{n+1}-a_n, \\
\sum_{k=0}^{n-1}G(n,k+1)-\sum_{k=0}^{n-1}G(n,k)
&=-\sum_{k=1}^n\frac{2^n}{(n+1)\binom{n}k}+\sum_{k=0}^{n-1}\frac{2^n}{(n+1)\binom{n}k}=0. \end{align}
Therefore, $a_{n+1}-a_n=\frac{2^{n+1}}{n+1}$. But, it is evident that $b_{n+1}-b_n=\frac{2^{n+1}}{n+1}$. Since $a_1=b_1$, it follows $a_n=b_n$ for all $n\in\mathbb{N}$.
=====================================
Here is an alternative approach to Fedor's answer below in his elaboration of Fry's comment.
With $\frac1{n+1}\binom{n}k=\int_0^1x^{n-k}(1-x)^kdx$, we get $a_{n+1}=2^{n+1}\int_0^1\sum_{k=0}^nx^{n-k}(1-x)^kdx$. So,
\begin{align}
2^{n+1}\int_0^1 dx\sum_{k=0}^nx^{n-k}(1-x)^k
&=2^{n+1}\int_0^1x^ndx\sum_{k=0}^n\left(\frac{1-x}x\right)^k \\
&=2^{n+1}\int_0^1x^n\frac{\left(\frac{1-x}x\right)^{n+1}-1}{\frac{1-x}x-1}dx \\
&=\int_0^1\frac{(2-2x)^{n+1}-(2x)^{n+1}}{1-2x}\,dx:=c_{n+1}.
\end{align}
Let's take successive difference of the newly-minted sequence $c_{n+1}$:
\begin{align}
c_{n+1}-c_n
&=\int_0^1\frac{(2-2x)^{n+1}-(2-2x)^n+(2x)^n-(2x)^{n+1}}{1-2x}\,dx \\
&=\int_0^1\left[(2-2x)^n+(2x)^n\right]dx=2^{n+1}\int_0^1x^ndx=\frac{2^{n+1}}{n+1}. \end{align}
But, $b_{n+1}-b_n=\frac{2^{n+1}}{n+1}$ and hence $a_n=b_n$.
 A: Let me elaborate on Fry's suggestion and your forthcoming comment.
$$\frac1{2^{n+1}}\sum_{k=1}^{n+1}\frac{2^k}k=\frac1{2^{n+1}}\int_0^2(1+x+\dots+x^n)dx=\frac1{2^{n+1}}\int_0^2\frac{1-x^{n+1}}{1-x}dx=\\2\int_{0}^1\frac{(1/2)^{n+1}-t^{n+1}}{1-2t}dt=2\int_{0}^1\frac{(1-s)^{n+1}-(1/2)^{n+1}}{1-2s}ds.$$
We used change of variables $x=2t$, $s=1-t$. Now take a half-sum of two last expressions (identifying $t$ and $s$), you get
$$
\int_{0}^1\frac{(1-t)^{n+1}-t^{n+1}}{1-2t}dt=\sum_{k=0}^n\int_0^1(1-t)^kt^{n-k}dt=\sum_{k=0}^n\frac1{(n+1)\binom{n}k}.
$$
A: As in the question
$$a_n:=\sum_{k=0}^{n-1}\frac{2^n}{n\binom{n-1}k} \qquad \text{and} \qquad
b_n:=\sum_{k=1}^n\frac{2^k}k.$$
It is clear that $a_1=b_1$ and $b_{n+1}-b_n=\frac{2^{n+1}}{n+1}$. But we have the same recursive relation for $a_n$ because
\begin{align}
a_n&=2^n\sum_{k=0}^{n-1}\frac{k!(n-1-k)!(k+1+n-k)}{n!(n+1)} \\
&=2^n\sum_{k=0}^{n-1}\left(\frac{(k+1)!(n-1-k)!}{(n+1)!}+\frac{k!(n-k)!}{(n+1)!}\right) \\
&=2^n\left(2\sum_{k=0}^{n}\frac{k!(n-k)!}{(n+1)!}-\frac{2}{n+1}\right)=a_{n+1}-\frac{2^{n+1}}{n+1}.
\end{align}
