Thread: [SOLVED] recursive def. Check my answer please.

Find f(2), f(3), f(4), f(5) if f(n) is defined recursively by f(0)= 0, f(1) = 1, f(n+1) = f(n)+2f(n-1)+1 for n = 1, 2, ....

f(2) = f(1) +2(1-1)+1
f(2) = 2

f(3) = f(2) + 2(2-1)+1
f(3) = 5

f(4) = f(3) + 2(5-1)+1
f(4) = 14

f(5) = f(4) + 2(14-1)+1
f(5) = 41

correct?

Originally Posted by ninobrn99

Find f(2), f(3), f(4), f(5) if f(n) is defined recursively by f(0)= 0, f(1) = 1, f(n+1) = f(n)+2f(n-1)+1 for n = 1, 2, ....

f(2) = f(1) +2(1-1)+1
f(2) = 2

f(3) = f(2) + 2(2-1)+1
f(3) = 5

f(4) = f(3) + 2(5-1)+1
f(4) = 14

f(5) = f(4) + 2(14-1)+1
f(5) = 41

correct?

the formula is f( n + 1 ) = f( n ) + 2*f( n - 1 ) + 1
and you are making mistake because you did:
f( n + 1 ) = f( n ) +2*( n - 1 ) + 1

answers:

f( 2 ) = f( 1 ) + 2*f( 1 - 1 ) + 1 = 1 + 2*0 + 1 = 2

f( 3 ) = f( 2 ) + 2*f( 1 ) + 1 = 2 + 2*1 + 1 = 5

f( 4 ) = f( 3 ) + 2*f( 2 ) + 1 = 5 + 2*2 + 1 = 10

f( 5 ) = f( 4 ) + 2*f( 3 ) + 1 = 10 + 2*5 + 1 = 21

Originally Posted by josipive

the formula is f( n + 1 ) = f( n ) + 2*f( n - 1 ) + 1
and you are making mistake because you did:
f( n + 1 ) = f( n ) +2*( n - 1 ) + 1

answers:

f( 2 ) = f( 1 ) + 2*f( 1 - 1 ) + 1 = 1 + 2*0 + 1 = 2

f( 3 ) = f( 2 ) + 2*f( 1 ) + 1 = 2 + 2*1 + 1 = 5

f( 4 ) = f( 3 ) + 2*f( 2 ) + 1 = 5 + 2*2 + 1 = 10

f( 5 ) = f( 4 ) + 2*f( 3 ) + 1 = 10 + 2*5 + 1 = 21

Thanks for showing me what I was doing wrong! It helped tremendously!