1

I am interested in establishing a form of multidimensional induction where I would like to establish $P(n_1, n_2, n_3, ..., n_m)$ for some $m\in \mathbb{N}$. I want to show that $\forall n_1, n_2,\ldots, n_m \geq 0$, $P(n_1, n_2, n_3, ..., n_m)$ is true.

Similar questions on Math SE are included here and here. I'm not aware of a general technique or strategy for $m>2$. I am also considering $0$ as a natural number so that I write the indices as $P(0, 0, n_j, \ldots, 0)$ instead of $P(1, 1, n_j, \ldots, 1)$ (although, I don't see any concern with using $1$ or $0$ for the indices).

Here are my proposed strategies for the case $m=2,m=3,$ and $m=m$. I don't think my way of performing the induction is standard and might be doing some additional work as opposed to the minimum needed.

Case $1$ ($m=2$): Establish $P(n_1, n_2)$ for all $n_1,n_2 \geq 0$ (Induct on $n_2$).

  1. Establish $P(n_1, 0)$ for all $n_1 \geq 0$.

  2. Given $P(n_1, n_2)$ for all $n_1 \geq 0$, $n_2 < \bar{n}_2$, establish $P(n_1, \bar{n}_2)$ for all $n_1 \geq 0$. This can be accomplished through the two steps below:

    • (a) Establish $P(0, \bar{n}_2)$ for all $\bar{n}_2\geq 0$ (where the hypothesis in step $2$ gives the required case for $n_2 < \bar{n}_2$).
    • (b) Given $P(n_1, \bar{n}_2)$ for all $n_1 < \bar{n}_1$, $\bar{n}_2 \geq 0$, establish $P(\bar{n}_1, \bar{n}_2)$.

Case $2$ ($m=3$): Establish $P(n_1, n_2,n_3)$ for all $n_1,n_2,n_3 \geq 0$ (Induct on $n_3$).

  1. Establish $P(n_1, 0,0)$ for all $n_1 \geq 0$.

  2. Given $P(n_1, n_2,0)$ for all $n_1 \geq 0$, $n_2 < \bar{n}_2$, establish $P(n_1, \bar{n}_2,0)$ for all $n_1 \geq 0$. This can be accomplished through the two steps below:

    • (a) Establish $P(0, \bar{n}_2,0)$ for all $\bar{n}_2\geq 0$ (where the hypothesis in step $2$ gives the required case for $n_2 < \bar{n}_2$).
    • (b) Given $P(n_1, \bar{n}_2,0)$ for all $n_1 < \bar{n}_1$, $\bar{n}_2 \geq 0$, establish $P(\bar{n}_1, \bar{n}_2,0)$.

  3. Given $P(n_1, 0,n_3)$ for all $n_1 \geq 0$, $n_3 < \bar{n}_3$, establish $P(n_1, 0,\bar{n}_3)$ for all $n_1 \geq 0$. This can be accomplished through the two steps below:

    • (a) Establish $P(0, 0,\bar{n}_3)$ for all $\bar{n}_3\geq 0$ (where the hypothesis in step $3$ gives the required case for $n_3 < \bar{n}_3$).
    • (b) Given $P(n_1, 0,\bar{n}_3)$ for all $n_1 < \bar{n}_1$, $\bar{n}_3 \geq 0$, establish $P(\bar{n}_1, 0,\bar{n}_3)$.

  4. Establish $P(0, n_2,0)$ for all $n_2 \geq 0$.

  5. Given $P(0, n_2,n_3)$ for all $n_2 \geq 0$, $n_3 < \bar{n}_3$, establish $P(0, n_2,\bar{n}_3)$ for all $n_2 \geq 0$. This can be accomplished through the step below (as the base case for $P(0, 0,\bar{n}_3)$ is handled in step $3a$).

    • (a) Given $P(0, n_2,\bar{n}_3)$ for all $n_2 < \bar{n}_2$, $\bar{n}_3 \geq 0$, establish $P(0, \bar{n}_2,\bar{n}_3)$.

  6. Given $P(n_1, n_2,n_3)$ for all $n_1,n_2 \geq 0, n_3 < \bar{n}_3$, establish $P(n_1, n_2,\bar{n}_3)$ for all $n_1,n_2 \geq 0.$ This can be accomplished through the step below (once again, the base case is handled by previous steps $2,3,3a,5$).

    • (a) Given $P(n_1, n_2, \bar{n}_3)$ for all $n_1 < \bar{n}_1$, $n_2 < \bar{n}_2$, $\bar{n}_3 \geq 0$, establish $P(\bar{n}_1, \bar{n}_2, \bar{n}_3)$.

