Consider the set $S1$ constructed recursively. The recursive step takes a string $w$ from $S1$ and

concatenates the same symbol to the beginning and end of $w.$

$($i$)$ Basis: $inS1,$ainS$1,$ and binS$1$

$($ii$)$ Recursive step: if winS$1,$ then awa inS$1$ and bwbinS$1$

$($iii$)$ Closure: $S1$ consists of exactly the elements that can be obtained by starting

$($iv$)$ with the basis elements of S$1$ and applying the recursive step finitely many times to

construct new elements of $S1.$

Use induction to prove that every string in $S1$ is a palindrome. A palindrome is a string that reads

the same from left to right and from right to left.