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 1 of 6: Find L

Previous step Next step

f(2k+1)-f(2k)=k\quad(k>0)

Detailed analysis

From the defining rules, f(2k+1)−f(2k)=k. Thus every positive even index belongs to L. Also f(4k+1)=2k+4f(k)=f(4k+2), while f(0)=f(1)=0, so 0 and every number congruent to 1 modulo 4 belong to E.