# Proof by complete induction on binary strings

The question below is a past midterm question and i do not have any idea how to start.

Let x and y be two binary strings. We say that x is a subsequence of y iﬀ x equals y with zero or more of its bits removed. E.g., 1011 is a subsequence of 01101001

I want to prove that for any two binary strings u, v, there is a longest string w such that w is a subsequence of u and w is a subsequence of v by using complete induction. What should be the approach?

• what if u=1 and v=0 – FickyLicky May 24 '17 at 22:03
• Then it's the null string. – marty cohen May 25 '17 at 1:37
• Maybe double induction over the lengths of u and v. – marty cohen May 25 '17 at 1:38
• Maybe I'm misunderstanding the question, but this seems completely trivial: just take all the strings that are subsequences of both $u$ and $v$, and take one among them that has maximal length. I don't understand why you would use induction... – Eric Wofsey May 25 '17 at 1:41

As EricWofsey points out, the existence of $w$ is trivial: out of all the strings that are subsequences of both $u$ and $v$, there must of course be one or more with the maximum length ... But let me describe a recursive procedure to actually find such a $w$ ... And attach an inductive proof to that very recursion:

The basic idea is to start by looking at the first digits of both $u$ and $v$: if they are the same, then we can have $w$ start with that very digit as well, and now we look at the second digit ... Which is really the first digit of the rest, i.e. here is where we can recurse. And if the digits are different, then either remove the first digit from $u$, or remove the first digit from $v$, and see in which case you get the longest subsequence common to both.

More formally:

Claim: For any $n$: for any binary strings $u$ and $v$ whose lengths add up to $n$, we can find a longest string $w$ that is a subsequence of both $u$ and $v$

Proof: By strong/complete induction on $n$

Base: If $n =0$ then both $u$ and $v$ are the empty string, and with $w$ being the empty string as well, it is clear that $w$ is the longest strig that is a subsequence of both $u$ and $v$

Step: Suppose the claim holds for any $n \le k$. Now consider any two strings $u$ and $v$ whose lengths add up to $k+1$. Then consider the following cases:

• Either $u$ or $v$ is the empty string. Then it is obvious that with $w$ being the empty string, $w$ is the longest string that is a subsequence of both $u$ and $v$
• $u$ and $v$ have the same digit $d$ as the first digit. Remove this first digit from both $u$ and $v$, resulting in $u'$ and $v'$ whose lengths add up to $k-1$. Thus, by the inductive hypothesis, we can find a longest string $w'$ that is a subsequence of both $u'$ and $v'$. Then it is obvious that $w$, which is $w'$ with digit $d$ in frontof it will be the longest string that is a subsequence of both $u$ and $v$.
• $u$ and $v$ start with a different digit. Then remove the first digit from $u$, resulting in $u'$. Since the lengths of $u'$ and $v$ add up to $k$, it follows by the inductive hypothesis that we can find a longest string $w'$ that is a subsequence of both $u'$ and $v$. Now remove the first digit fro $v$, resulting in $v'$. Since the lengths of $u$ and $v'$ add up to $k$, it follows by the inductive hypothesis that we can find a longest string $w''$ that is a subsequence of both $u$ and $v'$. Finally, if the length of $w'$ is greater or equal to the length of $w''$, then let $w$ be $w'$, otherwise let $w$ be $w''$. It should be clear that $w$ is the longest string that is a subsequence of $u$ and $v$.

Since this overs all possible scenarios, and since in each scenario we can find the longest string that is a subsequence of both, the step is hereby proven, and with that the whole inductive proof is completed.