D'oh. You can do better than f(2)≤7, you can get f(2)≤5. Actually, no, make that f(2)≤3, which means it's either 2 or 3. And f(n)≤2^2^n, still clearly nowhere near strict.
...double d'oh. Now I see how you do the "obvious" induction that I missed before. f(n+1)≤2f(n)+1. Starting with f(0)=0 yields f(n)≤2^n-1. OK. That's a much, much better bound...
Now I probably am going to stop thinking about this, except for maybe trying to see if I can prove f(2)=3...
...double d'oh. Now I see how you do the "obvious" induction that I missed before. f(n+1)≤2f(n)+1. Starting with f(0)=0 yields f(n)≤2^n-1. OK. That's a much, much better bound...
Now I probably am going to stop thinking about this, except for maybe trying to see if I can prove f(2)=3...
