The average of reciprocal binomials

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}. $$

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}