combinatorics - 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!

Answer

A palindrome is a sequence of characters that reads the same forwards as backwards.

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.