2

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?

hanugm
  • 2,353
  • 1
  • 13
  • 34

1 Answers1

1

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

drhab
  • 151,093