Mixing
Proof by induction on $r$ variables
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
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?
induction
asked Aug 2 at 11:44
hanugm
789419
add a comment |Â
up vote
2
down vote
favorite
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?
induction
asked Aug 2 at 11:44
hanugm
789419
Choose one and prove by induction on it; then generalize. If you cannot generalize, you have to perform "nested" inductions.
– Mauro ALLEGRANZA
Aug 2 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 at 11:52
2
See e.g. Mathematical Induction , page 111-on.
– Mauro ALLEGRANZA
Aug 2 at 11:59
1
See also the post : Multidimensional induction for $n$ variables.
– Mauro ALLEGRANZA
Aug 2 at 12:34
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
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?
induction
asked Aug 2 at 11:44
hanugm
789419
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?
induction
asked Aug 2 at 11:44
hanugm
789419
asked Aug 2 at 11:44
hanugm
789419
asked Aug 2 at 11:44
hanugm
789419
asked Aug 2 at 11:44
hanugm
789419
789419
Choose one and prove by induction on it; then generalize. If you cannot generalize, you have to perform "nested" inductions.
– Mauro ALLEGRANZA
Aug 2 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 at 11:52
2
See e.g. Mathematical Induction , page 111-on.
– Mauro ALLEGRANZA
Aug 2 at 11:59
1
See also the post : Multidimensional induction for $n$ variables.
– Mauro ALLEGRANZA
Aug 2 at 12:34
add a comment |Â
Choose one and prove by induction on it; then generalize. If you cannot generalize, you have to perform "nested" inductions.
– Mauro ALLEGRANZA
Aug 2 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 at 11:52
2
See e.g. Mathematical Induction , page 111-on.
– Mauro ALLEGRANZA
Aug 2 at 11:59
1
See also the post : Multidimensional induction for $n$ variables.
– Mauro ALLEGRANZA
Aug 2 at 12:34
Choose one and prove by induction on it; then generalize. If you cannot generalize, you have to perform "nested" inductions.
– Mauro ALLEGRANZA
Aug 2 at 11:51
Choose one and prove by induction on it; then generalize. If you cannot generalize, you have to perform "nested" inductions.
– Mauro ALLEGRANZA
Aug 2 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 at 11:52
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 at 11:52
2
2
See e.g. Mathematical Induction , page 111-on.
– Mauro ALLEGRANZA
Aug 2 at 11:59
See e.g. Mathematical Induction , page 111-on.
– Mauro ALLEGRANZA
Aug 2 at 11:59
1
1
See also the post : Multidimensional induction for $n$ variables.
– Mauro ALLEGRANZA
Aug 2 at 12:34
See also the post : Multidimensional induction for $n$ variables.
– Mauro ALLEGRANZA
Aug 2 at 12:34
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
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_ileq n_i$ for $i=1,dots,r$ and $sum_i=1^rk_i<sum_i=1^rn_i$.
answered Aug 2 at 12:52
drhab
85.8k540118
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
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_ileq n_i$ for $i=1,dots,r$ and $sum_i=1^rk_i<sum_i=1^rn_i$.
answered Aug 2 at 12:52
drhab
85.8k540118
add a comment |Â
up vote
1
down vote
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_ileq n_i$ for $i=1,dots,r$ and $sum_i=1^rk_i<sum_i=1^rn_i$.
answered Aug 2 at 12:52
drhab
85.8k540118
add a comment |Â
up vote
1
down vote
up vote
1
down vote
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_ileq n_i$ for $i=1,dots,r$ and $sum_i=1^rk_i<sum_i=1^rn_i$.
answered Aug 2 at 12:52
drhab
85.8k540118
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_ileq n_i$ for $i=1,dots,r$ and $sum_i=1^rk_i<sum_i=1^rn_i$.
answered Aug 2 at 12:52
drhab
85.8k540118
edited Aug 2 at 12:57
answered Aug 2 at 12:52
drhab
85.8k540118
answered Aug 2 at 12:52
drhab
85.8k540118
answered Aug 2 at 12:52
drhab
85.8k540118
85.8k540118
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2869987%2fproof-by-induction-on-r-variables%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Choose one and prove by induction on it; then generalize. If you cannot generalize, you have to perform "nested" inductions.
– Mauro ALLEGRANZA
Aug 2 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 at 11:52
2
See e.g. Mathematical Induction , page 111-on.
– Mauro ALLEGRANZA
Aug 2 at 11:59
1
See also the post : Multidimensional induction for $n$ variables.
– Mauro ALLEGRANZA
Aug 2 at 12:34