Recursion or typo?

Jun 2012
2
0
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?
 
Jun 2012
2
0
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?
 
Jul 2010
12,211
522
St. Augustine, FL., U.S.A.'s oldest city
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
Sep 2007
2,409
6
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.