From where you left off, we want to prove this:
The above would be true if and only if:
Thus, by the exhaustion of cases, we proved the result:
Hence, the result is true for n = k+1 if it is also true for n = k.
By, mathematical induction, the result is true for all positive integers of n.