Not Deducing a Closed Form for Recurrence Relation Correctly

Question

Here is a recurrence relation

$$a_1 = 2$$ $$a_{n+1} = \frac{1}{2}(a_n + 6)$$

where $n \in \mathbb{N}$.

For hiccups and giggles, I wanted to determine a closed form for the recurrence relation. After several enumerations, the relation is clearly a finite geometric series, so I proceed as follows

$$a_{n+1} = \frac{1}{2}(a_n + 6) = \frac{1}{2^2}a_{n-1} + \frac{6}{2^2} + \frac{6}{2}$$

$$= \frac{1}{2^3} a_{n-2} + \frac{6}{2^3} + \frac{6}{2^2} + \frac{6}{2}$$

$$\vdots$$ $$= \Big(\frac{1}{2}\Big)^n a_1 + 6 \cdot \sum_{k=1}^n \Big(\frac{1}{2}\Big)^k$$ $$= \Big(\frac{1}{2}\Big)^{n-1} + 6 \cdot \frac{\big(\frac{1}{2}\big)^{n+1} - \frac{1}{2}}{\frac{1}{2}-1}$$ $$= 2\Big(\frac{1}{2}\Big)^n + 6 - 6 \Big(\frac{1}{2}\Big)^n$$ $$= 6 - 4\Big(\frac{1}{2}\Big)^n$$

where I am using the geometric series $a \cdot \sum_{k=m}^n r^k = a \cdot \frac{r^{n+1}-r^m}{r-1}$ where $m,n \in \mathbb{N}$ and $m < n$.

But it is easy to see that this "closed form" does not work when $n = 1$, so any assistance is appreciated.

Answer 1

Let $a_m=b_m+cm+d$

$$6=2a_{n+1}-a_n=2\{b_{m+1}+c(n+1)+d\}-(b_n+cn+d)=2b_{n+1}-b_n+cn+2c+d$$

Set $c=0,2c+d=6\iff d=6\implies a_m=b_m+6\implies b_1=a_1-6=-5$

$$b_{n+1}=\dfrac{b_n}2=\dfrac{b_{n-r}}{2^r}=\cdots=\dfrac{b_1}{2^{n-1}}=\cdots$$

Can you take it from here?

Answer 2

Here's a method that works for all kinds of linear recurrences , this means those of the form $a_{n+1}=ba_n+c$ except those where $b=1$ which are simply arithmetic series and are easy to deal with .

This is called the fixed point method :

Replace every appearance of a term from the sequence with $x$ and then solve the equation :

$$x=\frac{1}{2}(x+6)$$

thus $x=6$ is the fixed point .

Consider also the recurrence relation and then subtract them so :

$$a_{n+1}-x=\frac{1}{2}(a_n+6)-\frac{1}{2}(x+6)=\frac{1}{2}(a_n-x)$$

So it makes sense to denote $b_n=a_n-x$ :

$b_{n+1}=\frac{1}{2}b_n$ with $b_1=a_1-x=2-6=-4$

This is a simple geometric series and thus :

$$b_n=-4\left (\frac{1}{2} \right )^{n-1} $$and then :

$$a_n=6-4\left (\frac{1}{2} \right )^{n-1} $$

This method doesn't work for $b=1$ because this recurrence hasn't a fixed point :

$$x=x+c$$ is generally false (except when $c=0$ and the recurrence is $a_{n+1}=a_n$ ..)

I like this approach because it involves nearly no calculations at all .

Answer 3

Here is another general method for solving recurrences of the form $x_{n+1}=ax_n+b$. Let $y_n=x_n+c$, where $c$ is a constant yet to be determined. Then $x_n=y_n-c$, and the recurrence can be rewritten

$$y_{n+1}-c=a(y_n-c)+b=ay_n-ac+b\;,$$

or

$$y_{n+1}=ay_n-(a-1)c+b\;.$$

We now choose $c$ so as to reduce this to the simple exponential recurrence $y_{n+1}=ay_n$:

$$c=\frac{b}{a-1}\;.$$

For this choice of $c$ we clearly have $y_n=a^ny_0$. We know that $y_n=x_n+c=x_n+\dfrac{b}{a-1}$, so

$$x_n=y_n-c=a^nx_0-c=a^n\left(x_0+\frac{b}{a-1}\right)-\frac{b}{a-1}\;.$$

Of course this fails if $a=1$, but in that case the original recurrence is $x_{n+1}=x_n+b$, which obviously has the closed form $x_n=bn+x_0$.