How many bit strings of length n are palindromes? While reading in a Discrete maths text book, there was this question:

How many bit strings of length n are palindromes?

The answer is:

$2^\frac{n+1}{2}$ for odd and $2^\frac{n}{2}$ for even.

I searched it on the internet and people were saying that first $\frac{n}{2}$ ($\frac{n+1}{2}$ for odd ) can be selected arbitrarily and the next bits has to be determined.
I got the first part but I fail to understand the second. How can a palindrome can be determined by the first part?
Please explain it using an example. Thanks!
 A: If a string is length $n$, then we can write it as either being length $2k+1$ if $n$ is odd, or $2*k$ if $n$ is even, where $k \in \mathbb Z$. 
In either case, the first half of the digits determine the values of the second half of the digits. Indeed, let $$(a_m)_{m=1}^{n}$$ be a string that is a palindrome. Then $a_1 = a_n, a_2 = a_{n-1},\ldots$ If $n$ is odd, then $a_{k+1} = a_{k+1}$ otherwise $a_k = a_{k+1}$. 
Thus, there are $2$ choices for the value of $a_1$, $2$ choices for $a_2$, $\ldots$, and $2$ choices for $a_k$. If $n$ is odd, then there are also two choices for the middle digits $a_{k+1}$. Combining, we see that if $n$ is odd, we have a total of $2^{k+1}$ possible choices; if $n$ is even then we have a total of $2^k$ possible choices. Substituting back for $n$ gives $2^{\frac{n+1}{2}}$ choices for $n$ odd and $2^{\frac{n}{2}}$ for $n$ even.
A: Let $P_{n}$ be the number of palindromes of length n. Then the recursive formula for $P_{n}$ can be given as,
           $P_{n} = 2.P_{n-2}$, with base case $P_{1} =1$ and $P_{2} = 2$,
that can be conversed easily into $P_{n} = 2^{n/2}$, if n is even or $P_{n} = 2^{(n+1)/2}$, if n is odd.
