While preparing for an exam, I came across this question (it was previously asked in the exam):
By taking a few different values of $x$, I noticed a pattern: if $x$ is a multiple of 5, then the function value reduces to $f(5)$, else it always reduces to $f(1)$.
$f(15) = f(20) = f(10) = f(5)$
$f(3) = f(8) = f(4) = f(2) = f(1)$
So, looks like $f$ can take only two values: $f(1)$ and $f(5)$. So, the answer to the above question should be $2$. And it is indeed the correct answer. But how do I go about proving it so that I can be absolutely sure about the answer? (The exam awards negative marks for incorrect answers). I am not even sure where to begin with the proof.
Note: the exam is for computer science graduates and discrete mathematics is one of the subjects.
Best Answer
We want to show that $f(k)$ is either $f(1)$ or $f(5)$ for all $k$. We'll do it by induction.
There is no difficulty doing this for small $k$.
Now, suppose that we have done it up to $k=n-1$. We want to show that it is also true for $k=n$.
Case I: $n$ even. Then $f(n)=f\left(\frac n2\right)$ and, as $\frac n2<n-1$ we can apply the inductive hypothesis to $\frac n2$.
Case II: $n$ odd. Then $f(n)=f(n+5)=f\left( \frac {n+5}2\right)$. For $n≥7$ we have $\frac {n+5}2≤n-1$ so the inductive hypothesis again applies.
And we are done.
To see that it is possible that $f(1)\neq f(5)$, pick any two values $a,b$ and define $$ f(n) = \begin{cases} a & \text{if $n$ is a multiple of 5}\\ \quad \\ b & \text{if $n$ is not a multiple of 5 } \end{cases}$$
It is then easy to show that $f(n)$ satisfies the functional equations ($5\,|\,2n\iff 5\,|\,n$ and $5\,|\,n\iff 5\,|\,n+5$).