What is wrong with the following definitions of a recursive function?

Question

Can someone please explain what is wrong with these 4 recursive functions?

(a) $f(0)=0, f(1)=1, f(2)=1, f(3)=3, f(n)=f(n-1)+f(n-2)$ for $n \geq 2$

(b) $f(0)=0, f(n)=f(n-1)+f(n-2)$ for $n \geq 2$

(c) $f(0)=0, f(n)=f(n-1)+f(n-2)$ for $n \geq 1$

(d) $f(0)=0, f(n)=f(1 + ⌊n/2⌋)$ for $n \geq 1$

Answer 1

For the first $3$ questions, they are defined in terms of the previous $2$ terms, so for them to work, these two values must be defined, and any further terms must satisfy the formula for the terms before it.

(a) For this one, we check $f(3)$:

\begin{align}f(n)&=f(n-1)+f(n-2)\\ f(3)&=f(3-1)+f(3-2)\\ &=f(2)+f(1)\\ &=1+1\\ &=2\end{align}

This is not equal to the given value for $f(3)$

(b) For this one, we check $f(2)$:

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

However $f(1)$ has not been defined so we can't calculate $f(2)$

(c) For this one, we check $f(1)$:

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

However $f(-1)$ has not been defined so we can't calculate $f(1)$

(d) For this one, we check $f(1)$:

\begin{align}f(n)&=f\left(1+\left\lfloor\frac n2\right\rfloor\right)\\ f(1)&=f\left(1+\left\lfloor\frac 12\right\rfloor\right)\\ &=f(1+0)\\ &=f(1)\end{align}

This is not a recursive formula as $f(1)$ doesn't depend on $f(0)$

Answer 2

Hint:

All the definitions use two preceding values of the function to define $f(n)$ (double recursion). So the function is well defined if these two preceding values are defined and if their value is compatible with the recursive rule.

Check this for your definitions and you can see that this is not true for:

$f(3)$ in the def. a)

$f(2)$ in the def. b)

$f(1)$ in the def. c)

$f(1)$ in the def. d)

Answer 3

Hint:

In all cases, try to evaluate $f(0),f(1),f(2)\cdots$ using all the given information, and detect incoherencies.

E.g. for a) you are given that

$$f(0)=0,f(1)=1,f(2)=1,f(3)=3$$ but also

$$f(2)=f(1)+f(0),f(3)=f(2)+f(1)\ \color{red}?\ ,f(4)=f(3)+f(2),\cdots$$