Register to reply 
Recursive function equals xmod3 for all x in N 
Share this thread: 
#1
Nov809, 01:53 PM

P: 2

I have a suspicion that if f(0)=0, and f(x)=min(N\Uf(x2^i)) where i runs from 0 to i=floor(ln(x)/ln(2)), then f(x)=xmod3 for all natural numbers, x. Can anyone help me prove this inductively?



#2
Nov809, 04:29 PM

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 [itex]f(y) \in \{0,1,2\}[/itex] in addition to [itex]f(y) \equiv y \pmod 3[/itex]. The key observation is that among, [tex]x2^0,x2^1,x2^2,\ldots[/tex] no elements are congruent to [itex]x[/itex] modulo 3, but the first two represents the other two residue classes modulo 3. This means that if [itex]x=3k+a[/itex] where [itex]a\in\{0,1,2\}[/itex] and we assume that the hypothesis holds for all natural numbers less than x, then f(x2^i) is never a, which means, [tex]a \in \mathbb{N} \setminus \bigcup_{i=0}^{\left\lfloor \log_2(x)\right\rfloor} \{f\left(x2^i\right)\}[/tex] For x > 1 we have [itex]\{f(x2^0),f(x2^1),a\}=\{0,1,2\}[/itex] 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. 


#3
Nov809, 08:37 PM

P: 2

It took me a little while, but I understand this now. Thank you very much for your help. Now, I claim f(x)= min(N\Uf(xp)) where p is 1 or a prime less than or equal to x. Then, f(x)=xmod4. Do you think I could use a similar style of an inductive proof to prove this?



Register to reply 
Related Discussions  
If integral equals zero, then function equals zero  Calculus & Beyond Homework  17  
Recursive function  Calculus & Beyond Homework  1  
Even summation with recursive function in c++  Programming & Computer Science  1  
Simplifying a recursive function  Calculus & Beyond Homework  10  
Recursive Function  Computing & Technology  4 