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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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
share|cite|improve this question
    
You can simply use WolframAlpha. You'll get $a_n=2\left(2^n-1\right)$ for all $n\ge 0$. – user236182 Jan 7 at 1:40
1  
You can find a general approach on Wikipedia. – A.P. Jan 7 at 1:49
up vote 8 down vote accepted

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.

share|cite|improve this answer
    
Awesome detailed answer to the "How". Could you explain where the -2 came from a tiny bit? (Edit) - Oh, is that (a0) simplified? If so, I don't get where that came from, lol. – Suamere Jan 7 at 2:01
1  
@Suamere I've added a section on where the magic numbers came from. (Hopefully I added something regarding the right -2, since there are a few -2's in there. Notice that we use $a_0=0$ at some point) – Milo Brandt Jan 7 at 2:07
1  
I upvoted you two more times for the detailed answer. Not my fault if StackExchange doesn't count it. Lol. Thanks a lot. – Suamere Jan 7 at 2:10
    
Such answer. Much math. Wow. (kudos!) – mattecapu Jan 7 at 13:27

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

share|cite|improve this answer

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.