A palindrome is a string whose reversal is identical to the string.

Ch $06$ Sec $1$ Ex $41($a$)-$ Palindromes

How many bit strings of length $n$ are palindromes if $n$ is even and if $n$ is odd?

$($You must provide an answer before moving to the next part.$)$

Multiple Choice

If $n$ is even, $2^{(n+\frac{1}{2})}$; if $n$ is odd, $2^{\frac{n}{2}}$

If $n$ is even, $2^{\frac{n}{2}}$; if $n$ is odd, $2^{\frac{n+1}{2}}$

If $n$ is even, $2^{\frac{n}{2}}$; if $n$ is odd, $2^{2n+1}$

$$ If $n$ is even, $2^{2n+1}$; if $n$ is odd, $2^{\frac{n+1}{2}}$