Monday 30 January 2017

Multidimensional Induction for n Variables




I am wanting to use a proof technique known as multidimensional induction, and I am having a hard time finding a situation that explains how to use this technique clearly for three or more variables. I want to use this technique properly and have listed the steps below which would make sense to me, but they could be wrong. Please, feel free to copy the code as it is a lot of typing and post answers as to how to conduct this proof technique properly.



Let us say I have a statement that is $P(x_1, x_2, x_3, ..., x_n)$ for some $n\in \mathbb{N}$ and want to show that $\forall x_1, x_2,..., x_n\in \mathbb{N}$, $P(x_1, x_2, x_3, ..., x_n)$ is true.





  1. We let $x_1, x_2, x_3, ..., x_n\in \mathbb{N}$ and confirm the base case is true, namely $P(1, 1, 1, ..., 1)$.


  2. Inductive step over $x_1$: We let $k_1\in \mathbb{N}$ and assume the statement $P(k_1, 1,1,...,1)$ is true. Our goal here is to show $P(k_1+1, 1, 1, ..., 1)$ is true.


  3. Inductive step over $x_2$: We let $k_2\in \mathbb{N}$ and assume $P(h_1, k_2, 1, ..., 1)$ is true for some $h_1\in \mathbb{N}$. Our goal here is to show $P(h_1, k_2+1, 1, ..., 1)$ is true.



  4. Inductive step over $x_3$: We let $k_3\in \mathbb{N}$ and assume $P(h_1, h_2, k_3, ..., 1)$ is true for some $h_1, h_2\in \mathbb{N}$. Our goal here is to show $P(h_1, h_2, k_3+1, ..., 1)$ is true.





We continue our inductive steps until we have expended all variables through our inductive steps except $x_n$.





  1. Inductive step over $x_n$: We let $k_n\in \mathbb{N}$ and assume $P(h_1, h_2, h_3, ..., k_n)$ is true for some $h_1, h_2, ... \in \mathbb{N}$. Our goal here is to show $P(h_1, h_2, h_3, ..., k_n+1)$ is true.





We have shown $\forall h_1, h_2, ..., h_n\in \mathbb{N}$, $P(h_1, h_2, h_3, ..., h_n)$ is true. Therefore, $\forall x_1, x_2,..., x_n\in \mathbb{N}$, $P(x_1, x_2, x_3, ..., x_n)$ is true.




Answer



In practice I would hope that the statement $P(x_1,\dotsc,x_n)$ would be highly symmetrical, and then it would suffice just prove the $i$th case and be done with it.



In principle, however, without any symmetry assumptions, I agree that induction will need to be done separately in each variable.




Perhaps you should also consider doing induction in the number of variables: I have an inductive proof of $\forall x_1 P(x_1,\cdots,1)$, and if I have an inductive proof of $\forall x_1,\cdots,x_i\,P(x_1,\cdots,x_i,1,\cdots,1),$ then I can derive a proof of $\forall x_1,\cdots,x_i,x_{i+1}\,P(x_1,\cdots,x_i,x_{i+1},1,\cdots,1),$ for $i

No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...