Problem 1 - Recursive Functions

For a non-negative integer $n$, define $f(n)$ as follows:

$$f(n) = \begin{tabular}{ll} $n+99$ & if $0 \leq n < 101$ \\ $f(f(n-100))$ & otherwise \end{tabular}$$

Prove that $f(n)=199$ under each of the following conditions:

1.

$n=101$,

2.

$101 < n \leq 200$,

3.

$200 < n$.

1.

$f(101) = f(f(101 - 100)) = f(f(1)) = f(100) = 199$

2.

Let assume that $n=102$. Then:

$f(102) = f(f(102-100)) = f(f(2)) = f(101) = 199$

Let assume that $f(k)=199$ for some $k$ such that $101 \leq k < n \leq 200$. Since $n-100 \leq 100$, we have:

$f(n) = f(f(n-100)) = f(n-1)$

which is equal to 199 by the inductive hypothesis.

3.

$f(201) = f(f(201 - 100)) = f(f(101)) = f(199) = 199$

because we saw that $\forall n \in [101,200], f(n)=199$, and in particular, 199 is a fixed point of $f$.

$\forall n > 200, \exists k \in \mathbb{N}$ such that:

$f(n) = f(f(\dots f( n - 100k)\dots)) = f^{k+1}(n - 100k)$

with $n-100k \in [101,200]$. Therefore $\forall n > 200, f(n)=199$.