Grade 12 1997 Problem 3

Dana je funkcija $f$ definirana na pozitivnim cijelim brojevima, koja ima ova svojstva $$f(1) = 1, \quad f(2) = 2,$$ $$f(n + 2) = f(n + 2 - f(n + 1)) + f(n + 1 - f(n)), \quad (n \geq 1).$$

(a) Pokažite da je $f(n + 1) - f(n) \in \{0, 1\}$ za svaki $n \geq 1$.

(b) Ako je $f(n)$ neparan, pokažite da je $f(n + 1) = f(n) + 1$.

(c) Za dani prirodan broj $k$ odredite sve vrijednosti $n$ za koje je $$f(n) = 2^{k-1} + 1.$$