Let f:N→N be a strictly increasing function such that f(1)=1 and f(2n)f(2n+1)=9f(n)2+3f(n) for all n∈N. Compute f(137).
A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.
Solution
Plugging in n=1 gives f(2)f(3)=12, therefore (f(2),f(3))=(2,6) or (3,4). However, the former implies f(4)f(5)≥(6+1)(6+2)>42=9⋅22+3⋅2 which is impossible; therefore f(2)=3 and f(3)=4. We now show by induction with step size 2 that f(2n)=3f(n) and f(2n+1)=3f(n)+1 for all n; the base case n=1 has already been proven. Assume the statement is true for n<2k. Applying the given and the inductive hypothesis, we have f(4k)f(4k+1)f(4k+2)f(4k+3)=(3f(2k))(3f(2k)+1)=(9f(k))(9f(k)+1)=(3f(2k+1))(3f(2k+1)+1)=(9f(k)+3)(9f(k)+4) Let x=f(4k+1). Since f is strictly increasing, this implies x≥f(4k)f(4k+1)>9f(k) and x≤f(4k+2)f(4k+3)−1<9f(k)+3. So x=9f(k)+1 or x=9f(k)+2. Since 9f(k)+2 does not divide 9f(k)(9f(k)+1), we must have f(4k+1)=x=9f(k)+1 and f(4k)=9f(k). A similar argument shows that f(4k+2)=9f(k)+3 and f(4k+3)=9f(k)+4, and this completes the inductive step. Now it is a straightforward induction to show that f is the function that takes a number's binary digits and treats it as base 3. Since 137=100010012 in binary, f(137)=100010013=37+33+1=2215.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: Omni-MATH,
licensed Apache-2.0.
Statement and solution reproduced as published; topic and difficulty added by this site.