<s>[INST] Can I get a hint on solving this recurrence relation? I am having trouble solving for a closed form of the following recurrence relation.
$$\begin{align*}
a_n &= \frac{n}{4} -\frac{1}{2}\sum_{k=1}^{n-1}a_k\\
a_1 &= \frac{1}{4}
\end{align*}$$
The first few values are $a_1=\frac{1}{4},a_2=\frac{3}{8},a_3=\frac{7}{16},a_4=\frac{15}{32}...$ So it seems the pattern is $a_n = \frac{2^{n}-1}{2^{n+1}}$, but I have been unable to show this algebraically. Here is what I tried:
$$\begin{align*}
2a_n &= \frac{n}{2} - \sum_{k=1}^{n-1}a_k\\
a_n + \sum_{k=1}^n a_k &= \frac{n}{2}\\
a_{n-1} + \sum_{k=1}^{n-1} a_k &= \frac{n-1}{2} \\
2a_n - a_{n-1} & = \frac{1}{2} \\
a_n = \dfrac{2a_{n-1} + 1}{4}
\end{align*}$$
I am so close, I can taste the closed form. Can someone nudge me in the right direction without giving too much away?
 [/INST] You could use generating functions. Put $$f(z) = \sum_{n\ge 1} a_n z^n.$$
Summing your recurrence for $n\ge 2$ and multiplying by $z^n,$ we get
$$ f(z) - \frac{1}{4} z = \frac{1}{4} \sum_{n\ge 2} n z^n
- \frac{1}{2} z \sum_{n\ge 2} z^{n-1} \sum_{k=1}^{n-1} a_k.$$
Simplify to obtain
$$ f(z) - \frac{1}{4} z =  \frac{1}{4} \frac{z^2(2-z)}{(1-z)^2}
- \frac{1}{2} z \frac{1}{1-z} f(z).$$
Now solve for $f(z).$ This yields
$$ f(z) = \frac{1}{2} \frac{z}{(1-z)(2-z)}
= \frac{1}{2} \frac{1}{1-z} -  \frac{1}{2} \frac{1}{1-z/2}.$$
Finally read off the coefficients, which is now easy, to get
$$a_n = \frac{1}{2} \left(1 - \frac{1}{2^n}\right).$$ 
</s>