2
$\begingroup$

Find all functions $f:\mathbb{Z} \to \mathbb{Z} $ such that$f(0)=1$ and $$f(f(n))=f(f(n+2)+2)=n. \quad \forall n \in \mathbb{Z} $$

My approach: Plugging in some values, it is not hard to see that $f(n)=1-n$ satisfies the given relation. I claim that $ f(k)=1-k $ for some $k \in \mathbb{Z}$.

I just cannot see a way to use the relation and induct on $k$ to prove my hypothesis. Am I missing something obvious? Please help as I am new to functional equations. Also please share some online resources to solve functional equations as I am preparing for Olympiads.

Thank you.

$\endgroup$
  • $\begingroup$ "I claim that $ f(k)=1-k$ for some $k \in \mathbb{Z}$ ": you just said that it holds for all $k$ ! $\endgroup$ – Yves Daoust Feb 12 '18 at 9:25
  • $\begingroup$ @YvesDaoust shouldn't I do that for some k to proceed with my induction hypothesis? $\endgroup$ – alphasquared Feb 12 '18 at 13:20
  • $\begingroup$ You say "it is not hard to see that $f(n)=1−n$ satisfies the given relation", don't you ? $\endgroup$ – Yves Daoust Feb 12 '18 at 13:37
  • $\begingroup$ @YvesDaoust I'm sorry I didn't mean that. i actually meant to point out what i thought the function according to me is, to the viewers of this question. $\endgroup$ – alphasquared Feb 12 '18 at 13:47
5
$\begingroup$

$f(f(n)) = n \ (\forall n \in \mathbb{Z})$ implies $f$ is injective, thus$$ f(f(n)) = f(f(n + 2) + 2) \Longrightarrow f(n) = f(n + 2) + 2. \quad \forall n \in \mathbb{Z} $$ Also$$ 0 = f(f(0)) = f(1), $$ then$$ f(n) = -n + 1 \quad (\forall n \in \mathbb{Z}) $$ can be proved by induction.

$\endgroup$
  • $\begingroup$ How do I proceed with the inductive step? $\endgroup$ – alphasquared Feb 13 '18 at 10:05
  • 1
    $\begingroup$ First using $n = 0, 1$ as base cases to prove for $n \geqslant 0$, then using $n = 0, 1$ as base cases to prove for $n < 0$. $\endgroup$ – Saad Feb 13 '18 at 10:13
  • $\begingroup$ Please check this: suppose that $f(k)=1-k$ for some $k \in \mathbb{Z}$. Then we have $f(k)=f(k+2)+2$ which implies $f(k) > f(k+2)$ which implies $f(k) \geqslant f(k+1)$. But $f(k) = f(k+1)$ implies $0=1$ which is absurd. Therefore $f(k) > f(k+1)$ thus forcing $f(k+1) = -k$. (It can be seen using the relation that $f(k+2)= -1-k$) $\endgroup$ – alphasquared Feb 13 '18 at 10:23
  • $\begingroup$ No need to be so complicated since $f$ has the recurrence relation $f(n + 2) = f(n) - 2$ with initial conditions $f(0) = 1$, $f(1) = 0$ for $n \in \mathbb{N}$. $\endgroup$ – Saad Feb 13 '18 at 10:59
  • $\begingroup$ That $+2$ inside the recurrence function is making it difficult for me to induct on consecutive integers, instead I am ending up inducting on consecutive integers with same parity. $\endgroup$ – alphasquared Feb 13 '18 at 11:04

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.