Case $3$ ($m=m$): Establish $P(n_1, n_2,\ldots,n_m)$ for all $n_1,n_2,\ldots,n_m \geq 0$ (Induct on $n_m$).

  1. Establish $P(0,\ldots,n_j,\ldots,0)$ for all $1 \leq j < m$ and $n_1,\ldots,n_j \geq 0.$

  2. Given $P(n_1,n_2,\ldots,n_j,\ldots,0)$ for all $1 \leq j < m$ and $n_1,\ldots,n_j \geq 0$, establish $P(n_1,n_2,\ldots,\bar{n}_j,\ldots,0)$. This can be accomplished through the two steps below:

    • (a) Establish $P(0,\ldots,\bar{n}_j,\ldots,0)$ for all $\bar{n}_j \geq 0$ (where the hypothesis in step $2$ gives the required case for $n_j < \bar{n}_j$).
    • (b) Given $P(n_1,n_2,\ldots,\bar{n}_j,\ldots,0)$ for all $1 \leq j < m$ and $n_1 < \bar{n}_1, n_2 < \bar{n}_2,\ldots, n_{j-1} < \bar{n}_{j-1}$ and $\bar{n}_j\geq 0$, establish $P(\bar{n}_1,\bar{n}_2,\ldots,\bar{n}_j,\ldots,0)$.

  3. Given $P(n_1,n_2,\ldots,n_j,n_{j+1},\ldots,0)$ for all $1 \leq j+1 < m$ and $n_1,\ldots,n_{j+1} \geq 0$, establish $P(n_1,n_2,\ldots,n_j,\bar{n}_{j+1},\ldots,0)$. This can be accomplished through the two steps below:

    • (a) Establish $P(0,\ldots,\bar{n}_{j+1},\ldots,0)$ for all $\bar{n}_{j+1} \geq 0.$ (where the hypothesis in step $3$ gives the required case for $n_{j+1} < \bar{n}_{j+1}$).
    • (b) Given $P(n_1,n_2,\ldots,n_j,\bar{n}_{j+1},\ldots,0)$ for all $1 \leq j+1 < m$ and $n_1 < \bar{n}_1, n_2 < \bar{n}_2,\ldots, n_{j} < \bar{n}_{j}$ and $\bar{n}_{j+1}\geq 0$, establish $P(\bar{n}_1,\bar{n}_2,\ldots,\bar{n}_j,\bar{n}_{j+1}\ldots,0)$.

  4. Given $P(n_1,n_2,\ldots,n_{m-1},n_m)$ for all $n_1,n_2,\ldots,n_{m-1} \geq 0$ and $n_m < \bar{n}_m$, establish $P(n_1,n_2,\ldots,n_{m-1},\bar{n}_m)$. This can be accomplished through the two steps below (the base cases are handled by steps $2$ and $3$):

    • (a) Establish $P(0,\ldots,\bar{n}_{m})$ for $\bar{n}_{m} \geq 0$ (where from step $4$, we know that this is true for $n_{m} < \bar{n}_{m}$).
    • (b) Given $P(n_1,n_2,\ldots,n_{m-1},\bar{n}_m)$ for all $n_1 < \bar{n}_1, n_2 < \bar{n}_2, \ldots n_{m-1} < \bar{n}_{m-1}$ and $\bar{n}_m \geq 0$, establish $P(\bar{n}_1,\bar{n}_2,\ldots,\bar{n}_{m-1},\bar{n}_m)$.

I don't recall seeing many results past the case where $m=2$ (various authors generally show what happens when $m=2$ and then say that "the general case will follow from similar arguments.") If, for example, $m=100$, then is the general procedure to show what happens for $m=2$ and not worry about completing a successful proof for $m=40$ or $m=80$? Is there a published result in a textbook or paper which handles something similar to the general case?

Axion004
  • 10,056
  • There are lots of ways to do multi-dimensional induction, and you pick which is most convenient to induct on. EG You can induct on $N = \sum n_i $, like in the case of the multinomial theorem. $\quad$ Alternatively, you can induct on each variable, holding all others constant. This greatly simplifies your case 3. (You have 2 case 3's so ...) – Calvin Lin Feb 26 '22 at 22:43
  • Why do I have two case $3$? I'm not sure how one would induct on $N=\sum n_i$ and inducted on every variable (as this made the most sense to me). I will review the proof of the multinomial theorem. – Axion004 Feb 27 '22 at 01:53
  • (Oh, I misread, your cases are labelled correctly.) $\quad$ You induct on $N$, and do the case of figuring out which $n_i$ has increased. If the variables represent similar things, then hopefully you can just show the case of 1 variable. – Calvin Lin Feb 27 '22 at 12:39

0 Answers0