Consider strings made up only of the characters $0$ and $1$; these are binary strings. A binary palindrome is a palindrome that is also a binary string.
(a)Let $f(n)$ be the number of binary palindromes of length $2n$, for $n\ge 0$. Discover a formula for $f(n)$. Here are two pairs to get you started: $f(0) = 1$, $f(1) = 2$, $\ldots$. (Notice that we are concerned only with even-length binary palindromes.)
(b)Prove that your formula is correct for all $n\ge 0$, using simple induction.
I get that the formula would be $f(n) = 2^n$, but I'm having difficulty proving this. I am new to induction, so I am unsure where to begin. Any help would be appreciated 🙂
Best Answer
Two methods:
Direct Approach: To make a palindrome of length $2n$ we may choose the first $n$ however we like, then repeat the string backwards. But there are $2$ ways to choose the first character, $2$ ways to choose the second, up to $2$ ways to choose the $n^{th}$ so there are $2^*2^*\dots^*2=2^n$ ways to do it.
Induction: It is easy to verify the formula for small $n$ (but you should be sure to do it!). Assume we have done it for $n-1$. Thus we know there are $2^{n-1}$ palindromic strings of length $2(n-1)$. Now, to make a palindromic string of lenght $2n$ we choose one of length $2(n-1)$ and select a character (either $1$ or $0$) to surround it (one in front, one at the end). There are, by induction, $2^{n-1}$ ways to choose the string of length $2(n-1)$ and $2$ ways to choose the surrounding character so all in all there are $2^*2^{n-1}=2^n$ ways to make our string of length $2n$, as desired.