What would be a closed-form formula that would determine the ith value of the sequence
1, 3, 11, 43, 171...
where each value is one minus the product of the previous value and 4?
Thanks!
What would be a closed-form formula that would determine the ith value of the sequence
1, 3, 11, 43, 171...
where each value is one minus the product of the previous value and 4?
Thanks!
The following is a simple way of solving the problem. The recurrence has the shape $y_{n+1}=4y_n-1$
It would be nice if the recurrence looked like $u_{n+1}=4u_n$
Then life would be easy. Unfortunately, we have that pesky $-1$ that spoils things!
So let's try for the next best thing. Could we transform our recurrence to something of the shape $y_{n+1}-a=4(y_n-a)$ where $a$ is a constant? Do a bit of arithmetic. We get $y_{n+1}=4y_n-3a$. If we choose $a=1/3$, we can get our recurrence into the desired shape.
Thus we can rewrite our recurrence as
$y_{n+1} -\frac{1}{3}=4\left(y_n -\frac{1}{3}\right)$
Temporarily, let $u_n=y_n-\frac{1}{3}$ for all $n$. Then $u_{n+1}=4u_n$
Now we have to decide whether we start our indices at $0$ or at $1$. Like many mathematicians, I prefer to start at $0$. (Starting at $1$ would not change things very much.)
We have $y_0=1$, so $u_0=1-1/3=2/3$. And because to get the "next" $u$ we multiply the previous $u$ by $4$, we have $u_n=\left(\frac{2}{3}\right)4^n$ But $y_n=u_n+1/3$. It follows that $y_n=\left(\frac{2}{3}\right)4^n +\frac{1}{3}$
Comment: Essentially the same method works for the recurrence $y_{n+1}=cy_n+d$ where $c$ and $d$ are constants, and the idea can be adapted to deal with many other situations.
The general formula is:
$a_n=\frac{2}{3}4^n+\frac{1}{3}$
This can be derived using the trick of converting a non-homogeneous difference equation, which in this case is $a_n=4a_{n-1}-1$, into a homogeneous one of a higher degree, which in this case is $a_{n+1}=5a_n-4a_{n-1}$. This has characteristic polynomial $x^2-5x+4=(x-4)(x-1)$, and therefore $a_n=\alpha 4^n+\beta 1^n$ for some $\alpha, \beta$. Solving the system $1=a_0=\alpha+\beta$ $3=a_1=4\alpha+\beta$ gives $\alpha=\frac{2}{3}$ and $\beta=\frac{1}{3}$.
The OEIS gives the closed form formula of this sequence to be $ \frac{2^{(2n+1)} + 1}{3}. $