# Proof Question involving Binary Strings & Sets

I'm just wondering about this question I've been working on for my review homework. I tried to solve it on my own and I feel my proof makes decent sense but not the best sense. Please try to give any hints or comments to help me with this thanks.

Question:

If w: {1,...,L} => {0,1} is a binary string, the complement of w, denoted w^c, is the string of length L defined by w^c(i) = 1 - w(i). The reverse of w, denoted w^R, is the string of length L defined by w^R(i) = w(L + 1 - i). Use these definitions to give a careful proof that, for every binary string x, (x^C)^R = (x^R)^C.

Proof By Induction:

Hypothesis:

We can see that x is a binary string with length L and has other strings such as x^C and x^R which are within the length 0 < i ≤ L where i is the position of a character in the string x.

Base Case:

x = {0,1}, L = 2, x^c(1) = 1, x^c(2) = 0, (x^c)^R(1) = 0, (x^c)^R(2) = 1 x^R(1) = 1, x^R(2) = 0, (x^R)^C(1) = 0, (x^R)^C(2) = 1 => (x^c)^R = {0,1}, (x^R)^C = {0,1} thus the base case holds.

Inductive Step:

Suppose for every binary string L = K the base case is satisfied for every character in the string x for 0 < i ≤ L. Then for L = K + 1 we have (x^c)^R(i) = x^c(k+2-i) ≡ 1 - x^R(i) which satisfies the base case because for every character at pos i it is equal because of outer bracket functions.

conclude:

Thus the assertion holds for L = K + 1.

I appreciate all sorts of criticism and help towards this question so I can gain the knowledge on what I am doing wrong.

To use induction, you should be clear that you are progressing from strings of length $L$ to strings of length $L+1$ by adding a new character at a specific location, either the beginning or the end. I will use the beginning. If $x$ is a new character and $s$ is a string of length $L$ where it is known (from the induction hypothesis) that $(s^C)^R=(s^R)^C$ you want to prove that $((xs)^R)^C=((xs)^C)^R$ To do so, you need to argue that $(xs)^R=sx$ and $(xs)^C=x^Cs^C$ and you will be home.
For the base case, you have $L=1$ and there are two strings of that length. You can just say $(0^R)^C=0^C=1=1^R=(0^C)^R$ and the same for $1$ and be done.
• The idea of adding another character is in the spirit of an induction proof. You want to prove the assertion for $L+1$ from the known fact about $L$, so I want a string of length $L$ in my proof. Yes, I was sloppy about the use of $x$ and $s$-it would have been better to reverse them. – Ross Millikan Sep 12 '14 at 23:26