It is generally a good idea to start off by simplifying the first equation:
1. P(A) = P(A|C)*P(C) + P(A|C!)*P(C!)
Which can be simplified into
2. P(A) = P(A∩C) + P(A∩C!) [2]
After this useful simplification, we can start manipulating the second equation using the formula:
3. P(A|B) = P(A∩B)/P(B)
Inserting "2." in place of P(A) in "3." gives us
4. P(A|B) = P(A∩B∩C)/P(B) + P(A∩B∩C!)/P(B)
Conditioning on (B ∩ C) or (B ∩ C!) gives
5. P(A|B) = P(A|C∩B)*P(C∩B)/P(B) + P(A|C!∩B)*P(C!∩B)/P(B)
Expressing P(C∩B)/P(B) as P(C|B) and P(C!∩B)/P(B) as P(C!|B) yields
6. P(A|B) = P(A|C∩B)P(C|B) + P(A|C!∩B)P(C!|B)
The intersection components are interchangeable.
Hence the equality is proven.
