# Finding recursive function Range

A function $f: \Bbb{N^+} \rightarrow \Bbb{N^+}$ , defined on the set of positive integers $\Bbb{N^+}$,satisfies the following properties: $$f(n)=\begin{cases} f(n/2) & \text{if } n \text{ is even}\\ f(n+5) & \text{if } n \text{ is odd} \end{cases}$$ Let $R=\{ i \mid \exists{j} : f(j)=i \}$ be the set of distinct values that $f$ takes. The maximum possible size of $R$ is ___________.

Answer of this question is $2$, and solution goes like this:-
every multiple of $5$ has same value, and every other number has same value.

I want to proof it, by NOT using examples, but some real mathematical proof, that can show us that indeed this is true.

Thanks.

Suppose that $f(1) = a$ and $f(5) = b$. It is clear that $$f(5n) = b$$ for all $n$. We'll prove by induction that for all $n \ne 5k$, $f(n) = a$. First note that $$f(2) = f(\frac{2}{2}) = f(1) = a,$$ $$f(3) = f(3+5) = f(8) = f(4) = f(2) = a,$$ $$f(4) = f(2) = a.$$ Now suppose $n = 5k + r$, where $0 < r < 5$, and for all $m<n$ which are not divisible by $5$, $f(m) = a$.

If $n$ is odd, $f(n) = f(n-5)$, and by induction hypothesis, $f(n-5) = a$, so we get $$f(n) = a.$$

If $n$ is even, $f(n) = f(n/2)$, and by induction hypothesis, $f(n/2) = a$, so we get $$f(n) = a.$$

Note that here $\frac{n}{2}$ isn't divisible by $5$.

• Excellent work :) Any other method without induction ? And can u plz make it more illustrative as i am not getting it much :( – user3699192 Jan 29 '17 at 3:33
• On which part is it that you need more detail? – SSepehr Jan 29 '17 at 3:35
• Last part plz, induction hypothesis part. Plz make it in such a way that 10th class student can also get it :) i know that, if we have solution for n=k then we also have solution for n=k+1 (using hypothesis) Your base cases are $f(1)$, $f(2)$, $f(3)$, $f(4)$, right ? and then u said that we have solution for $f(n-5)$ and by hyposthesis we are finiding $f(n)$ ? – user3699192 Jan 29 '17 at 3:39
• Yes, $f(1)$, $f(2)$, $f(3)$, $f(4)$ are the base cases, and I'm assuming the hypothesis for all $k<n$, not just $n-1$, so it covers $n-5$ and $n/2$. This is called "strong induction", which is basically equivalent to the usual induction you mentioned. – SSepehr Jan 29 '17 at 3:45
• Because if it were, $f(k)$ would be $b$, not $a$. – SSepehr Jan 29 '17 at 3:51