Problem 4

Consider the function

f:\mathbb N_0\to\mathbb N_0

, where

\mathbb N_0

is the set of all non-negative integers, defined by

f(0)=0

f(2n)=2f(n)

and

f(2n+1)=n+2f(n)

for all

n\ge0

. (a) Determine the three sets

L=\{n\mid f(n)<f(n+1)\}

E=\{n\mid f(n)=f(n+1)\}

, and

G=\{n\mid f(n)>f(n+1)\}

. (b) For each

k\ge0

, find a formula for

a_k=\max\{f(n):0\le n\le2^k\}

in terms of

k

Step 3 of 6: Find G

Previous step Next step

f(4k+4)-f(4k+3)=4\bigl(f(k+1)-f(k)\bigr)-(4k+1)<0

Detailed analysis

Using the recurrence, f(4k+4)−f(4k+3)=4(f(k+1)−f(k))−(4k+1), which is negative by the preceding bound. Hence every index congruent to 3 modulo 4 belongs to G. The three disjoint classes cover all nonnegative integers, so L={2k:k>0}, E={0}∪{4k+1:k≥0}, and G={4k+3:k≥0}.