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 2 of 6: Bound the successive difference

Previous step Next step

f(n+1)-f(n)\le n\quad(n\ge0)

Detailed analysis

Prove by induction that f(n+1)−f(n)≤n. For even n=2t the difference equals t. For odd n=2t+1, the induction hypothesis at t gives 2(f(t+1)−f(t))−t≤t<n.