# Proof by induction on $r$ variables

If there is a statement $P(n)$, proof by induction has three steps.

Base case is to show $P(1)$ is true

Induction step is to assume $P(K)$ is true and then to show $P(k+1)$ is true.

If our statement $P(n_1,n_2,n_3,\cdots, n_r)$ involves $r$ variables, then how to prove it by induction?

• Choose one and prove by induction on it; then generalize. If you cannot generalize, you have to perform "nested" inductions. – Mauro ALLEGRANZA Aug 2 '18 at 11:51
• Means, Showing $P(1,n_2, n_2,\cdots n_r)$ as true, then assuming $P(k,n_2, n_2,\cdots n_r)$ as true then showing $P(k+1,n_2, n_2,\cdots n_r)$ as true? – hanugm Aug 2 '18 at 11:52
• See e.g. Mathematical Induction , page 111-on. – Mauro ALLEGRANZA Aug 2 '18 at 11:59
• See also the post : Multidimensional induction for $n$ variables. – Mauro ALLEGRANZA Aug 2 '18 at 12:34

## 1 Answer

Depends on context.

In general it boils down to finding a suitable well order on $\mathbb N^r$.

Then the induction step is proving that $P(n_1,\dots,n_r)$ implies $P(m_1,\dots,m_r)$ where $(m_1,\dots,m_r)$ denotes the successor of $(n_1,\dots,n_r)$.

Sometimes it is possible to do it with induction on $n=n_1+\cdots+n_r$.

Also you could use strong induction. Then it must be proved that $P(n_1,\dots,n_r)$ is true if $P(k_1,\dots,k_r)$ is true for every tuple $(k_1,\dots,k_r)$ with $k_i\leq n_i$ for $i=1,\dots,r$ and $\sum_{i=1}^rk_i<\sum_{i=1}^rn_i$.