Dgdrxrt

I had a hard time figuring out a formula for this. Is there a trick that could be used?

The formula in the back of the book is $2^lfloor fracn+12rfloor$ for $n > 0$.

Experiment with small values of $n$:
$$
beginarrayllrr
n = 2: & quad f(2) = 2 f(0)\
n = 4: & quad f(4) = 2 f(2) = 2 left( ; 2 f(0) ; right) & = & 2^2 f(0)\
n = 6: & quad f(6) = 2 f(4) = 2 left( ; 2^2 f(0) right) & = & 2^4 f(0)\
endarray
$$
Now for odd $n$:
$$
beginarrayllrr
n = 3: & quad f(3) = 2 f(1)\
n = 5: & quad f(5) = 2 f(3) = ldots \
endarray
$$

To understand the books answer it helps to notice that

If $n = 2k -1$ is odd then $lfloor frac n+12rfloor = lfloor frac 2k2 rfloor = lfloor k rfloor = k$.

And if $n = 2k$ is even then $lfloor fracn+12rfloor = lfloor frac2k+12 rfloor=lfloor k + frac 12 rfloor= k$.

So this formula is:

If $n = 2k -1$, $f(n) = 2^k$. ANd if $n = 2k$ then $f(n) = 2^k$.

But is that the formula?

Well, as $f(0) = 1$ and $f(2) = 2f(0)= 2$ and $f(4) = 2*f(2)=2*2 =2^2$ and we can see by induction that if $f(2k) = 2^k$ then $f(2k+2) = 2*f(2k) = 2*2^k = 2^k+1$ so, yes the formula works for even numbers.

Likewise as $f(1) =2$ and $f(3) = 2f(1)=2*2=2^2$ and if we assume $f(2k-1)=2^k$ then $f(2k+1) = 2*f(2k-1)=2*2^k = 2^k+1$ so by induction the formula works for odd numbers.

And that's that.

(Although I agree with Bernard; I'd use $f(n) = 2^lceil frac n2rceil$. Thats the same thing as

(If $n= 2k$ then $lceil frac n2rceil = lceil krceil = k = lfloor k + frac 12 rfloor = lfloor frac n+12rfloor$

(If $n= 2k-1$ then $lceil frac n2rceil = lceil k-frac 12rceil = k =frac n+12 = lfloor frac n+12rfloor$)

Let $g(n)=f(2n)$. Then $g(n)=2g(n-1)$ from which you can see, by induction, that $g(n)=2^n-1g(1)$. This gives $f(2n)=2^n$. Now verify that $[frac 2n+1 2]=n$ this gives the answer for all even $n$. Now consider $h(n)=g(2n+1)$ and use a similar argument.

Because $f(2) = 2*f(0) = 2*1 = 2 = f(1)$, the value is doomed to only change every two numbers. Now only considering the first value, it can clearly be seen it is of the form $2^n$, as each value is twice the previous. Combining these two pieces of knowledge and using the base cases, the given formula can be found.

I would write it as
$$f(n)=2^lceil frac n2rceil.$$
You can guess calculating the first values of $f(n)$, then prove it by induction.

Note that $lceilfrac n2rceil=m$ leans that
$$m-1 <frac n2le miff 2m-2<nle 2m.$$