Mixing
Proof using mathematical Induction
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Suppose I am proving the statement $P(m,n)$ in natural numbers.
Steps:
1) Proving $P(1,1)$ true
2) $P(m,n) implies P(m+1,n)$
My doubt while proving second step is that, can I assume $P(m,1), P(m,2),cdots P(m,n)$ are true or I have to prove by taking $n$ as constant (using $P(m,n)$ only)?
Suppose I prove step 2, then
3) $P(m,n) implies P(m,n+1)$
Here can I assume $P(m-1,n+1)$ as true?
induction
edited yesterday
md2perpe
5,5691821
asked yesterday
hanugm
789419
 |Â
show 3 more comments
up vote
2
down vote
favorite
Suppose I am proving the statement $P(m,n)$ in natural numbers.
Steps:
1) Proving $P(1,1)$ true
2) $P(m,n) implies P(m+1,n)$
My doubt while proving second step is that, can I assume $P(m,1), P(m,2),cdots P(m,n)$ are true or I have to prove by taking $n$ as constant (using $P(m,n)$ only)?
Suppose I prove step 2, then
3) $P(m,n) implies P(m,n+1)$
Here can I assume $P(m-1,n+1)$ as true?
induction
edited yesterday
md2perpe
5,5691821
asked yesterday
hanugm
789419
1
$n$ must remain constant. Once you have proved $P(m,n)$ for a fixed $n$ then you can apply induction in the second argument.
– Dog_69
yesterday
In you prove $forallnP(1,n)$ and you prove $forallnP(m,n)impliesforallnP(m+1,n)$ you will have proved the theorem.
– saulspatz
yesterday
Exactly. The validity of your reasoning depends on this : can you prove 1) $P(1,n)$ true for all $n$, 2) $P(m,n)Longrightarrow P(m+1,n)$ for all $n$ ? If this is the case, then $n$ is merely a parameter in your induction. If not, then you have to build some sort of induction on $mathbb Ntimes mathbb N$, which can be quite tricky.
– Nicolas FRANCOIS
yesterday
@NicolasFRANCOIS Can I prove $P(m,n) implies P(m+1,n+1)$ without step 2 and 3?
– hanugm
yesterday
1
@hanugm : no, it's not enough. You lose $P(m,n+1)$ and $P(m+1,n)$.
– Nicolas FRANCOIS
yesterday
 |Â
show 3 more comments
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Suppose I am proving the statement $P(m,n)$ in natural numbers.
Steps:
1) Proving $P(1,1)$ true
2) $P(m,n) implies P(m+1,n)$
My doubt while proving second step is that, can I assume $P(m,1), P(m,2),cdots P(m,n)$ are true or I have to prove by taking $n$ as constant (using $P(m,n)$ only)?
Suppose I prove step 2, then
3) $P(m,n) implies P(m,n+1)$
Here can I assume $P(m-1,n+1)$ as true?
induction
edited yesterday
md2perpe
5,5691821
asked yesterday
hanugm
789419
Suppose I am proving the statement $P(m,n)$ in natural numbers.
Steps:
1) Proving $P(1,1)$ true
2) $P(m,n) implies P(m+1,n)$
My doubt while proving second step is that, can I assume $P(m,1), P(m,2),cdots P(m,n)$ are true or I have to prove by taking $n$ as constant (using $P(m,n)$ only)?
Suppose I prove step 2, then
3) $P(m,n) implies P(m,n+1)$
Here can I assume $P(m-1,n+1)$ as true?
induction
edited yesterday
md2perpe
5,5691821
asked yesterday
hanugm
789419
edited yesterday
md2perpe
5,5691821
edited yesterday
md2perpe
5,5691821
edited yesterday
md2perpe
5,5691821
5,5691821
asked yesterday
hanugm
789419
asked yesterday
hanugm
789419
asked yesterday
hanugm
789419
789419
1
$n$ must remain constant. Once you have proved $P(m,n)$ for a fixed $n$ then you can apply induction in the second argument.
– Dog_69
yesterday
In you prove $forallnP(1,n)$ and you prove $forallnP(m,n)impliesforallnP(m+1,n)$ you will have proved the theorem.
– saulspatz
yesterday
Exactly. The validity of your reasoning depends on this : can you prove 1) $P(1,n)$ true for all $n$, 2) $P(m,n)Longrightarrow P(m+1,n)$ for all $n$ ? If this is the case, then $n$ is merely a parameter in your induction. If not, then you have to build some sort of induction on $mathbb Ntimes mathbb N$, which can be quite tricky.
– Nicolas FRANCOIS
yesterday
@NicolasFRANCOIS Can I prove $P(m,n) implies P(m+1,n+1)$ without step 2 and 3?
– hanugm
yesterday
1
@hanugm : no, it's not enough. You lose $P(m,n+1)$ and $P(m+1,n)$.
– Nicolas FRANCOIS
yesterday
 |Â
