<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] Let $b_{n}:=\sum_{k=1}^{n-1}a_{k}$ for $n=2,3,\cdots$,
then $b_{n+1}-b_{n}=a_{n}$ for $n=2,3,\cdots$.
Then, the equation reads as $b_{n+1}-b_{n}=-\frac{1}{2}b_{n}+\frac{n}{4}$ for $n=2,3,\cdots$ with $b_{2}=a_{1}=\frac{1}{4}$. Rearraging the terms, we get $$\begin{cases}b_{n+1}-\frac{1}{2}b_{n}=\frac{n}{4},{\quad}n=2,3,\cdots,\\ b_{2}=\frac{1}{4}.\end{cases}$$
Let $\mu_{n}:=2^{n}$ for $n=2,3,\cdots$.
Multiplying both sides of the equation by $\mu_{n+1}$, we get
$$\mu_{n+1}b_{n+1}-\mu_{n}b_{n}=\mu_{n}\frac{n}{2}.$$
Summing this from $2$ to $(n-1)$ for $n=2,3,\cdots$, we get
$$\begin{aligned}&\underbrace{\sum_{k=2}^{n-1}[\mu_{k+1}b_{k+1}-\mu_{k}b_{k}]}_{\text{telescoping sum}}=\frac{1}{2}\sum_{k=2}^{n-1}k2^{k}\\ &{\implies}\mu_{n}b_{n}-\mu_{2}b_{2}=\frac{1}{2}2^{n}(n-2)\\ &{\implies}b_{n}=\frac{1}{2^{n}}+\frac{1}{2}(n-2),\end{aligned}$$
where we have used the fact that $\mu_{2}b_{2}=1$.
Then, the desired solution is $$a_{n}=b_{n+1}-b_{n}=\frac{1}{2}\bigg(1-\frac{1}{2^{n}}\bigg),{\quad}n=2,3,\cdots.\tag*{$\blacksquare$}$$
</s>