Quote:
|
Originally Posted by 10intheCrunch
I noted that f(11) = f(12) = 2f(4), thought it might be general, so that f(3n-1) = f(3n).
So then I scrolled down as I type this and realized that n > 0 is a check on the system. As a Q to the writer, does this mean that 0 is not in the domain of f? "Nonnegative integers" would indicate that 0 is allowable.
I wrote out a little list of integers and the laws seem to break down at some point, or at least stop agreeing with each other.
|
0 is in the domain of f. The reason I say "n>0" is because when n = 0, the inequality is not true. Otherwise, it is true, but you need to prove this.
f(3*0)=2*f(0) so f(0) = 0.
"f(3n-1) = f(3n)" is not generally true. Try looking at some more values.
The laws do not break down, and in fact this can be proved by strong induction: Base case f(0) = 0, f(1) = 1, f(2) = 2, and inductive step:
If true for all i < k, then we show that f is defined uniquely for k:
k = 0 mod 3 => f(k) = 2f(k/3), and k/3 < k so f(k) is defined uniquely.
k = 1 mod 3 => f(k) = f(k-1) + 1, and k-1 < k so f(k) is defined uniquely.
k = 2 mod 3 => f(k) = f(k-2) + 2, and k-2 < k so f(k) is defined uniquely.
Thus, this completes our inductive step and f(n) is defined uniquely for all nonnegative integers n.