<s>[INST] 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!
 [/INST] 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. 
</s>