1

What is wrong with these attempts at defining a recursive function?

(i) $f(0) = 0, f(1) = 1, f(2) = 1, f(3) = 3, f(n) = f(n - 1) + f(n - 2)$ $\quad$$for \ n \ge 2$

(ii) $f(0) = 0, f(n) = f(n - 1) + f(n - 2)$ $\quad$$for \ n \ge 2$

jhg
  • 77
  • 1
    For (i) look more closely at what happens for $n=2,$. For (ii) at $n=1$. – dxiv May 24 '17 at 23:32
  • 1
    In the first one, $f(1)+f(2)\ne f(3)$, breaking the function rule. In the second, the first term must also be given, because in order to find the next term, two terms before it must be known. – Franklin Pezzuti Dyer May 24 '17 at 23:32

2 Answers2

1

i

$f(n) \neq f(n-1) + f(n-2)$ for $n \geq 2$ because $f(3) = 3$ and $f(2) + f(1) = 2$

ii

$f(1)$ is not defined, which is needed to define $f(2)$, which is need to define $f(3)$, ... etc.

Manuel Guillen
  • 2,703
  • for ii. if it was for n greater or equal to 1. would it still be wrong? why? – studymaths May 25 '17 at 03:25
  • The recursion defines a term using the two terms before it. So you need two terms to generate the sequence of terms. For your specific question, how would you find the value of $f(1)$ – Manuel Guillen May 26 '17 at 05:38
1

For $i) $, $f (3) $ must be $=2$

For $ii) $, you need $f (1) $ to compute $f (2 ) $.

hamam_Abdallah
  • 62,951