Some Very Interesting Math Challenges

[Grommit]

1) f is a function from the nonnegative integers to themselves.
For all nonnegative integers n, f satisfies:
f(3n) = 2f(n)
f(3n+1) = f(3n) + 1
f(3n+2) = f(3n) + 2
Prove that f(3n) >= f(2n) > f(n) for n>0.
And yes, the second inequality is STRICT.

2) For positive, real, a, b, with a != b, prove that:
(a+b)/2 > (1/e)*b^(b/(b-a))*a^(a/(a-b)) > (b-a)/(ln b - ln a).

3) S_n = a^n + b^n + c^n. Show that S_n is a rational polynomial in S_1, S_2, S_3, for all integers n>0.

[10intheCrunch]

OK I tried to do some of the first one, and I didn't get around to an actual proof yet, but as it's late and I'm really tired I'll try and post what I found out.

First thing I realized when iterating the function through itself was that f(3^m * n) = 2^mf(n) where m is any nonnegative interger. That kinda helps down the road.

I started out just by listing some function values, 6-->12. I called f(3)=x, so f(4)=x+1, f(5)=x+2. f(6) I called y, so f(7)=y+1, f(9)=y+2. f(9)=2x, f(10)=2x+1, f(11)=2x+2 and f(12)=2x+2. I noted that f(11) = f(12) = 2f(4), thought it might be general, so that f(3n-1) = f(3n).

About this time I wanted to link up x and y so I could compare them directly, and the magic of zero jumped out and smacked me in the head (couldn't believe I hadn't thought of it first). f(0) = z, f(1) = z+1 = x/2 (from f(3)), f(2) = y/2 (from f(6)). So, x/2 + 1 = y/2 => x + 2 = y. This checks out my f(3n-1_ = f(3n) as f(6) = y = x + 2 = f(5). However, it fails at f(17) = 2x + 6 != f(18) = 2y = 2x + 4.

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.

I think I might have gotten in over my head here. I'll try again tomorrow...nice hard problem (at least for those of us who suck at proofs...).

[Grommit]

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.