HOW do you refactor a recursive function into a single equation

Question

I have an initial equation which is very simple:

answer1 = 0*2+2

But it is recursive such that:

answer2 = answer1*2+2
answer3 = answer2*2+2
answer4 = answer3*2+2

How would I go about writing that as a single equation so I can determine what Answer 6 is without going through answers 1-5 first?

answer1 = 2
answer2 = 6
answer3 = 14
answer4 = 30
answer5 = 62
answer6 = 126

Answer 1

One way to solve this is to consider the following: If we write answer1 as $a_1$ and answer2 as $a_2$ and so on, one can re-express your formula as: $$a_{n+1}=2a_n+2.$$ This just tells us how to get the next answer ($a_{n+1}$) in terms of the previous one ($a_n$). The standard trick to finding a closed form for such a linear recurrence relation is to write something like $$a_{n+1}=2(a_n+2)-2$$ the important thing here is that to get the next number, we add two, then multiply, then subtract two. However, if we chain this process on itself a few times, for instance to get $a_{n+3}$ in terms of $a_n$, then the process looks like:

• Add two to $a_n$.
• Double it.
• Subtract two.
• Add two.
• Double it.
• Subtract two.
• Add two.
• Double it.
• Subtract two.

but we can cancel the consecutive steps of "subtract two" then "add two" since they do nothing together (and I've crossed them out above). Removing them gives:

• Add two to $a_n$.
• Double it.
• Double it.
• Double it.
• Subtract two.

Here, we've got three steps of doubling, but if we wanted to advance $k$ steps, we'd need $k$ steps of doubling. Meaning that, since doubling $k$ times is the same as multiplying by $2^k$, we may write: $$a_{n+k}=2^k(a_n+2)-2.$$ In particular, with your sequence, $$a_n=2^n(a_0+2)-2=2^n\cdot 2 - 2 = 2^{n+1}-2$$

---

Now, looking back at what we did, we can generalize a bit. Notice that essentially, our goal is to write the equation in the form: $$a_{n+1}=m(a_n+c)-c$$ since we want the adding $c$ and subtracting $c$ to cancel "around" the multiplication. In our case, we essentially wanted to find $m$ and $c$ such that the desired form equalled the given form - that is: $$m(a_n+c)-c=2a_n+2$$ Clearly, $m=2$ for this to happen, since we need to match the coefficient of $a_n$. Thus we want to find a $c$ satisfying: $$2(a_n+c)-c=2a_n+2$$ distributing the $2$ gives $$2a_n+2c-c=2a_n+2$$ and canceling some terms gives $$c=2$$ which is where we got that magic number from.

Another way to look at this is that $-2$ is the so-called "fixed point" of the form $2a_n+2$ - that is, if we plug in $-2$ to this formula for $a_n$, we get out $-2$. Since the fixed point doesn't move, it's advantageous to measure everything with respect to the fix point - when we apply the expression $2a_n+2$, everything gets twice as far from the fixed point! So, basically, we first shift $-2$ to $0$ by adding $2$, then we double the distances from the fixed point, then we shift everything back by subtracting $2$. In general, in the form given before, $-c$ will be the fixed point.

---

Sidenote: This pattern of chaining together a pattern of:

• Do something.
• Do something else.
• Undo the first thing.

is fairly common in mathematics since, if we understand "Do something else" pretty well, now we understand this whole 3-step process too.

Answer 2

You have $a_0=0$ and $a_{n+1}=2a_n+2$.

Let $b_n=a_n+2$. Then $b_{n+1}=2b_n$ and so $b_n=2^n b_0 = 2^{n+1}$.

This gives $a_n=2^{n+1}-2=2(2^{n}-1)$.