# 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 :( Jan 29 '17 at 3:33
• On which part is it that you need more detail? 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)$ ? 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. Jan 29 '17 at 3:45
• Because if it were, $f(k)$ would be $b$, not $a$. Jan 29 '17 at 3:51

Just seeing the question, I drew the above diagram. The numbers which have the same functional values are marked in the same color. So it occurred to me that possibly the answer to this question is $$2$$. Now let's see how.

Claim : $$f(n)=\begin{cases} a & \text{if } n \text{ =5k, where k\in \mathbb{N}}\\ b & \text{otherwise} \end{cases}$$

First let us show that $$f(n)=a$$ when $$n=5k$$.

From the diagram we see that $$f(5)=f(10)=f(15)...$$

For the base case i.e. $$k=1$$ we see $$f(5)=a$$ is true. [Assuming the red color corresponds to the value $$a$$].

Assume that $$f(n)=a$$ when $$n=5\lambda, \text{for all \lambda

Case 1: When $$k$$ is even,

then let $$k=2\beta$$, $$f(5\times 2\beta)=f(5\beta)=a$$. [Since $$5\times2\beta$$ is even and $$\beta$$ is less than $$k$$ and from out induction hypothesis, we have $$f(5\beta)=a$$]

Case 2: When $$k$$ is odd,

Then let $$k=2\alpha+1$$. So $$5k=5(2\alpha+1)$$ is odd. Hence

$$f(5(2\alpha+1))=f(5(2\alpha+1)-5)= f(5(2\alpha))$$

But $$5\times 2\alpha$$ is even. So

$$f(5(2\alpha+1))=f(5(2\alpha))=f(5\alpha)=a$$

Since $$\alpha and by induction hypothesis we have $$f(5\alpha)=a$$.

Now let us work with $$f(n)=b, \text{where n=5k+r,and 1\leq r\leq 4}$$

For the base case: $$k=0$$ we see from the diagram $$f(1)=f(2)=f(3)=f(4)=b$$, [assuming the blue color corresponds to value $$b$$.]

Let us assume that our claim is true for all $$n\lt 5k$$.

case 1: when $$k$$ is even.

Let $$k=2\lambda$$. Hence $$n=5(2\lambda)$$ and $$n+1=5(2\lambda)+1$$ and $$n+3=5(2\lambda)+3$$ are odd. Also $$n+2 = 5(2\lambda)+2$$ and $$n+4= 5(2\lambda)+4$$ are even.

So,

$$f(5(2\lambda)+1)=f(5(2\lambda)+1 -5)= f(5(2\lambda-1)+1)$$

From the induction hypothesis, $$f(5(2\lambda-1)+1)=f(b)$$ since $$5(2\lambda-1)+1 \lt 5k$$

so $$f(5(2\lambda)+1)=f(b)$$

Similarly,

$$f(5(2\lambda)+3)=f(5(2\lambda)+3 -5)= f(5(2\lambda-1)+3)$$

From the induction hypothesis, $$f(5(2\lambda-1)+3)=f(b)$$ since $$5(2\lambda-1)+3 \lt 5k$$

so $$f(5(2\lambda)+3)=f(b)$$

Again,

$$f(5(2\lambda)+2)=f(2(5\lambda+1))= f(5\lambda+1)$$

From the induction hypothesis, $$f(5\lambda+1)=f(b)$$ since $$5\lambda+1 \lt 5k$$

so $$f(5(2\lambda)+2)=f(b)$$

Similarly,

$$f(5(2\lambda)+4)=f(2(5\lambda+2))= f(5\lambda+2)$$

From the induction hypothesis, $$f(5\lambda+2)=f(b)$$ since $$5\lambda+2 \lt 5k$$

so $$f(5(2\lambda)+4)=f(b)$$

case 2: when $$k$$ is odd.

Let $$k=2\lambda+1$$. Hence $$n=5(2\lambda+1)$$ and $$n+1=5(2\lambda+1)+1$$ and $$n+3=5(2\lambda+1)+3$$ are even. Also $$n+2=5(2\lambda+1)+2$$ and $$n+4=5(2\lambda+1)+4$$ are odd.

So,

$$f(5(2\lambda+1)+2)=f(5(2\lambda+1)+2 -5)= f(5(2\lambda)+2)$$

From the induction hypothesis, $$f(5(2\lambda)+2)=f(b)$$ since $$5(2\lambda)+2 \lt 5k$$

so $$f(5(2\lambda+1)+2)=f(b)$$

Similarly,

$$f(5(2\lambda+1)+4)=f(5(2\lambda+1)+4 -5)= f(5(2\lambda)+4)$$

From the induction hypothesis, $$f(5(2\lambda)+4)=f(b)$$ since $$5(2\lambda)+4 \lt 5k$$

so $$f(5(2\lambda+1)+4)=f(b)$$

Again,

$$f(5(2\lambda+1)+1)=f(2(5\lambda+3))= f(5\lambda+3)$$

From the induction hypothesis, $$f(5\lambda+3)=f(b)$$ since $$5\lambda+3 \lt 5k$$

so $$f(5(2\lambda+1)+1)=f(b)$$

Similarly,

$$f(5(2\lambda+1)+3)=f(2(5\lambda+4))= f(5\lambda+4)$$

From the induction hypothesis, $$f(5\lambda+4)=f(b)$$ since $$5\lambda+4 \lt 5k$$

so $$f(5(2\lambda+1)+3)=f(b)$$