1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – oldrinb Aug 30 '13 at 2:25
  • $\begingroup$ Are you allowed to prove your guess via induction? $\endgroup$ – Adriano Aug 30 '13 at 2:37
  • $\begingroup$ You can use this technique. $\endgroup$ – Mhenni Benghorbal Aug 30 '13 at 4:33
2
$\begingroup$

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

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

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

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

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.