Iterated sequence - general formula

Question

I have a question regarding writing a general formula for an iterated sequence of variables.

Say we have $$a_0=1$$ $$a_1=\frac{3}{2}a_0$$ $$a_2=\frac{3}{2}a_1-\frac{1}{2}a_0$$ $$a_3=\frac{3}{2}a_2-\frac{1}{2}a_1$$ So in general we have $a_i=\frac{3}{2}a_{i-1}-\frac{1}{2}a_{i-2}$. The solution this this iterated sequence is $a_i=2-2^{-i}$. What method should one use to come up with this solution? ?

Thanks in advance.

Answer 1

A recurrence relation of the form,

$$c_pa_{n+p}+c_{p-1}a_{n+p-1}+....{c_0}a_{n}+....+c_{-s}a_{n-s}=0$$

Is called a homogenous linear recurrence relation.

---

In your case we have,

$$2a_{n}-3a_{n-1}+1a_{n-2}=0$$

---

Something like,

$$a_{n+1}=2a_{n}$$

Is also a homogeneous recurrence as it can be rearranged to look like one. Furthermore, from here we see a good guess to a solution of a homogenous linear recurrence is $a_{n}=r^n$.

Our method to solve linear recurrences is always to guess $a_{n}=r^n$, because as we will see this will lead to a solution where our only job is to find the roots of a polynomial.

In your case we guess $a_n=r^n$ and plug that guess in to get,

$$2r^{n}-3r^{n-1}+r^{n-2}=0$$

At this point we disregard the trivial solution $r=0$, and divide both sides by $r^{n-2}$, the lowest degree.

$$2r^2-3r+1=0$$

Notice then to get a solution we may just take $r$ that solves the above characteristic equation, as the steps are invertible.

$$(2r-1)(r-1)=0$$

$$r=\frac{1}{2},1$$

We see that both $a_n=\left(\frac{1}{2} \right)^n$ and $a_n=1^n=1$ solves that above recurrence.

---

As it turns out, if $a_n=f(n)$ is a solution then $a_n=cf(n)$ is also a solution. I'll prove it for your specific polynomial and let you prove it for the more general case.

Let $a_n=f(n)$ be a solution, then $2f(n)-3f(n-1)+f(n-2)=0$ and thus $2cf(n)-3cf(n-1)+cf(n-2)=0$. Make the conjecture that another possible solution is, $a_n=cf(n)$ and see that indeed we also have $2a_{n}-3a_{n-1}+a_{n-2}=0$.

It also turns out, if $a_n=f(n)$ is a particular solution and $a_n=g(n)$ is another particular solution, then $a_{n}=f(n)+g(n)$ is a solution. I leave you with the proof.

From here we find that if $r_1^n,r_2^n,...r_s^n$ are solutions then,

$$a_n=k_1r_1^n+k_2r_2^n+...+k_sr^n$$

Is also solution, and it turns out that this accounts for all possible solutions if the roots of our characteristic equation are distinct.

From initial conditions, one may find the constants $k_1,k_2,...k_s$ one needs to put to guarantee their solution works in the particular case.

---

Hence we find,

$$a_n=k_1(\frac{1}{2})^n+k_2 1^n$$

To be a general solution to the recurrence,

And from the conditions,

$$a_0=1$$

$$a_1=\frac{3}{2}$$

We may deduce, $k_1=-1$ and $k_2=2$ by plugging in $n=0$ and $n=1$ and solving the resulting system of equations.

Answer 2

Starting from your general term

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

substituting value of $a_{n-1}$ in this , it will transform into $$a_{n}=\frac{7}{4}a_{n-2}-\frac{3}{4}a_{n-3}$$

which is also equals to $$a_n=\frac{2^{2+1}-1}{2^2}a_{n-2}-\frac{2^2-1}{2^2}a_{n-3}$$

again substituting the value of $a_{n-2}$ in it , it will transform into (I hope you will be understanding from where I am substituting values, of course from your general terms)$$a_n=\frac{15}{8}a_{n-3}-\frac{7}{8}a_{n-4}$$

which is also equals to$$a_n=\frac{2^4-1}{2^3}a_{n-3}-\frac{2^3-1}{2^3}a_{n-4}$$ conclusion goes to$$a_n=\frac{2^{x+1}-1}{2^x}a_{n-x}-\frac{2^x-1}{2^x}a_{n-(x+1)}$$ put $x=n-1$ and take it from here, you will get your original answer that is $$a_n=2-2^{-n}$$

Answer 3

Here is a formal derivation of your result. The sequence you have found is a generalization of the Fibonacci sequence.

There have been many extensions of the sequence with adjustable (integer) coefficients and different (integer) initial conditions, e.g., $f_n=af_{n-1}+bf_{n-2}$. (You can look up Pell, Jacobsthal, Lucas, Pell-Lucas, and Jacobsthal-Lucas sequences.) Maynard has extended the analysis to $a,b\in\mathbb{R}$, (Ref: Maynard, P. (2008), “Generalised Binet Formulae,” $Applied \ Probability \ Trust$; available at http://ms.appliedprobability.org/data/files/Articles%2040/40-3-2.pdf.)

We have extended Maynard's analysis to include arbitrary $f_0,f_1\in\mathbb{R}$. It is relatively straightforward to show that

$$f_n=\left(f_1-\frac{af_0}{2}\right) \frac{\alpha^n-\beta^n}{\alpha-\beta}+\frac{f_0}{2} (\alpha^n+\beta^n) $$

where $\alpha,\beta=(a\pm\sqrt{a^2+4b})/2$.

The result is written in this form to underscore that it is the sum of a Fibonacci-type and Lucas-type Binet-like terms. It will also reduce to the standard Fibonacci and Lucas sequences for $a=b=1 \ \text{and} \ f_0=0, f_1=1$.

So, specializing to your case, we can say

$$ \begin{align} \alpha,\beta & =\frac{(a\pm\sqrt{a^2+4b})}{2}\\ & =\frac{(\frac{3}{2}\pm\sqrt{\frac{3}{2}^2-2})}{2}\\ & = \frac{1}{2},1 \end{align} $$

Then,

$$ \begin{align} a_n &=\left(\frac{3}{2}-\frac{3}{2}\frac{1}{2}\right) \frac{\frac{1}{2^n}-1}{\frac{1}{2}-1}-\frac{3}{2}\frac{1}{2} \left(\frac{1}{2^n}+1\right)\\ &=\frac{1}{2^n}\left(-\frac{3}{2}+\frac{1}{2} \right)+\left( \frac{3}{2}+\frac{1}{2}\right)\\ &=2-2^{-n} \end{align} $$

This proves the OP's assertion. Moreover, it applies to all such problems.

Disclosure: this post is derived largely from a previous one: Decimal Fibonacci Number?