# Recursive function equals xmod3 for all x in N

by ama03630
Tags: gametheory, induction, recursion
 P: 54 I'm not bothering to show the base cases as they are easy. I'm leaving out some detail here and just giving a proof sketch, but the general approach is as follows: Strengthen the induction hypothesis slightly by claiming that $f(y) \in \{0,1,2\}$ in addition to $f(y) \equiv y \pmod 3$. The key observation is that among, $$x-2^0,x-2^1,x-2^2,\ldots$$ no elements are congruent to $x$ modulo 3, but the first two represents the other two residue classes modulo 3. This means that if $x=3k+a$ where $a\in\{0,1,2\}$ and we assume that the hypothesis holds for all natural numbers less than x, then f(x-2^i) is never a, which means, $$a \in \mathbb{N} \setminus \bigcup_{i=0}^{\left\lfloor \log_2(x)\right\rfloor} \{f\left(x-2^i\right)\}$$ For x > 1 we have $\{f(x-2^0),f(x-2^1),a\}=\{0,1,2\}$ by our previous comments. This shows a is actually the minimum when x >1. So if you prove the theorem for x=0 and x =1, then you can inductively show f(3k+a)=a.