Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
add comment

3 Answers 3

up vote 5 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
    
Thank you Zev! A really clean formulation. Is there a methodology you used? –  Rio May 19 '11 at 9:14
    
@Rio: I've added an explanation of the method. This is the same process as the wikipedia article uses to solve the recurrence $a_n=a_{n-1}+1$. –  Zev Chonoles May 19 '11 at 9:17
add comment

The OEIS gives the closed form formula of this sequence to be $$ \frac{2^{(2n+1)} + 1}{3}. $$

share|improve this answer
    
Thank you for the quick response! –  Rio May 19 '11 at 9:14
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.