# 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?

• Consider the homogeneous case $2a_n-a_{n-1}=0$ and then consider that you can find a trivial constant particular solution to your recurrence namely $a_n=1/2$ – obataku Aug 30 '13 at 2:25
• Are you allowed to prove your guess via induction? – Adriano Aug 30 '13 at 2:37
• You can use this technique. – Mhenni Benghorbal Aug 30 '13 at 4:33

By inspection we determine a particular solution to $2a_n-a_{n-1}=1/2$ is given by $a_n=1/2$ trivially -- try an ansatz of the form $a_n=k$ and thus we get $k=2k-k=1/2$.

Considering the homogeneous case, $2a_n-a_{n-1}=0$, let $a_n=\lambda^n$ hence:$$2\lambda^n-\lambda^{n-1}=0\\2\lambda-1=0\\\lambda=\frac12$$... and so it follows that $a_n=(1/2)^n=1/2^n$ is a solution to our general equation and further so is any scalar multiple (since our equation is linear) i.e. $a_n=C/2^n$. Adding our particular equation to the mix we get a solution of the form $a_n=C/2^n+1/2$. Impose your initial conditions to determine $C$.

• Thanks! I can't believe I have never thought of applying this kind of "differential equations" approach. It seems so obvious now! – A.E Aug 30 '13 at 2:50
• no problem @AEdwards :-p since both solution spaces for differential and difference form vector spaces we find similar approaches work in both cases – obataku Aug 30 '13 at 2:55

Subtract the formula for $a_{n-1}$ from that for $a_n$ $$a_n-a_{n-1}=\frac14-\frac12a_{n-1}$$ Multiply by $2^n$ and bring $a_{n-1}$ from the left to the right $$2^na_n=2^{n-2}+2^{n-1}a_{n-1}$$ Using the formula for the sum of a geometric series, we get $$2^na_n=2^{n-1}+C$$ Plug in $n=1$ to find that $C=-\frac12$. Thus, $$a_n=\frac12-\frac1{2^{n+1}}$$

• It is interesting to note that no matter what $a_1$ is, this sequence will always tend to $\frac12$. – robjohn Nov 29 '15 at 10:44

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

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