# Recursion or typo?

#### warpstar

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.

http://imgur.com/rgN69,ly9Qh

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?

#### warpstar

ok i figured out why its x2... 2+2 = 2*2... silly mistake.

What i still dont get is how they ended up with line two?

#### MarkFL

Here's another method:

We are given the inhomogeneous recursion:

$$\displaystyle \text{rec}(n)=\text{rec}(n-1)+2$$ where $$\displaystyle \text{rec}(0)=0$$

Replace $$\displaystyle n$$ with $$\displaystyle n+1$$:

$$\displaystyle \text{rec}(n+1)=\text{rec}(n)+2$$

Using symbolic differencing, we subtract the first form from the second to obtain the homogeneous recursion:

$$\displaystyle \text{rec}(n+1)-2\text{rec}(n)+\text{rec}(n-1)=0$$

The associated auxiliary equation is:

$$\displaystyle r^2-2r+1=0$$

$$\displaystyle (r-1)^2=0$$

Since we have the repeated root of $$\displaystyle r=1$$, the closed form is:

$$\displaystyle \text{rec}(n)=k_0+k_1n$$

We may now use the given initial value to determine the coefficients $$\displaystyle k_i$$:

$$\displaystyle \text{rec}(0)=k_0=0$$

$$\displaystyle \text{rec}(1)=k_1=2$$

Hence, the closed form is:

$$\displaystyle \text{rec}(n)=2n$$

#### HallsofIvy

Math Team
warpstar said:
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.

http://imgur.com/rgN69,ly9Qh

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?
They don't, that's not what they wrote. The left side is rec(n), not rec(n-1).

Just replacing n, in the first equation, by n-1, rec(n-1)= rec(n-2)+ 2. So replacing rec(n-1), in the first equation, by that, rec(n)= (rec(n-2)+ 2)+ 2= rec(n-2)+ 4. And, of course, 2+ 2= 4= 2 X 2.