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?

  • $\begingroup$ Choose one and prove by induction on it; then generalize. If you cannot generalize, you have to perform "nested" inductions. $\endgroup$ – Mauro ALLEGRANZA Aug 2 '18 at 11:51
  • $\begingroup$ 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? $\endgroup$ – hanugm Aug 2 '18 at 11:52
  • 2
    $\begingroup$ See e.g. Mathematical Induction , page 111-on. $\endgroup$ – Mauro ALLEGRANZA Aug 2 '18 at 11:59
  • 1
    $\begingroup$ See also the post : Multidimensional induction for $n$ variables. $\endgroup$ – Mauro ALLEGRANZA Aug 2 '18 at 12:34

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.