The functions f(n) and g(n) are defined for positive integers n as follows: f(n) = 2n + 1, g(n) = 4n. This question is about the set S of positive integers that can be achieved by applying, in some order, a combination of fs and gs to the number 1. For example as gfg(1) = gf(4) = g(9) = 36, and ffgg(1) = ffg(4) = ff(16) = f(33) = 67, then both 36 and 67 are in S.
(i) Write out the binary expansion of 100 (one hundred).
(ii) Show that 100 is in S by describing explicitly a combination of fs and gs that achieves 100.
(iii) Show that 200 is not in S.
(iv) Show that, if n is in S, then there is only one combination of applying fs and gs in order to achieve n. (So, for example, 67 can only be achieved by applying g then g then f then f in that order.)
(v) Let $u_k $ be the number of elements n of S that lie in the range $ 2^k<n < 2^{k+1} $
Show that $$u_{k+2} = u_{k+1} + u_{k}$$ Please help me to anwser (V)