Recursion or typo?

• Jun 12th 2012, 04:40 PM
warpstar
Recursion or typo?
Hi there, new user here. would appreciate it alot if someone can help me out with this problem.

I am looking at the solution and I cannot seem to figure out how they are going line by line.

imgur: the simple image sharer

see above, can someone please explain how they went from

rec(n) = rec(n-1) + 2
rec(n-1) = (rec(n - 2) + 2) + 2 = rec(n - 2) + 2 X 2 <--- how is it times 2?
• Jun 12th 2012, 05:35 PM
Reckoner
Re: Recursion or typo?
Quote:

Originally Posted by warpstar
rec(n) = rec(n-1) + 2
rec(n-1) = (rec(n - 2) + 2) + 2 = rec(n - 2) + 2 X 2 <--- how is it times 2?

Well, you've made a typo in your post. That second line should be $\displaystyle \mathrm{rec}(n),$ not $\displaystyle \mathrm{rec}(n-1).$ I don't see anything wrong with the text in the image however.

To answer your question, you should know that $\displaystyle 2 + 2 = 2\cdot2$ and that $\displaystyle 2 + 2\cdot2 = 2 + 2 + 2 = 3\cdot2.$ You're adding an extra 2 each time.

In general, $\displaystyle a + a = 2a$ and $\displaystyle \overbrace{a+a+a+a+\cdots+a}^{n\ \mathrm{terms}} = na.$ This is simple arithmetic.
• Jun 12th 2012, 05:47 PM
warpstar
Re: Recursion or typo?
Thanks, I feel like an idiot.

But can you explain what they did on line two? I thought line 2 was rec(n-1) since they were using recursion and inputing n-1 into the previous eq. ?
• Jun 12th 2012, 05:58 PM
Reckoner
Re: Recursion or typo?
Quote:

Originally Posted by warpstar
Thanks, I feel like an idiot.

But can you explain what they did on line two? I thought line 2 was rec(n-1) since they were using recursion and inputing n-1 into the previous eq. ?

They substituted $\displaystyle \mathrm{rec}(n-1)=\mathrm{rec}(n-2)+2$. So we have

$\displaystyle \mathrm{rec}(n) = \mathrm{rec}(n-1)+2 = \left(\mathrm{rec}(n-2)+2\right)+2$

$\displaystyle =\left(\left(\mathrm{rec}(n-3)+2\right)+2\right)+2$

and so on.