# How do get combination sequence formula?

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

-
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

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

-
Thank you for the quick response! – Rio May 19 '11 at 9:14