A palindrome can be defined as a string that reads the same forward and backward. You can also

define a palindrome as follows:

i$.$ The empty string, $,$ is a palindrome.

ii$.$ If $$ in $,$ then string $$ is a palindrome.

iii. If $$ in $$ and $$ in $$ is a palindrome, then $$ is a palindrome.

Prove by induction that the two definitions are equivalent.