# Deriving the number of all even length palindromic sequences with length at most $n$

Derive the number of all even length palindromic sequences with length $\leq n$.

If $n=4$, I have to count the number of non-palindromes of length 0, 2, and 4.

Also, $2p = n$, so a string of length $n = 4$ has $p = 2$. This comes in handy later.

$x$ represents the number of possible characters in the given alphabet- so $x = 26$ for English, 2 for binary, etc.

I chose to approach by counting, using this thought process.

$$\sum_{k=0}^{p} (x^{2k} - x^k)$$ In other words - a summation of all possible even length strings up to length $n$, subtracting cases that are palindromes.

I tested this with binary, up to length 4. (Binary non-palindromes of length 0, 2, and 4). This means $p$ goes from 0, to 1, to 2.

This evaluates to: $$2^0 - 2^0 +$$ $$2^2 - 2^1 +$$ $$2^4 - 2^2$$

Which sums to a total of 14 non palindromes.

All possible combinations are {}, 11, 00, 10, 01, 1111, 1100, 1000, 0000, 0001, 0011, 0111, 1010, 0101, 0110, 1001 1110, 1101, 0010, 1011, 0100.

14 of these are not palindromes, confirming my approach.

The solution states the formula is $$\frac{x^{2p+1}-2x^{p+1}+x}{x-1}$$ Following the same logic...

With $p = 2$, $x = 2$, $n = 4$, we have

$$\frac{2^{4+1}-2(2)^{3}+2}{2-1}$$

Which works out to 18, not 14. I have worked this out several times, and I'm not exactly sure what/if I am misunderstanding. Any help would be greatly appreciated. Thanks!

If the sequence has even length, say $n = 2k$, selecting the first $k$ characters completely determines the palindrome since the remaining $k$ characters can be found by repeating the sequence in the reverse order. Hence, the number of palindromes of even length at most $n$ in an alphabet with $x$ characters is $$x^0 + x^1 + x^2 + x^3 + \cdots + x^k = \frac{1 - x^{k + 1}}{1 - x}$$ where we have used the formula for the sum of a geometric series with initial term $1$ and common ratio $x$.
In your example of binary sequences of even length at most $4$, there are seven palindromes: $$\emptyset, 00, 11, 0000, 0110, 1001, 1111$$ Notice that our formula yields $$2^0 + 2^1 + 2^2 = 1 + 2 + 4 = 7$$ or $$\frac{1 - 2^{2 + 1}}{1 - 2} = \frac{1 - 2^3}{-1} = \frac{-7}{-1} = 7$$
Since there are a total of $$x^0 + x^2 + x^4 + \ldots + x^{2k} = \frac{1 - x^{2k + 2}}{1 - x^2}$$ sequences of even length at most $n = 2k$ in an alphabet with $x$ characters, the number of sequences of even length at most $n = 2k$ that are not palindromes is \begin{align*} \frac{1 - x^{2k + 2}}{1 - x^2} - \frac{1 - x^{k + 1}}{1 - x} & = \frac{1 - x^{2k + 2}}{1 - x^2} - \frac{1 - x^{k + 1}}{1 - x} \cdot \frac{1 + x}{1 + x}\\ & = \frac{1 - x^{2k + 2}}{1 - x^2} - \frac{1 + x - x^{k + 1} - x^{k + 2}}{1 - x^2}\\ & = \frac{-x + x^{k + 1} + x^{k + 2} - x^{2k + 2}}{1 - x^2} \end{align*} In your example of binary sequences of even length at most $4$, the total number of sequences is $$2^0 + 2^2 + 2^4 = 1 + 4 + 16 = 21$$ of which seven are palindromes, so there are $14$ non-palindromes as you found. Notice that our formulas yield $$\frac{1 - 2^{2 \cdot 2 + 2}}{1 - 2^2} = \frac{1 - 2^6}{1 - 2^2} = \frac{1 - 64}{1 - 4} = \frac{-63}{-3} = 21$$ total sequences and $$\frac{-2 + 2^{2 + 1} + 2^{2 + 2} - 2^{2 \cdot 2 + 2}}{1 - 2^2} = \frac{-2 + 2^3 + 2^4 - 2^6}{1 - 2^2} = {-2 + 8 + 16 - 64}{1 - 4} = \frac{-42}{-3} = 14$$ non-palindromes.