show 3 more comments
1
$n$ must remain constant. Once you have proved $P(m,n)$ for a fixed $n$ then you can apply induction in the second argument.
– Dog_69
yesterday
In you prove $forallnP(1,n)$ and you prove $forallnP(m,n)impliesforallnP(m+1,n)$ you will have proved the theorem.
– saulspatz
yesterday
Exactly. The validity of your reasoning depends on this : can you prove 1) $P(1,n)$ true for all $n$, 2) $P(m,n)Longrightarrow P(m+1,n)$ for all $n$ ? If this is the case, then $n$ is merely a parameter in your induction. If not, then you have to build some sort of induction on $mathbb Ntimes mathbb N$, which can be quite tricky.
– Nicolas FRANCOIS
yesterday
@NicolasFRANCOIS Can I prove $P(m,n) implies P(m+1,n+1)$ without step 2 and 3?
– hanugm
yesterday
1
@hanugm : no, it's not enough. You lose $P(m,n+1)$ and $P(m+1,n)$.
– Nicolas FRANCOIS
yesterday
1
1
$n$ must remain constant. Once you have proved $P(m,n)$ for a fixed $n$ then you can apply induction in the second argument.
– Dog_69
yesterday
$n$ must remain constant. Once you have proved $P(m,n)$ for a fixed $n$ then you can apply induction in the second argument.
– Dog_69
yesterday
In you prove $forallnP(1,n)$ and you prove $forallnP(m,n)impliesforallnP(m+1,n)$ you will have proved the theorem.
– saulspatz
yesterday
In you prove $forallnP(1,n)$ and you prove $forallnP(m,n)impliesforallnP(m+1,n)$ you will have proved the theorem.
– saulspatz
yesterday
Exactly. The validity of your reasoning depends on this : can you prove 1) $P(1,n)$ true for all $n$, 2) $P(m,n)Longrightarrow P(m+1,n)$ for all $n$ ? If this is the case, then $n$ is merely a parameter in your induction. If not, then you have to build some sort of induction on $mathbb Ntimes mathbb N$, which can be quite tricky.
– Nicolas FRANCOIS
yesterday
Exactly. The validity of your reasoning depends on this : can you prove 1) $P(1,n)$ true for all $n$, 2) $P(m,n)Longrightarrow P(m+1,n)$ for all $n$ ? If this is the case, then $n$ is merely a parameter in your induction. If not, then you have to build some sort of induction on $mathbb Ntimes mathbb N$, which can be quite tricky.
– Nicolas FRANCOIS
yesterday
@NicolasFRANCOIS Can I prove $P(m,n) implies P(m+1,n+1)$ without step 2 and 3?
– hanugm
yesterday
@NicolasFRANCOIS Can I prove $P(m,n) implies P(m+1,n+1)$ without step 2 and 3?
– hanugm
yesterday
1
1
@hanugm : no, it's not enough. You lose $P(m,n+1)$ and $P(m+1,n)$.
– Nicolas FRANCOIS
yesterday
@hanugm : no, it's not enough. You lose $P(m,n+1)$ and $P(m+1,n)$.
– Nicolas FRANCOIS
yesterday
 |Â
