A palindrome is a string whose reversal is identical to the string. How many bitstrings of length n are palindromes?

The number of palindromic bitstrings of length n depends on whether n is even or odd.

1. If n is even, then the first n/2 bits can be anything, and the last n/2 bits are determined by the first n/2 bits (they must be the same in reverse order). Since each bit can be either 0 or 1, there are 2^(n/2) possible bitstrings for the first n/2 bits. Therefore, there are 2^(n/2) palindromic bitstrings of length n when n is even.

2. If n is odd, then the first (n-1)/2 bits can be anything, the middle bit can be anything, and the last (n-1)/2 bits are determined by the first (n-1)/2 bits. Therefore, there are 2^((n-1)/2) * 2 = 2^((n+1)/2) palindromic bitstrings of length n when n is odd.

So, in general, the number of palindromic bitstrings of length n is 2^(ceil(n/2)), where ceil is the ceiling function (rounding up to the nearest integer).