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