$\begingroup$

Having a function $f:\mathbb{N}\rightarrow\mathbb{N}$:

$$f(n)=\left\{ \begin{array}{lcc} n-3 & if & n \geq 1000 \\f(f(n+6)) & if & n < 1000 \end{array} \right\}$$ Calculate the exact value of $f(1)$ by hand.

Is there an easy way to solve it?

$\endgroup$ 8

3 Answers

$\begingroup$

This isn't the most rigorous proof, but it is by hand and gets to the correct answer.

Adopting the notation that $f^n(x) = \underbrace{f(f(\dots(x)\dots))}_{n\text{ times}}$, we have that: \begin{align*} f(1) & = f(f(1+6)) = f^2(7) \\ & = f(f(7)) = f(f^2(13)) = f^3(13) \\ & = f(f^2(13)) = f(f^3(19)) = f^4(19) \end{align*} It seems as though we have the pattern that $f(1) = f^n((n-1)6+1)$ (you'd likely have to prove this with induction, it shouldn't be hard).

So, now we want $(n-1)6+1\geq 1000$, this will happen when $n-1\geq 166\implies n\geq 167$.

Letting $n = 167$, we have that: $f(1) = f^{167}(1000) = f^{\color{red}{166}}(997) = f^{165}(f(997)) = f^{167}(1003) = f^{\color{red}{165}}(995)$ It appears that $f^n(997) = f^{n-1}(997)$ (again, you should likely prove this).
So, this will be equal to $f(997) = f^2(1003) = 997$, as calculated with a computer.

$\endgroup$ $\begingroup$

We have $f(1000)=997$, $f(997)=f(f(1003))=f(1000)=997$, and $f(994)=f(f(1000))=f(997)=997$. Continuing down by induction, we find that $f(1000-3n)=f(f(1000-3(n-2)))=f(997)=997$ for all $n>1$.

$\endgroup$ $\begingroup$

You have $f(1)=f(f(7))$, $f(7)=f(f(13))$ and so on. The numbers $1, 7, 13,... $ form a sequence with general term $a_{n}=6n-5$. So if we want $6n-5\ge 1000$ we need $ n\ge 168$. This gives us for $n=167$, $f(997)=f(f(1003))=f(1000)=997$. Thus $f(991)=f(f(997))=997$ and so on. Therefore $f(1)=997$.

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy