recursive function equals xmod3 for all x in N


by ama03630
Tags: gametheory, induction, recursion
ama03630
ama03630 is offline
#1
Nov8-09, 01:53 PM
P: 2
I have a suspicion that if f(0)=0, and f(x)=min(N\Uf(x-2^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?
Phys.Org News Partner Mathematics news on Phys.org
Researchers help Boston Marathon organizers plan for 2014 race
'Math detective' analyzes odds for suspicious lottery wins
Pseudo-mathematics and financial charlatanism
gunch
gunch is offline
#2
Nov8-09, 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]x-2^0,x-2^1,x-2^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(x-2^i) is never a, which means,
[tex]a \in \mathbb{N} \setminus \bigcup_{i=0}^{\left\lfloor \log_2(x)\right\rfloor} \{f\left(x-2^i\right)\}[/tex]
For x > 1 we have [itex]\{f(x-2^0),f(x-2^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.
ama03630
ama03630 is offline
#3
Nov8-09, 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(x-p)) 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