It is slightly easier if we change our variables for strong induction. Here is what the formal proof would look like: