Question

The table below shows the values of f(n) for different values of n:


n 1 2 3 4 5 6
f(n) 1 2 4 16 128 4096


Which recursive function best represents the values shown in the table?

A) f(1) = 1, f(2) = 2, f(n) = f(n -3) + f(n - 2); n > 2
B) f(1) = 1, f(2) = 2, f(n) = f(n -3) f(n - 2); n > 2
C)f(1) =1, f(2) = 2, f(n) = 2f(n -1) + f(n - 2); n > 2
D) f(1) = 1, f(2) = 2, f(n) = 2f(n -1) f(n - 2); n > 2

Answer 1

please help!

Answer 2

@welshfella can you help with this one?

Answer 3

f(1) means the value of function when n = 1
f(2) when n=2 etc

Answer 4

what you need to do is substitute n = 3 into the formulae for f(n) and see if this gives you f(2) - that is a value of 2.

Answer 5

oh, ok i'll do that really quickly

Answer 6

wait:/ i don't have a formula

Answer 7

sorry - i got that wrong - it should give you the value for f(3) which is 4

Answer 8

yeah

Answer 9

ok lets try the last one

Answer 10

alrighty, what happens first

Answer 11

f(n) = 2f(n -1) f(n - 2); n > 2
f(3) = 2*f(2)*f(1) = 2*2*1 = 4

Answer 12

what do you do from there?

Answer 13

thats the one - we hit the right one

Answer 14

f(3) = 4 - which is the value on the table

Answer 15

oh ok

Answer 16

understand?

Answer 17

yeah, so just to be clear it would be D?

Answer 18

yes
we could double check to see if f(4) = 16

f(4) = 2*f(3)*f(2)
= 2 * 4 * 2 = ?

Answer 19

does that = 16?

Answer 20

yes:^)

Answer 21

thats itt the
D is the correct choice

Answer 22

oh i see, okay thank you @welshfella

Answer 23

yw