Consider the set $S1$ constructed recursively. The recursive step takes a string $w$ from $SI$ and coneatenates 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 awainS$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 S$1.$

Use induction to prove that every string in S$1$ is a palindrome. A palindrome is a string that reads the same from left to right and from right to left.