Question

@Mehek14
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 5 12 29 70


Which recursive function best represents the values shown in the table? (4 points)


f(1) = 1, f(2) = 2, f(n) = 2f(n -1) f(n - 2); n > 2
f(1) = 1, f(2) = 2, f(n) = f(n -3) + f(n - 2); n > 2
f(1) = 1, f(2) = 2, f(n) = 2f(n -1) + f(n - 2); n > 2
f(1) = 1, f(2) = 2, f(n) = f(n -3) f(n - 2); n > 2

Answer 1

Let's focus on choice A for now

f(1) = 1, f(2) = 2, f(n) = 2f(n -1) f(n - 2); n > 2

specifically, I want to focus on the last part where it says `f(n) = 2f(n -1) f(n - 2); n > 2`

Let's plug in n = 3 and see what happens

\[\Large f(n) = 2f(n -1) f(n - 2)\]
\[\Large f({\color{red}{n}}) = 2f({\color{red}{n}} -1) f({\color{red}{n}} - 2)\]
\[\Large f({\color{red}{3}}) = 2f({\color{red}{3}} -1) f({\color{red}{3}} - 2)\]
\[\Large f(3) = 2*f(2)*f(1)\]
\[\Large f(3) = 2*2*1\]
\[\Large f(3) = 4\]
Hopefully you see how this all works?