Recursively Defined Functions

Question

I am taking a summer class in discrete math and have done very well up till now. I am nervous because I have reviewed the lecture slides and practice problems but I still don't really understand what to do. The problem example I was given is:

Suppose $f$ is defined by:

\begin{align} f(0) &= 0, \\ f(1) &= 1, \\ f(n + 2) &= f(n + 1) + 2\times f(n) \end{align}

Question: Find $f(2), f(3), f(4), f(5), f(6)$

Now I understand that what I am doing is finding the function by plugging in the previous function, but I do not understand the $f(n+2)$. How do I interpret this? Does this mean that for $f(2)$ I plug in the result of $f(1)$ and add $2$ to it? Or do I plug in $0$ since $0+2 = 2$ and I am trying to find $f(2)$?

Answer 1

No. For $f(n+2)$ you first compute $n+2$, then apply $f$ to it.

So, for $n=2$ we want $f(n+2)=f(4)$. In order to compute $f(2)$, we take $n=0$ in the equation to get $f(2)=f(1)+2 f(0)$. Then for $f(3)$, we take $n=1$ in the equation to get $f(3) = f(2)+2f(1)$.

Answer 2

This function is recursively defined as a function of the previous two inputs. So to calculate $f(2)$ you need the values of $f(1)$ and $f(0)$. Following the definition,

$f(2) = f(0 + 2) = f(1) + 2*f(0)$.

An equivalent way of thinking about this recursive function is

$f(k) = f(k-1) + 2*f(k-2),\,\, k>1$