1. ## [SOLVED] Palindromes (Tricky)

How many binary strings of length n are palindromes?

Now, I have come to the conclusion that it depends on whether n is even or odd because I just cant find a single formula for this otherwise.

Even length = 2 ^ (n / 2).
Odd Length im not sure. Can someone give me alittle hint or help on this.
Ive been thinking about it for too long.

2. Originally Posted by kurac
How many binary strings of length n are palindromes?

Now, I have come to the conclusion that it depends on whether n is even or odd because I just cant find a single formula for this otherwise.

Even length = 2 ^ (n / 2).
Odd Length im not sure. Can someone give me alittle hint or help on this.
Ive been thinking about it for too long.
You are correct for when n is even.

Suppose n is odd. Then n=2k+1.
A palindrome is entirely determined by the first k positions, as the last k must be the same in reverse. The middle position can be anything.

So we have 2 choices for the middle positions, and $2^k$ choices for the first k positions. So there are $2\cdot 2^k=2^{k+1}=2^{(n-1)/2+1}=2^{(n+1)/2}$

3. Hello, kurac!

How many binary strings of length $n$ are palindromes?
Both you and amitface are correct . . .

. . $\begin{array}{cc}\text{Even }n\!:& 2^{\frac{n}{2}} \\ \\[-3mm] \text{Odd }n\!: & 2^{\frac{n+1}{2}} \end{array}$

They can be merged into one function like this:

. . $f(n) \;=\;\frac{1+(\text{-}1)^n}{2}\cdot2^{\frac{n}{2}} + \frac{1-(\text{-}1)^n}{2}\cdot 2^{\frac{n+1}{2}}$