Proving by induction that a palindrome contains an even number of $b$s and $c$s

Question

Suppose we want to construct palindromes that contain an $aa$ in the middle if the length is even and an $a$ in the middle if the length is odd. I'm trying to prove by induction that all of these palindromes (over $\{a,b,c\}$) contain an even number of $b$s and $c$s.

I'm having trouble figuring out what the inductive hypothesis should be. I understand that straight away, if the string is $aa$ or $a$ that it contains an even number of $b$s and $c$s, but I don't know how to extend the definition formally. Can someone please help?

Answer 1

start values:

Something small has property P:

• "a" is an even palindrome
• "aa" is an even palindrome

Induction step:

If something small has property P then something a bit bigger has property P

• if $x$ is an even palindrome then a$x$a is an even palindrome
• if $x$ is an even palindrome then b$x$b is an even palindrome
• if $x$ is an even palindrome then c$x$c is an even palindrome

And then prove that your palindrome can be built this way

PS this way you cannot prove that "bb" and "cc" are even palindromes (but you can just add them to the startvalues)

(Maybe easier) You can also also do the induction steps the other way around

• if a$x$a is NOT an even palindrome then $x$ is NOT an even palindrome
• if b$x$b is NOT an even palindrome then $x$ is NOT an even palindrome
• if c$x$c is NOT an even palindrome then $x$ is NOT an even palindrome

start with assuming your palindrome is NOT even and shorten it and if it ends as a valid palindrome you have a contradiction so your assumption was false.