show 3 more comments
2 Answers
2
active
oldest
votes
up vote
1
down vote
If $X$ is a set that is well-ordered by some ordering relation $<$, then you can prove a property $Q(x)$ by induction on $x$, by showing that for any $x in X$, if $Q(y)$ holds for every $y < x$, then $Q(x)$ holds.
This is called complete or course-of-values induction when $X$ is the natural numbers with the usual ordering. Peano's principle of induction for the natural numbers asking you to prove that $Q(0)$ holds and that for every $x in BbbN$, $Q(x + 1)$ holds if $Q(x)$ holds is a special case.
In your case, $X$ is $BbbNtimesBbbN$ (the set of pairs of natural numbers $(m, n)$). The induction principle you want to use is justified by considering the lexicographic ordering on $X$: $(m, n) < (m', n')$ iff $m < m'$ or $m = m'$ and $n < n'$.
answered yesterday
Rob Arthan
27k42863
add a comment |Â
up vote
1
down vote
It is easier to figure out the answer by drawing a grid with the first few elements of $Bbb Ntimes Bbb N$.
Given the question you're asking, what you really want to do is proceed by squares: let $T(n)$ denote the proposition
$P(p,q)$ is true for all $p,q$ such that $pleq n$ and $qleq n$.
I claim that if you prove what you said, then you can prove that $T(n)implies T(n+1)$ for all $n$.
What you said you can prove is
$$[P(p,1), P(p,2),cdots P(p,q)]implies P(p+1,q)tag1$$
$$[P(p-1,q+1), P(p,q)] implies P(p,q+1)tag2$$
I'm assuming here that cases where $pleq 0$ or $qleq 0$ are considered vacuously true.
Now assume $T(n)$.
- By $(2)$, you can prove that $P(1,n+1)$ and then $P(p,n+1)$ for all $pleq n$.
- By applying $(1)$ to every $q$ between $1$ and $n+1$, you get $P(n+1,q)$ for all $qleq n+1$.
Hence $T(n+1)$ as claimed.
answered yesterday
Arnaud Mortier
17.7k21757
By 2, how $P(1, n+1)$ can be proved?
– hanugm
yesterday
To prove $P(1,n+1)$, we need $P(0,n+1)$ and $P(1,1)$, but we dont have $P(0,n+1)$. Isnt it?
– hanugm
yesterday
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
If $X$ is a set that is well-ordered by some ordering relation $<$, then you can prove a property $Q(x)$ by induction on $x$, by showing that for any $x in X$, if $Q(y)$ holds for every $y < x$, then $Q(x)$ holds.
This is called complete or course-of-values induction when $X$ is the natural numbers with the usual ordering. Peano's principle of induction for the natural numbers asking you to prove that $Q(0)$ holds and that for every $x in BbbN$, $Q(x + 1)$ holds if $Q(x)$ holds is a special case.
In your case, $X$ is $BbbNtimesBbbN$ (the set of pairs of natural numbers $(m, n)$). The induction principle you want to use is justified by considering the lexicographic ordering on $X$: $(m, n) < (m', n')$ iff $m < m'$ or $m = m'$ and $n < n'$.
answered yesterday
Rob Arthan
27k42863
add a comment |Â
up vote
1
down vote
If $X$ is a set that is well-ordered by some ordering relation $<$, then you can prove a property $Q(x)$ by induction on $x$, by showing that for any $x in X$, if $Q(y)$ holds for every $y < x$, then $Q(x)$ holds.
This is called complete or course-of-values induction when $X$ is the natural numbers with the usual ordering. Peano's principle of induction for the natural numbers asking you to prove that $Q(0)$ holds and that for every $x in BbbN$, $Q(x + 1)$ holds if $Q(x)$ holds is a special case.
In your case, $X$ is $BbbNtimesBbbN$ (the set of pairs of natural numbers $(m, n)$). The induction principle you want to use is justified by considering the lexicographic ordering on $X$: $(m, n) < (m', n')$ iff $m < m'$ or $m = m'$ and $n < n'$.
answered yesterday
Rob Arthan
27k42863
add a comment |Â
up vote
1
down vote
up vote
1
down vote
If $X$ is a set that is well-ordered by some ordering relation $<$, then you can prove a property $Q(x)$ by induction on $x$, by showing that for any $x in X$, if $Q(y)$ holds for every $y < x$, then $Q(x)$ holds.
This is called complete or course-of-values induction when $X$ is the natural numbers with the usual ordering. Peano's principle of induction for the natural numbers asking you to prove that $Q(0)$ holds and that for every $x in BbbN$, $Q(x + 1)$ holds if $Q(x)$ holds is a special case.
In your case, $X$ is $BbbNtimesBbbN$ (the set of pairs of natural numbers $(m, n)$). The induction principle you want to use is justified by considering the lexicographic ordering on $X$: $(m, n) < (m', n')$ iff $m < m'$ or $m = m'$ and $n < n'$.
answered yesterday
Rob Arthan
27k42863
If $X$ is a set that is well-ordered by some ordering relation $<$, then you can prove a property $Q(x)$ by induction on $x$, by showing that for any $x in X$, if $Q(y)$ holds for every $y < x$, then $Q(x)$ holds.
This is called complete or course-of-values induction when $X$ is the natural numbers with the usual ordering. Peano's principle of induction for the natural numbers asking you to prove that $Q(0)$ holds and that for every $x in BbbN$, $Q(x + 1)$ holds if $Q(x)$ holds is a special case.
In your case, $X$ is $BbbNtimesBbbN$ (the set of pairs of natural numbers $(m, n)$). The induction principle you want to use is justified by considering the lexicographic ordering on $X$: $(m, n) < (m', n')$ iff $m < m'$ or $m = m'$ and $n < n'$.
answered yesterday
Rob Arthan
27k42863
answered yesterday
Rob Arthan
27k42863
answered yesterday
Rob Arthan
27k42863
answered yesterday
Rob Arthan
27k42863
27k42863
add a comment |Â
add a comment |Â
up vote
1
down vote
It is easier to figure out the answer by drawing a grid with the first few elements of $Bbb Ntimes Bbb N$.
Given the question you're asking, what you really want to do is proceed by squares: let $T(n)$ denote the proposition
$P(p,q)$ is true for all $p,q$ such that $pleq n$ and $qleq n$.
I claim that if you prove what you said, then you can prove that $T(n)implies T(n+1)$ for all $n$.
What you said you can prove is
$$[P(p,1), P(p,2),cdots P(p,q)]implies P(p+1,q)tag1$$
$$[P(p-1,q+1), P(p,q)] implies P(p,q+1)tag2$$
I'm assuming here that cases where $pleq 0$ or $qleq 0$ are considered vacuously true.
Now assume $T(n)$.
- By $(2)$, you can prove that $P(1,n+1)$ and then $P(p,n+1)$ for all $pleq n$.
- By applying $(1)$ to every $q$ between $1$ and $n+1$, you get $P(n+1,q)$ for all $qleq n+1$.
Hence $T(n+1)$ as claimed.
answered yesterday
Arnaud Mortier
17.7k21757
By 2, how $P(1, n+1)$ can be proved?
– hanugm
yesterday
To prove $P(1,n+1)$, we need $P(0,n+1)$ and $P(1,1)$, but we dont have $P(0,n+1)$. Isnt it?
– hanugm
yesterday
add a comment |Â
up vote
1
down vote
It is easier to figure out the answer by drawing a grid with the first few elements of $Bbb Ntimes Bbb N$.
Given the question you're asking, what you really want to do is proceed by squares: let $T(n)$ denote the proposition
$P(p,q)$ is true for all $p,q$ such that $pleq n$ and $qleq n$.
I claim that if you prove what you said, then you can prove that $T(n)implies T(n+1)$ for all $n$.
What you said you can prove is
$$[P(p,1), P(p,2),cdots P(p,q)]implies P(p+1,q)tag1$$
$$[P(p-1,q+1), P(p,q)] implies P(p,q+1)tag2$$
I'm assuming here that cases where $pleq 0$ or $qleq 0$ are considered vacuously true.
Now assume $T(n)$.
- By $(2)$, you can prove that $P(1,n+1)$ and then $P(p,n+1)$ for all $pleq n$.
- By applying $(1)$ to every $q$ between $1$ and $n+1$, you get $P(n+1,q)$ for all $qleq n+1$.
Hence $T(n+1)$ as claimed.
answered yesterday
Arnaud Mortier
17.7k21757
By 2, how $P(1, n+1)$ can be proved?
– hanugm
yesterday
To prove $P(1,n+1)$, we need $P(0,n+1)$ and $P(1,1)$, but we dont have $P(0,n+1)$. Isnt it?
– hanugm
yesterday
add a comment |Â
up vote
1
down vote
up vote
1
down vote
It is easier to figure out the answer by drawing a grid with the first few elements of $Bbb Ntimes Bbb N$.
Given the question you're asking, what you really want to do is proceed by squares: let $T(n)$ denote the proposition
$P(p,q)$ is true for all $p,q$ such that $pleq n$ and $qleq n$.
I claim that if you prove what you said, then you can prove that $T(n)implies T(n+1)$ for all $n$.
What you said you can prove is
$$[P(p,1), P(p,2),cdots P(p,q)]implies P(p+1,q)tag1$$
$$[P(p-1,q+1), P(p,q)] implies P(p,q+1)tag2$$
I'm assuming here that cases where $pleq 0$ or $qleq 0$ are considered vacuously true.
Now assume $T(n)$.
- By $(2)$, you can prove that $P(1,n+1)$ and then $P(p,n+1)$ for all $pleq n$.
- By applying $(1)$ to every $q$ between $1$ and $n+1$, you get $P(n+1,q)$ for all $qleq n+1$.
Hence $T(n+1)$ as claimed.
answered yesterday
Arnaud Mortier
17.7k21757
It is easier to figure out the answer by drawing a grid with the first few elements of $Bbb Ntimes Bbb N$.
Given the question you're asking, what you really want to do is proceed by squares: let $T(n)$ denote the proposition
$P(p,q)$ is true for all $p,q$ such that $pleq n$ and $qleq n$.
I claim that if you prove what you said, then you can prove that $T(n)implies T(n+1)$ for all $n$.
What you said you can prove is
$$[P(p,1), P(p,2),cdots P(p,q)]implies P(p+1,q)tag1$$
$$[P(p-1,q+1), P(p,q)] implies P(p,q+1)tag2$$
I'm assuming here that cases where $pleq 0$ or $qleq 0$ are considered vacuously true.
Now assume $T(n)$.
- By $(2)$, you can prove that $P(1,n+1)$ and then $P(p,n+1)$ for all $pleq n$.
- By applying $(1)$ to every $q$ between $1$ and $n+1$, you get $P(n+1,q)$ for all $qleq n+1$.
Hence $T(n+1)$ as claimed.
answered yesterday
Arnaud Mortier
17.7k21757
edited yesterday
answered yesterday
Arnaud Mortier
17.7k21757
answered yesterday
Arnaud Mortier
17.7k21757
answered yesterday
Arnaud Mortier
17.7k21757
17.7k21757
By 2, how $P(1, n+1)$ can be proved?
– hanugm
yesterday
To prove $P(1,n+1)$, we need $P(0,n+1)$ and $P(1,1)$, but we dont have $P(0,n+1)$. Isnt it?
– hanugm
yesterday
add a comment |Â
By 2, how $P(1, n+1)$ can be proved?
– hanugm
yesterday
To prove $P(1,n+1)$, we need $P(0,n+1)$ and $P(1,1)$, but we dont have $P(0,n+1)$. Isnt it?
– hanugm
yesterday
By 2, how $P(1, n+1)$ can be proved?
– hanugm
yesterday
By 2, how $P(1, n+1)$ can be proved?
– hanugm
yesterday
To prove $P(1,n+1)$, we need $P(0,n+1)$ and $P(1,1)$, but we dont have $P(0,n+1)$. Isnt it?
– hanugm
yesterday
To prove $P(1,n+1)$, we need $P(0,n+1)$ and $P(1,1)$, but we dont have $P(0,n+1)$. Isnt it?
– hanugm
yesterday
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%2f2872394%2fproof-using-mathematical-induction%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
1
$n$ must remain constant. Once you have proved $P(m,n)$ for a fixed $n$ then you can apply induction in the second argument.
– Dog_69
yesterday
In you prove $forallnP(1,n)$ and you prove $forallnP(m,n)impliesforallnP(m+1,n)$ you will have proved the theorem.
– saulspatz
yesterday
Exactly. The validity of your reasoning depends on this : can you prove 1) $P(1,n)$ true for all $n$, 2) $P(m,n)Longrightarrow P(m+1,n)$ for all $n$ ? If this is the case, then $n$ is merely a parameter in your induction. If not, then you have to build some sort of induction on $mathbb Ntimes mathbb N$, which can be quite tricky.
– Nicolas FRANCOIS
yesterday
@NicolasFRANCOIS Can I prove $P(m,n) implies P(m+1,n+1)$ without step 2 and 3?
– hanugm
yesterday
1
@hanugm : no, it's not enough. You lose $P(m,n+1)$ and $P(m+1,n)$.
– Nicolas FRANCOIS
yesterday