Finding a formula for $f(n)$: $f(0)=1, f(1)=2, f(n)=2f(n-2)$ for $n \ge 2$

Question

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 \frac{n+1}{2}\rfloor}$ for $n > 0$.

Answer 1

Experiment with small values of $n$: $$ \begin{array}{llrr} 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)\\ \end{array} $$ Now for odd $n$: $$ \begin{array}{llrr} n = 3: & \quad f(3) = 2 f(1)\\ n = 5: & \quad f(5) = 2 f(3) = \ldots \\ \end{array} $$

Answer 2

Let $g(n)=f(2n)$. Then $g(n)=2g(n-1)$ from which you can see, by induction, that $g(n)=2^{n-1}g(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.

Answer 3

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.

Answer 4

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

Note that $\lceil\frac n2\rceil=m$ leans that $$m-1 <\frac n2\le m\iff 2m-2<n\le 2m.$$

Answer 5

To understand the books answer it helps to notice that

If $n = 2k -1$ is odd then $\lfloor \frac {n+1}2\rfloor = \lfloor \frac {2k}2 \rfloor = \lfloor k \rfloor = k$.

And if $n = 2k$ is even then $\lfloor \frac{n+1}2\rfloor = \lfloor \frac{2k+1}2 \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 n2\rceil}$. Thats the same thing as

(If $n= 2k$ then $\lceil \frac n2\rceil = \lceil k\rceil = k = \lfloor k + \frac 12 \rfloor = \lfloor \frac {n+1}2\rfloor$

(If $n= 2k-1$ then $\lceil \frac n2\rceil = \lceil k-\frac 12\rceil = k =\frac {n+1}2 = \lfloor \frac {n+1}2\rfloor$)