Compute the sum of a series given by non constant coefficient recurrence relation $a_k=(\frac{1}{2})^k-\frac{k}{n-k+1}a_{k-1}$ and $a_1=\frac{1}{2}+\frac{1}{n}(\frac{1}{2})^n-\frac{1}{n}$.($n\ge2$).I want to compute $\lim_{n\to\infty}\sum_{k=1}^{n-1}a_k$.
My first attempt is to find out a general form for $a_k$, and I tried to cast the recurrence relation into the form $f(k)a_k+f(k-1)a_{k-1}=g(k)$ and then the recurrence relation will become linear constant-coefficient one by taking $b_k=f(k)a_k$. However, I failed to convert it.
Also, since $\lim_{n\to\infty}\sum_{k=1}^{n-1}a_k\le\sum_{k=1}^{\infty}(\frac{1}{2})^k=1$, I tried to see if we can evaluate $\lim_{n\to\infty}\sum_{k=1}^{n-1}\frac{k}{n-k+1}a_{k-1}$.
Thanks for any hint.
 A: Preliminary Result
Using the Beta Function Integral, we get
$$
\begin{align}
\sum_{k=0}^m\frac{(-1)^k}{\binom{n}{k}}
&=(n+1)\sum_{k=0}^m\int_0^1(-1)^kt^k(1-t)^{n-k}\,\mathrm{d}t\\
&=(n+1)\sum_{k=0}^m\int_0^1(1-t)^n\left(\frac t{t-1}\right)^k\,\mathrm{d}t\\
&=(n+1)\int_0^1(1-t)^{n+1}\left(1-\left(\frac t{t-1}\right)^{m+1}\right)\mathrm{d}t\\
&=(n+1)\left(\frac1{n+2}+\frac{(-1)^m}{n+2}\frac{(n-m)!(m+1)!}{(n+1)!}\right)\\
&=\frac{n+1}{n+2}\left[1+\frac{(-1)^m}{\binom{n+1}{m+1}}\right]\tag{1}
\end{align}
$$
Now that we have this result, we could verify it more easily by induction.

Apply To The Question
Start with
$$
a_k=\frac1{2^k}-\frac{k}{n-k+1}a_{k-1}\tag{2}
$$
and
$$
a_1=\frac12+\frac1n\frac1{2^n}-\frac1n\tag{3}
$$
Multiply $(2)$ by $(-1)^k\binom{n}{k}$ and rearrange
$$
\underbrace{(-1)^k\binom{n}{k}a_k}_{\large u_k}-\underbrace{(-1)^{k-1}\binom{n}{k-1}a_{k-1}}_{\large u_{k-1}}=(-1)^k\binom{n}{k}\frac1{2^k}\tag{4}
$$
Thus, we can solve for $u_k=(-1)^k\binom{n}{k}a_k$
$$
\begin{align}
\overbrace{(-1)^k\binom{n}{k}a_k}^{\large u_k}
&=\overbrace{\ -na_1\ \ \vphantom{\binom{n}{j}}}^{\large u_1}+\sum_{j=2}^k\overbrace{(-1)^j\binom{n}{j}\frac1{2^j}}^{\large u_j-u_{j-1}}\\
&=-\frac1{2^n}+\sum_{j=0}^k(-1)^j\binom{n}{j}\frac1{2^j}\tag{5}
\end{align}
$$
Therefore,
$$
\begin{align}
\sum_{k=0}^na_k
&=-\frac1{2^n}\sum_{k=0}^n\frac{(-1)^k}{\binom{n}{k}}+\sum_{j=0}^n\sum_{k=j}^n\frac{(-1)^{j+k}}{2^j}\frac{\binom{n}{j}}{\binom{n}{k}}\tag{6a}\\
&=-\frac1{2^n}\frac{n+1}{n+2}\left(1+(-1)^n\right)+\frac{n+1}{n+2}\sum_{j=0}^n\left(-\frac12\right)^j\binom{n}{j}\left[(-1)^n+\frac{(-1)^j}{\binom{n+1}{j}}\right]\tag{6b}\\
&=-\frac1{2^n}\frac{n+1}{n+2}\left(1+(-1)^n\right)+\left(-\frac12\right)^n\frac{n+1}{n+2}\\
&+\frac{n+1}{n+2}\sum_{j=0}^n\frac1{2^j}\left(1-\frac j{n+1}\right)\tag{6c}\\
&=-\frac1{2^n}\frac{n+1}{n+2}\left(1+(-1)^n\right)+\left(-\frac12\right)^n\frac{n+1}{n+2}\\
&+\frac{n+1}{n+2}\left(2-\frac1{2^n}\right)-\frac1{n+2}\left(2-\frac{n+2}{2^n}\right)\tag{6d}\\
&=\frac{n}{n+2}\left(2-\frac1{2^n}\right)\tag{6e}
\end{align}
$$
Explanation:
$\text{(6a)}$: multiply $(5)$ by $\left.(-1)^k\middle/\binom{n}{k}\right.$ and sum in $k$, then change the order of summation
$\text{(6b)}$: apply $(1)$
$\text{(6c)}$: Binomial Theorem and $\left.\binom{n}{j}\middle/\binom{n+1}{j}\right.=1-\frac j{n+1}$
$\text{(6d)}$: $\sum\limits_{j=0}^n\frac1{2^j}=2-\frac1{2^n}$ and $\sum\limits_{j=0}^n\frac j{2^j}=2-\frac{n+2}{2^n}$
$\text{(6e)}$: combine terms

Subtracting $a_0=1-\frac1{2^n}$ and $a_n=0$ from $\text{(6e)}$, we get
$$
\bbox[5px,border:2px solid #C0A000]{\sum_{k=1}^{n-1}a_k
=\frac{n-2}{n+2}+\frac2{n+2}\frac1{2^n}}\tag{7}
$$
and finally,
$$
\bbox[5px,border:2px solid #C0A000]{\lim_{n\to\infty}\sum_{k=1}^{n-1}a_k=1}\tag{8}
$$
A: Only recasting the recurrence relation:
We know that $\frac{n \choose k}{n \choose k-1}=\frac{n-k+1}{k}$ (this is what lighted the bulb!)
So if $b_k={n \choose k}a_k$ we can recast the recurrence as:
$b_k+b_{k-1}={n \choose k}\left(\frac{1}{2}\right)^k$
Which is the linear recurrence that you were looking for.
$b_1=\frac{n-2}{2}+\left(\frac{1}{2}\right)^n$
EDIT: More progress (although I might have some mistakes)...
After playing with the binomial expansion of $\left(1-\frac{1}{2}\right)^n$ it looks like $b_k$ is the partial sum of the aforementioned binomial expansion:
$b_k=\sum_{i=k+1}^{n}(-1)^{i+k+1}{n \choose i}\left(\frac{1}{2}\right)^i$
So:
$a_k={n \choose k}^{-1}\sum_{i=k+1}^{n}(-1)^{i+k+1}{n \choose i}\left(\frac{1}{2}\right)^i$
Although I have to admit that this closed form doesn't help very much in calculating your limit. I have been thinking to further work along the lines of https://mathoverflow.net/questions/201530/partial-sum-of-the-binomial-theorem, but I'm tired and it seems very complicated. The problem should have a shorter trick, but I'm unable to see it.
