Show that $a_n=\frac{n+1}{2n}a_{n-1}+1$ 
Show that $a_n=\frac{n+1}{2n}a_{n-1}+1$ given that:
$a_n=1/{{n}\choose{0}}+1/{{n}\choose{1}}+...+1/{{n}\choose{n}}$

The hint says to consider when $n$ is even and odd. When $n=2k$ I get:
$$a_{n}=1/{{2k}\choose{0}}+1/{{2k}\choose{1}}+...+1/{{2k}\choose{2k}}$$
$$=1+1/{{2k}\choose{1}}+...+1/{{2k}\choose{2k}}$$
$$=1+1/(2k{{2k-1}\choose{0}})+1/(\frac{2k}{2}{{2k-1}\choose{0}})...+1/(\frac{2k}{2k}{{2k-1}\choose{2k-1}})$$
$$=1+\frac{1}{2k}(1/{{2k-1}\choose{0}}+1/{{2k-1}\choose{1}}+1/{{2k-1}\choose{2k-1}})$$
which should be $\frac{2k+1}{4k}a_{n-1}+1$ in the end.
I used:
${{n}\choose{k}}=\frac{n}{k}{{n-1}\choose{k-1}}$ and tried ${{n-1}\choose{k-1}}={{n-1}\choose{n-k}}$

First, observe that the given recursion can be written as $$2n(a_n - 1) - (n+1)a_{n-1} = 0.$$  Second, observe that $$a_n - 1 = \sum_{k=0}^{n-1} \binom{n}{k}^{\!-1},$$ since the final term of $a_n$ is always $1$.  Therefore, the relationship to be proven is equivalent to showing $$0 = S_{n-1} = \sum_{k=0}^{n-1} \frac{2n}{\binom{n}{k}} - \frac{n+1}{\binom{n-1}{k}}.$$  Simplify the summand by factoring out $\binom{n-1}{k}^{\!-1}$:  $$\frac{2n}{\binom{n}{k}} - \frac{n+1}{\binom{n-1}{k}} = \frac{n-1-2k}{\binom{n-1}{k}}.$$  Now, with the substitution $m = n-1-k$, we observe that the RHS sum $S_{n-1}$ is now $$S_{n-1} = \sum_{m=n-1}^0 \frac{n-1 - 2(n-1-m)}{\binom{n-1}{n-1-m}} = \sum_{m=0}^{n-1} \frac{-(n-1 - 2m)}{\binom{n-1}{m}},$$ where in the last step we use the reflection identity $$\binom{n}{m} = \binom{n}{n-m}.$$  Therefore, $S_{n-1} = -S_{n-1}$, from which it follows that $S_{n-1} = 0$, proving the required recursion.  No need to use odd/even cases.
