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 5 of 6: Obtain the recurrence

a_k=2a_{k-1}+2^{k-1}-1

Detailed analysis

Evaluating $f$ at $2^k-1$ gives $a_k=2a_{k-1}+2^{k-1}-1$ . This recurrence holds for $k\ge1$ , with initial values $a_0=a_1=0$ and $a_2=1$ .