1
$\begingroup$

Find the general term of the following recurrence relation:

$$a_{1} = 2$$

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

I've tried to find the first few terms:

$$a_{1} = 2$$ $$a_{2} = \frac{2.2 - 1}{3} = 1$$ $$a_{3} = \frac{2.1 - 1}{3} = \frac{1}{3}$$ $$a_{4} = -\frac{1}{9}$$ $$a_{5} = -\frac{1}{27}$$

but can't see any pattern, especially considering the first 2 terms.

$\endgroup$
2
$\begingroup$

We have $$ 3a_{n+1}=2a_n-1 \tag{1}$$ and we may try to get rid of the inhomogeneous term $-1$ by a suitable substitution.
For instance, by setting $a_n=b_n-1$, we get $b_1=3$ and $$ 3b_{n+1}=2b_n \tag{2} $$ from which $b_n = 3\cdot\frac{2^{n-1}}{3^{n-1}}$ readily follows. The general term of the original sequence is so: $$ a_n = \color{red}{3\cdot\frac{2^{n-1}}{3^{n-1}}-1}.\tag{3}$$

$\endgroup$
  • $\begingroup$ Thank you for your time and answer! Could you suggest a source for further reading on this topic? $\endgroup$ – Ziezi Sep 15 '16 at 12:25
  • 1
    $\begingroup$ @Ziezi: these slides nms.lu.lv/wp-content/uploads/2016/04/21-linear-recurrences.pdf should be a good starting point. $\endgroup$ – Jack D'Aurizio Sep 15 '16 at 12:32
  • 1
    $\begingroup$ The slides are great! (just to note) The link at the end is broken. $\endgroup$ – Ziezi Sep 15 '16 at 18:43
0
$\begingroup$

Following your (@Jack D'Aurizio) suggestion, here is what I understood:

The given recurrence relation: $3a_{n} = 2a_{n-1} - 1$, with initial conditions: $a_{1} = 2$ is a $1^{st}$ degree linear non-homogeneous recurrence relation.

Solution:

We are searching for solution1 of the form: $a_{n} = b_{n} + h_{n}$ (1), where $h_{n}$ is the sequence satisfying the associated homogeneous recurrence relation and $b_{n}$ is a solution which is similar to $f(n)$.

1.The associated homogeneous recurrence relation is: $3h_{n} = 2h_{n-1}$ and its characteristic equation is: $3r - 2 = 0$ or $ r = \frac{2}{3}$ and the solution is:

$$h_{n} = \alpha_{0} (\frac{2}{3})^{n-1} $$

From the initial conditions: $a_{1} = \alpha_{0} (\frac{2}{3})^{1} = 2$ or $\alpha_{0} = 3$, so the solution of the homogeneous recurrence is:

$$h_{n} = 3 (\frac{2}{3})^{n-1} $$

  1. In our case $b_{n} = -1$ and from (1) we have:

$$a_{n} = 3 (\frac{2}{3})^{n-1} - 1$$


1. $a_{n}$ satisfies both the recurrence relation and the initial conditions.

2. $f(n)$ - function depending only on $n$.

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