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 4 of 6: Locate the maximum

Previous step Next step

a_k=f(2^k-1)\quad(k\ge2)

Detailed analysis

For $k=2$ the claim is immediate. Assume it for $k-1$ . For even $n=2t$ in the upper half of $0\le n\le2^k$ , the recurrence gives $f(n)\le2a_{k-1}$ . For odd $n=2t+1$ there, $f(n)\le2^{k-1}-1+2a_{k-1}$ . Both bounds are at most $f(2^k-1)=2^{k-1}-1+2f(2^{k-1}-1)$ , so the maximum is attained at $2^k-1$ .