Question

Suppose that ${\mathit{c}}_{\mathbf{1}}\mathbf{,}{\mathit{c}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathit{c}}_{\mathbf{p}}$is a longest common subsequence of the sequences ${\mathit{a}}_{\mathbf{1}}\mathbf{,}{\mathit{a}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathit{a}}_{\mathbf{m}}$and${\mathit{b}}_{\mathbf{1}}\mathbf{,}{\mathit{b}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathit{b}}_{\mathbf{n}}$.
a) Show that if ${\mathit{a}}_{\mathbf{m}}\mathbf{=}{\mathit{b}}_{\mathbf{n}}$, then ${\mathit{c}}_{\mathbf{p}}\mathbf{=}{\mathit{a}}_{\mathbf{m}}\mathbf{=}{\mathit{b}}_{\mathbf{n}}$and ${\mathit{c}}_{\mathbf{1}}\mathbf{,}{\mathit{c}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathit{c}}_{\mathbf{p}\mathbf{-}\mathbf{1}}$is a longest common subsequence of ${\mathit{a}}_{\mathbf{1}}\mathbf{,}{\mathit{a}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathit{a}}_{\mathbf{m}\mathbf{-}\mathbf{1}}$and ${\mathit{b}}_{\mathbf{1}}\mathbf{,}{\mathit{b}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathit{b}}_{\mathbf{n}\mathbf{-}\mathbf{1}}$ when $\mathit{p}\mathbf{>}\mathbf{1}$.
b) Suppose that ${\mathit{a}}_{\mathbf{m}}\mathbf{\ne }{\mathit{b}}_{\mathbf{n}}$. Show that if ${\mathit{c}}_{\mathbf{p}}\mathbf{\ne }{\mathit{a}}_{\mathbf{m}}$, then ${\mathit{c}}_{\mathbf{1}}\mathbf{,}{\mathit{c}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathit{c}}_{\mathbf{p}}$is a longest common subsequence of ${\mathit{a}}_{\mathbf{1}}\mathbf{,}{\mathit{a}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathit{a}}_{\mathbf{m}\mathbf{-}\mathbf{1}}$and ${\mathit{b}}_{\mathbf{1}}\mathbf{,}{\mathit{b}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathit{b}}_{\mathbf{n}}$and also show that if ${\mathit{c}}_{\mathbf{p}}\mathbf{\ne }{\mathit{b}}_{\mathbf{n}}$, then ${\mathit{c}}_{\mathbf{1}}\mathbf{,}{\mathit{c}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathit{c}}_{\mathbf{p}}$is a longest common subsequence of ${\mathit{a}}_{\mathbf{1}}\mathbf{,}{\mathit{a}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathit{a}}_{\mathbf{m}}$and${\mathit{b}}_{\mathbf{1}}\mathbf{,}{\mathit{b}}_{\mathbf{2}}\mathbf{,}\mathbf{\dots }\mathbf{,}{\mathit{b}}_{\mathbf{n}\mathbf{-}\mathbf{1}}$

Short answer

(a)$c_p=a_m=b_n$from all three sequences, then $c_1,c_2,\dots ,c_{(}p-1)$has to be the longest common subsequence of the sequences $a_1,a_2,\dots ,a_{m-1}$and$b_1,b_2,\dots ,b_{n-1}.$

(b) The two sequences then need to have been one of the remaining $m-1$terms in the sequence and thus$c_1,c_2,\dots ,c_p$ has to be the longest common subsequence of the sequences $a_1,a_2,\dots ,a_m$and$b_1,b_2,\dots ,b_{n-1}$

Step-by-step solution

Given data

$c_1,c_2,\dots ,c_p$is the longest common subsequence of the sequences $a_1,a_2,\dots ,a_m$and$b_1,b_2,\dots ,b_n.$

Definition

A recurrence relation is an equation that recursively defines a sequence where the next term is a function of the previous terms.

Simplify the solution of part (a)

Given: $c_1,c_2,\dots ,c_p$is the longest common subsequence of the sequences $a_1,a_2,\dots ,a_m$and $b_1,b_2,\dots ,b_n.$

Note: The longest common subsequence does not require to be a subsequence of consecutive terms.

$a_m=b_n$

If $a_m=b_n$, then this means that the last two elements in the two sequences $a_1,a_2,\dots ,a_m$and $b_1,b_2,\dots ,b_n.$are identical and thus the element $a_m=b_n$is common in both sequences.

Since the element $a_m=b_n$is common in both sequences, the element $a_m=b_n$needs to be contained in the longest common subsequence$c_1,c_2,\dots ,c_p$.
Since $a_m$and $b_n$are the last terms in the two sequences $a_1,a_2,\dots ,a_m$and $b_1,b_2,\dots ,b_n.$, the element in the longest common subsequence also has to be the last term:

$c_p=a_m=b_n$

Moreover, if we remove the element $c_p=a_m=b_n$from all three sequences, then $c_1,c_2,\dots ,c_{(}p-1)$has to be the longest common subsequence of the sequences $a_1,a_2,\dots ,a_{m-1}$and $b_1,b_2,\dots ,b_{n-1}.$(as we only removed the last element that was common in all three sequences).

Simplify the solution of part (b)

$a_m\ne b_n$

First case If $a_m\ne b_n$and $c_p\ne a_m,$then this means that the last common element between the sequences $a_1,a_2,\dots ,a_m$and $b_1,b_2,\dots ,b_n$is not $a_m$, and thus $a_m$is not common with any element in the sequence $b_1,b_2,\dots ,b_n$.

The last common element between the two sequences then needs to have been one of the remaining $m-1$terms in the sequence and thus $c_1,c_2,\dots ,c_p$has to be the longest common subsequence of the sequences $a_1,a_2,\dots ,a_{m-1}$and $b_1,b_2,\dots ,b_n$

Second case If $a_m\ne b_n$and $c_p\ne b_n$, then this means that the last common element between the sequences $a_1,a_2,\dots ,a_m$and $b_1,b_2,\dots ,b_n$is not $b_n$, and thus $b_n$is not common with any element in the sequence $a_1,a_2,\dots ,a_m$

The last common element between the two sequences then needs to have been one of the remaining $m-1$terms in the sequence and thus $c_1,c_2,\dots ,c_p$has to be the longest common subsequence of the sequences $a_1,a_2,\dots ,a_m$and$b_1,b_2,\dots ,b_{n-1}$