Recursion or typo?

Printable View

June 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?
June 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 $\mathrm{rec}(n),$ not $\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 $2 + 2 = 2\cdot2$ and that $2 + 2\cdot2 = 2 + 2 + 2 = 3\cdot2.$ You're adding an extra 2 each time.

In general, $a + a = 2a$ and $\overbrace{a+a+a+a+\cdots+a}^{n\ \mathrm{terms}} = na.$ This is simple arithmetic.
June 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. ?
June 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 $\mathrm{rec}(n-1)=\mathrm{rec}(n-2)+2$ . So we have

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

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

and so on.