How does mutual induction work?

Question

In my understanding you use the Induction Hypothesis to back up your argument, but what doesn't make sense to me is that we use the Induction Hypothesis even though the Induction Hypothesis wasn't proven yet! How does that make any sense? The Induction Hypothesis are just claims we want to prove along with the main claim.

Answer 1

The proposition is true in the first case.

If the proposition is true in the first case, then it is true in the second case.

If the proposition is true in the second case, then it is true in the third case.

If the proposition is true in the third case, then it is true in the fourth case.

If the proposition is true in the fourth case, then it is true in the fifth case.

. . . and so on.

The part after "If" is the induction hypothesis. The part after "then" is what is proved by using the induction hypothesis.

Answer 2

When conducting induction, we are not trying to directly prove that a property $P$ in question holds for all members of a sequence $(f_n)$ or the set of natural numbers $\mathbb N$. Instead, we are trying to create a cascading domino effect, by showing that if the property holds for some element $f_n$, it then holds for the following element $f_{n+1}$.

In terms of dominoes, the inductive step shows that a falling domino causes another one to fall. This then means, that if the property $P$ should hold for some base case (not necessarily $0$ or $1$), as in $P(0)$, $P(1)$, or $P(2)$, et cetera, it then holds for the following element $P(1)$, $P(2)$ or $P(3)$. As the property now holds for the second element, by the inductive step it also holds for the third one, and so forth.

All of this of course requires, that there exists some base element for which the claim holds. In other words, for the entire set of dominoes to fall, there has to be some first element or domino piece that pushes the entire process into motion. That is the base case.

To find an answer to the question actually presented in the title about mutual induction, which is a special case of induction, I would look here.