Mixing
Proving a conditional statement by induction
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
I’m a university freshman and I saw this in the lecture slides of my Discrete Mathematics module. I do not know what the name of the theorem is, so I will just copy the proof to the best of my ability.
Theorem: If p is a prime and $x_1, x_2,... x_n$ are any integers such that: $pmid x_1x_2...x_n$;
then $pmid x_i$ , for some $i ,; 1le ile n$.
Proof: by Induction
- Let $P(n) = ( (pmid x_1x_2...x_n) to (pmid x_itext for some i in[1,n]) )$
- Base case: $n = 1$
- Clearly, $P(1)$ is true.
- Inductive step: For any $k in Bbb Z^+ $:
- If $P(k)$ ie. $(pmid x_1x_2...x_k) to (pmid x_itext for some i in[1,k])$.
- Consider the case $k + 1$:
- Suppose $pmid x_1x_2...x_k+1 $:
- Let $A = x_1x_2...x_k$ , so that $pmid Ax_k+1 $.
- If $pmid A$:
- Then $pmid x_i$ for some $i in [1, k]$ by the inductive
hypothesis. So $P(k + 1)$ is true. - Else $p notmid A$:
- Then $gcd(p,A) = 1$, because $p$ is prime and $p notmid A$.
- Then there exist integers $r, s$ such that $pr + As = 1$ by
Bézout's Identity. - Now, $x_k+1 = 1cdot x_k+1 = (pr + As)x_k+1
= p(rx_k+1) + (Ax_k+1)s $ by basic algebra. - Since $p$ divides both terms, it divides their
linear combination by Theorem 4.1.1. [For all $ a, b, c in Bbb Z$, if $amid b$ & $amid c$, then for all $x,y in Bbb Z$, $amid(bx + cy)$] - Thus, $pmid x_k+1$ and $P(k + 1)$ is true.
- Hence, by mathematical induction, the theorem is true.
Judging from the given proof, I would think in line 9 onwards, there is 2 cases we should consider(I would have stopped at line 10 and assume $P(k+1)$ is true if I wrote the proof myself). My question would be what is so special about this proof that we need to consider an (if-else) structure for it. Pardon my ignorance about induction as I only have used induction on Mathematical functions like summations from high school.
PS: New to Latex as well. Don't know how to write not | and subscript things like (k+1), see line 7,8,11,12,14,16. Would anyone kindly edit it for me so that I learn from my mistakes? Sorry for the confusion caused.
logic proof-writing induction
edited Jul 22 at 14:07
Bernard
110k635103
asked Jul 22 at 13:48
Prashin Jeevaganth
113
 |Â
show 3 more comments
up vote
2
down vote
favorite
I’m a university freshman and I saw this in the lecture slides of my Discrete Mathematics module. I do not know what the name of the theorem is, so I will just copy the proof to the best of my ability.
Theorem: If p is a prime and $x_1, x_2,... x_n$ are any integers such that: $pmid x_1x_2...x_n$;
then $pmid x_i$ , for some $i ,; 1le ile n$.
Proof: by Induction
- Let $P(n) = ( (pmid x_1x_2...x_n) to (pmid x_itext for some i in[1,n]) )$
- Base case: $n = 1$
- Clearly, $P(1)$ is true.
- Inductive step: For any $k in Bbb Z^+ $:
- If $P(k)$ ie. $(pmid x_1x_2...x_k) to (pmid x_itext for some i in[1,k])$.
- Consider the case $k + 1$:
- Suppose $pmid x_1x_2...x_k+1 $:
- Let $A = x_1x_2...x_k$ , so that $pmid Ax_k+1 $.
- If $pmid A$:
- Then $pmid x_i$ for some $i in [1, k]$ by the inductive
hypothesis. So $P(k + 1)$ is true. - Else $p notmid A$:
- Then $gcd(p,A) = 1$, because $p$ is prime and $p notmid A$.
- Then there exist integers $r, s$ such that $pr + As = 1$ by
Bézout's Identity. - Now, $x_k+1 = 1cdot x_k+1 = (pr + As)x_k+1
= p(rx_k+1) + (Ax_k+1)s $ by basic algebra. - Since $p$ divides both terms, it divides their
linear combination by Theorem 4.1.1. [For all $ a, b, c in Bbb Z$, if $amid b$ & $amid c$, then for all $x,y in Bbb Z$, $amid(bx + cy)$] - Thus, $pmid x_k+1$ and $P(k + 1)$ is true.
- Hence, by mathematical induction, the theorem is true.
Judging from the given proof, I would think in line 9 onwards, there is 2 cases we should consider(I would have stopped at line 10 and assume $P(k+1)$ is true if I wrote the proof myself). My question would be what is so special about this proof that we need to consider an (if-else) structure for it. Pardon my ignorance about induction as I only have used induction on Mathematical functions like summations from high school.
PS: New to Latex as well. Don't know how to write not | and subscript things like (k+1), see line 7,8,11,12,14,16. Would anyone kindly edit it for me so that I learn from my mistakes? Sorry for the confusion caused.
logic proof-writing induction
edited Jul 22 at 14:07
Bernard
110k635103
asked Jul 22 at 13:48
Prashin Jeevaganth
113
Just put the subscript in braces:x_k+1gives $x_k+1$
– saulspatz
Jul 22 at 13:55
I keep trying to edit it but you post an edit and forestall me. Stop editing it and I'll fix it.
– saulspatz
Jul 22 at 14:04
Sorry about that @saulspatz , saw ur comment and tried editing immediately, thanks for ur initiative.
– Prashin Jeevaganth
Jul 22 at 14:07
The symbol for ‘divides’ is obtained by the commandmid.
– Bernard
Jul 22 at 14:09
1
@Peteranmid bgives $anmid b$. If you right-click on a formula you get a pop-up that says "Show Math As" and then if you pick "TeX commands" you'll see the TeX commands that you just need to put inside $ signs. This has helped me a lot. Try it.
– saulspatz
Jul 22 at 14:20
 |Â
show 3 more comments
up vote
2
down vote
favorite
up vote
2
down vote
favorite
I’m a university freshman and I saw this in the lecture slides of my Discrete Mathematics module. I do not know what the name of the theorem is, so I will just copy the proof to the best of my ability.
Theorem: If p is a prime and $x_1, x_2,... x_n$ are any integers such that: $pmid x_1x_2...x_n$;
then $pmid x_i$ , for some $i ,; 1le ile n$.
Proof: by Induction
- Let $P(n) = ( (pmid x_1x_2...x_n) to (pmid x_itext for some i in[1,n]) )$
- Base case: $n = 1$
- Clearly, $P(1)$ is true.
- Inductive step: For any $k in Bbb Z^+ $:
- If $P(k)$ ie. $(pmid x_1x_2...x_k) to (pmid x_itext for some i in[1,k])$.
- Consider the case $k + 1$:
- Suppose $pmid x_1x_2...x_k+1 $:
- Let $A = x_1x_2...x_k$ , so that $pmid Ax_k+1 $.
- If $pmid A$:
- Then $pmid x_i$ for some $i in [1, k]$ by the inductive
hypothesis. So $P(k + 1)$ is true. - Else $p notmid A$:
- Then $gcd(p,A) = 1$, because $p$ is prime and $p notmid A$.
- Then there exist integers $r, s$ such that $pr + As = 1$ by
Bézout's Identity. - Now, $x_k+1 = 1cdot x_k+1 = (pr + As)x_k+1
= p(rx_k+1) + (Ax_k+1)s $ by basic algebra. - Since $p$ divides both terms, it divides their
linear combination by Theorem 4.1.1. [For all $ a, b, c in Bbb Z$, if $amid b$ & $amid c$, then for all $x,y in Bbb Z$, $amid(bx + cy)$] - Thus, $pmid x_k+1$ and $P(k + 1)$ is true.
- Hence, by mathematical induction, the theorem is true.
Judging from the given proof, I would think in line 9 onwards, there is 2 cases we should consider(I would have stopped at line 10 and assume $P(k+1)$ is true if I wrote the proof myself). My question would be what is so special about this proof that we need to consider an (if-else) structure for it. Pardon my ignorance about induction as I only have used induction on Mathematical functions like summations from high school.
PS: New to Latex as well. Don't know how to write not | and subscript things like (k+1), see line 7,8,11,12,14,16. Would anyone kindly edit it for me so that I learn from my mistakes? Sorry for the confusion caused.
logic proof-writing induction
edited Jul 22 at 14:07
Bernard
110k635103
asked Jul 22 at 13:48
Prashin Jeevaganth
113
I’m a university freshman and I saw this in the lecture slides of my Discrete Mathematics module. I do not know what the name of the theorem is, so I will just copy the proof to the best of my ability.
Theorem: If p is a prime and $x_1, x_2,... x_n$ are any integers such that: $pmid x_1x_2...x_n$;
then $pmid x_i$ , for some $i ,; 1le ile n$.
Proof: by Induction
- Let $P(n) = ( (pmid x_1x_2...x_n) to (pmid x_itext for some i in[1,n]) )$
- Base case: $n = 1$
- Clearly, $P(1)$ is true.
- Inductive step: For any $k in Bbb Z^+ $:
- If $P(k)$ ie. $(pmid x_1x_2...x_k) to (pmid x_itext for some i in[1,k])$.
- Consider the case $k + 1$:
- Suppose $pmid x_1x_2...x_k+1 $:
- Let $A = x_1x_2...x_k$ , so that $pmid Ax_k+1 $.
- If $pmid A$:
- Then $pmid x_i$ for some $i in [1, k]$ by the inductive
hypothesis. So $P(k + 1)$ is true. - Else $p notmid A$:
- Then $gcd(p,A) = 1$, because $p$ is prime and $p notmid A$.
- Then there exist integers $r, s$ such that $pr + As = 1$ by
Bézout's Identity. - Now, $x_k+1 = 1cdot x_k+1 = (pr + As)x_k+1
= p(rx_k+1) + (Ax_k+1)s $ by basic algebra. - Since $p$ divides both terms, it divides their
linear combination by Theorem 4.1.1. [For all $ a, b, c in Bbb Z$, if $amid b$ & $amid c$, then for all $x,y in Bbb Z$, $amid(bx + cy)$] - Thus, $pmid x_k+1$ and $P(k + 1)$ is true.
- Hence, by mathematical induction, the theorem is true.
Judging from the given proof, I would think in line 9 onwards, there is 2 cases we should consider(I would have stopped at line 10 and assume $P(k+1)$ is true if I wrote the proof myself). My question would be what is so special about this proof that we need to consider an (if-else) structure for it. Pardon my ignorance about induction as I only have used induction on Mathematical functions like summations from high school.
PS: New to Latex as well. Don't know how to write not | and subscript things like (k+1), see line 7,8,11,12,14,16. Would anyone kindly edit it for me so that I learn from my mistakes? Sorry for the confusion caused.
logic proof-writing induction
edited Jul 22 at 14:07
Bernard
110k635103
asked Jul 22 at 13:48
Prashin Jeevaganth
113
edited Jul 22 at 14:07
Bernard
110k635103
edited Jul 22 at 14:07
Bernard
110k635103
edited Jul 22 at 14:07
Bernard
110k635103
110k635103
asked Jul 22 at 13:48
Prashin Jeevaganth
113
asked Jul 22 at 13:48
Prashin Jeevaganth
113
asked Jul 22 at 13:48
Prashin Jeevaganth
113
113
Just put the subscript in braces:x_k+1gives $x_k+1$
– saulspatz
Jul 22 at 13:55
I keep trying to edit it but you post an edit and forestall me. Stop editing it and I'll fix it.
– saulspatz
Jul 22 at 14:04
Sorry about that @saulspatz , saw ur comment and tried editing immediately, thanks for ur initiative.
– Prashin Jeevaganth
Jul 22 at 14:07
The symbol for ‘divides’ is obtained by the commandmid.
– Bernard
Jul 22 at 14:09
1
@Peteranmid bgives $anmid b$. If you right-click on a formula you get a pop-up that says "Show Math As" and then if you pick "TeX commands" you'll see the TeX commands that you just need to put inside $ signs. This has helped me a lot. Try it.
– saulspatz
Jul 22 at 14:20
 |Â
show 3 more comments
Just put the subscript in braces:x_k+1gives $x_k+1$
– saulspatz
Jul 22 at 13:55
I keep trying to edit it but you post an edit and forestall me. Stop editing it and I'll fix it.
– saulspatz
Jul 22 at 14:04
Sorry about that @saulspatz , saw ur comment and tried editing immediately, thanks for ur initiative.
– Prashin Jeevaganth
Jul 22 at 14:07
The symbol for ‘divides’ is obtained by the commandmid.
– Bernard
Jul 22 at 14:09
1
@Peteranmid bgives $anmid b$. If you right-click on a formula you get a pop-up that says "Show Math As" and then if you pick "TeX commands" you'll see the TeX commands that you just need to put inside $ signs. This has helped me a lot. Try it.
– saulspatz
Jul 22 at 14:20
Just put the subscript in braces:
x_k+1 gives $x_k+1$– saulspatz
Jul 22 at 13:55
Just put the subscript in braces:
x_k+1 gives $x_k+1$– saulspatz
Jul 22 at 13:55
I keep trying to edit it but you post an edit and forestall me. Stop editing it and I'll fix it.
– saulspatz
Jul 22 at 14:04
I keep trying to edit it but you post an edit and forestall me. Stop editing it and I'll fix it.
– saulspatz
Jul 22 at 14:04
Sorry about that @saulspatz , saw ur comment and tried editing immediately, thanks for ur initiative.
– Prashin Jeevaganth
Jul 22 at 14:07
Sorry about that @saulspatz , saw ur comment and tried editing immediately, thanks for ur initiative.
– Prashin Jeevaganth
Jul 22 at 14:07
The symbol for ‘divides’ is obtained by the command
mid.– Bernard
Jul 22 at 14:09
The symbol for ‘divides’ is obtained by the command
mid.– Bernard
Jul 22 at 14:09
1
1
@Peter
anmid b gives $anmid b$. If you right-click on a formula you get a pop-up that says "Show Math As" and then if you pick "TeX commands" you'll see the TeX commands that you just need to put inside $ signs. This has helped me a lot. Try it.– saulspatz
Jul 22 at 14:20
@Peter
anmid b gives $anmid b$. If you right-click on a formula you get a pop-up that says "Show Math As" and then if you pick "TeX commands" you'll see the TeX commands that you just need to put inside $ signs. This has helped me a lot. Try it.– saulspatz
Jul 22 at 14:20
 |Â
show 3 more comments
3 Answers
3
active
oldest
votes
up vote
1
down vote
All that has been shown by line 10 is that if $p|A$ the the theorem is true. But we don't know that $p|A$. All we know is that $p|Ax_k+1,$ and so we also have to consider the case that $pnmid A.$
Having said that, I think most people would structure this proof differently. First prove by Bezout's identity that if $p|ab$ then $p|a text or p|b$ then prove that it's true for any number of factors by induction.
answered Jul 22 at 14:17
saulspatz
10.5k21323
Oh I think I saw something. Do u mean that even though we assumed that P(k) is true from the inductive step(which is the entire conditional statement), we do not know the truth value for the hypothesis, hence there are 2 cases, and to prove that a conditional statement is True, we have to prove that the conclusion of the conditional statement is True for both True and False values of the hypothesis.
– Prashin Jeevaganth
Jul 22 at 14:28
I don't know what you mean by "the hypothesis." There are a lot of different hypotheses floating around. (You never have to prove that anything is true for a false value of a hypothesis, though. A false statement implies anything.) You have to prove the conclusion is true if the hypothesis is true, just as in the proof of every theorem. In this particular example, it's a proof by cases.
– saulspatz
Jul 22 at 17:58
add a comment |Â
up vote
0
down vote
The key is that the base case was $n =1$. Not $n= 2$. And.... it's easier if I were to explain how I would have done it.
I'd start with base case $n=1$ so $p|x_1$ then $p|x_1$.
Then I'd do a second base case $n=2$ and prove if $p|x_1x_2$ then $p|x_1$ or $p|x_2$ and .... I'd basically do the stuff from step 12 on.
Now what I can't do is: Show it true for base case $n=1$ and then say: Well, I assumed it was true for $n=k$ and then for $n=k+1$ it is then $x_1....x_kx_k+1 = (x_1....x_k)(x_k+1)$ and that's really just two numbers so it is true that $p|(x_1....x_k)$ or $p|x_k+1$.
I can't say that because we haven't proven it for $2$ numbers! We proved (well, demonstrated) it for a base case of $1$! Not $2$!.
I must say this is kind of a weird in that the induction is used to dismiss the larger cases and the gyst is proving the case for two numbers. Normally that would be done by taking the base case of two and proving it in the base case.
====
This taking a proper base case is important. There's a famous false proof that all horses in a field are the same color. (I first heard it as marbles in a bag.)
Thats true for $n =1$.
If you assume it is true for $n= k$ then if you have a field of $n=k$ horse they are the same color. Walk a $k+1$th horse up to your field. Remove one of your old horses. The remaining horses are the same color. Put the new horse in. Youu have $n=k$ horses so the new horse must be the same color as all the old horses. Put the other horse back in and you have $n=k+1$ horses and they are all the same color.
Note: That in you base case $n= 1$ then that sentence the remaining horses are the same color refers to $n-1 = 0$ horses! There are no horses for the new horse to assimilate to. The new horse is the same color but it doesn't need to be the same color of the removed horse because once you remove the old horse there are no horses left to stay the original color.
answered Jul 22 at 16:17
fleablood
60.4k22575
add a comment |Â
up vote
0
down vote
Let $(x_k)_kinBbb N^+$ be any finite sequence of integers, $p$ be any prime integer, and $n$ be any positive integer.
let $X_n := prodlimits_kin [n]^+ x_k$ be the product of the first $n$ terms of that sequence.
Let $P(n)$ state that $(pmid X_n )toexists iin[n]^+:(pmid x_i)$ . Â That says: If $p$ is a factor of a product of a finite sequence integers, then it is a factor of at least one from the sequence.
Trivially, $P(1)$ does clearly hold. Â Because $X_1=x_1$ therefore $(pmid X_1)to exists iin[1]^+:(pmid x_i)$.
Assume $P(n)$ holds for any positive integer $n$.
Assume $(pmid X_n)$ or $(pmid x_n+1)$.
You need to use proof by cases to derive $exists iin[n+1]^+:(pmid x_i)$.- From that you may derive $(pmid X_nx_n+1)to exists iin[n+1]^+:(pmid x_i)$ .
- That is $P(n+1)$ can be derived from assuming $P(n)$ and either $(pmid X_n)$ or $(pmid x_n+1)$.
Assume $(pnmid X_n)$ and $(pnmid x_n+1)$.
You need to derive $negexists iin[n+1]^+:(pmid x_i)$ from the assumptions.- From you may derive $(pmid X_nx_n+1)to exists iin[n+1]^+:(pmid x_i)$
- That is $P(n+1)$ can be derived from assuming $P(n)$ and both $(pnmid X_n)$ and $(pnmid x_n+1)$.
That is $P(n+1)$ can be derived from assuming $P(n)$ in both the above. Do so.
Therefore $forall ngeq 1: (P(n)to P(n+1))$
$[n]^+=kinBbb N^+: kleq n$
answered Jul 23 at 5:09
Graham Kemp
80.1k43275
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
All that has been shown by line 10 is that if $p|A$ the the theorem is true. But we don't know that $p|A$. All we know is that $p|Ax_k+1,$ and so we also have to consider the case that $pnmid A.$
Having said that, I think most people would structure this proof differently. First prove by Bezout's identity that if $p|ab$ then $p|a text or p|b$ then prove that it's true for any number of factors by induction.
answered Jul 22 at 14:17
saulspatz
10.5k21323
Oh I think I saw something. Do u mean that even though we assumed that P(k) is true from the inductive step(which is the entire conditional statement), we do not know the truth value for the hypothesis, hence there are 2 cases, and to prove that a conditional statement is True, we have to prove that the conclusion of the conditional statement is True for both True and False values of the hypothesis.
– Prashin Jeevaganth
Jul 22 at 14:28
I don't know what you mean by "the hypothesis." There are a lot of different hypotheses floating around. (You never have to prove that anything is true for a false value of a hypothesis, though. A false statement implies anything.) You have to prove the conclusion is true if the hypothesis is true, just as in the proof of every theorem. In this particular example, it's a proof by cases.
– saulspatz
Jul 22 at 17:58
add a comment |Â
up vote
1
down vote
All that has been shown by line 10 is that if $p|A$ the the theorem is true. But we don't know that $p|A$. All we know is that $p|Ax_k+1,$ and so we also have to consider the case that $pnmid A.$
Having said that, I think most people would structure this proof differently. First prove by Bezout's identity that if $p|ab$ then $p|a text or p|b$ then prove that it's true for any number of factors by induction.
answered Jul 22 at 14:17
saulspatz
10.5k21323
Oh I think I saw something. Do u mean that even though we assumed that P(k) is true from the inductive step(which is the entire conditional statement), we do not know the truth value for the hypothesis, hence there are 2 cases, and to prove that a conditional statement is True, we have to prove that the conclusion of the conditional statement is True for both True and False values of the hypothesis.
– Prashin Jeevaganth
Jul 22 at 14:28
I don't know what you mean by "the hypothesis." There are a lot of different hypotheses floating around. (You never have to prove that anything is true for a false value of a hypothesis, though. A false statement implies anything.) You have to prove the conclusion is true if the hypothesis is true, just as in the proof of every theorem. In this particular example, it's a proof by cases.
– saulspatz
Jul 22 at 17:58
add a comment |Â
up vote
1
down vote
up vote
1
down vote
All that has been shown by line 10 is that if $p|A$ the the theorem is true. But we don't know that $p|A$. All we know is that $p|Ax_k+1,$ and so we also have to consider the case that $pnmid A.$
Having said that, I think most people would structure this proof differently. First prove by Bezout's identity that if $p|ab$ then $p|a text or p|b$ then prove that it's true for any number of factors by induction.
answered Jul 22 at 14:17
saulspatz
10.5k21323
All that has been shown by line 10 is that if $p|A$ the the theorem is true. But we don't know that $p|A$. All we know is that $p|Ax_k+1,$ and so we also have to consider the case that $pnmid A.$
Having said that, I think most people would structure this proof differently. First prove by Bezout's identity that if $p|ab$ then $p|a text or p|b$ then prove that it's true for any number of factors by induction.
answered Jul 22 at 14:17
saulspatz
10.5k21323
answered Jul 22 at 14:17
saulspatz
10.5k21323
answered Jul 22 at 14:17
saulspatz
10.5k21323
answered Jul 22 at 14:17
saulspatz
10.5k21323
10.5k21323
Oh I think I saw something. Do u mean that even though we assumed that P(k) is true from the inductive step(which is the entire conditional statement), we do not know the truth value for the hypothesis, hence there are 2 cases, and to prove that a conditional statement is True, we have to prove that the conclusion of the conditional statement is True for both True and False values of the hypothesis.
– Prashin Jeevaganth
Jul 22 at 14:28
I don't know what you mean by "the hypothesis." There are a lot of different hypotheses floating around. (You never have to prove that anything is true for a false value of a hypothesis, though. A false statement implies anything.) You have to prove the conclusion is true if the hypothesis is true, just as in the proof of every theorem. In this particular example, it's a proof by cases.
– saulspatz
Jul 22 at 17:58
add a comment |Â
Oh I think I saw something. Do u mean that even though we assumed that P(k) is true from the inductive step(which is the entire conditional statement), we do not know the truth value for the hypothesis, hence there are 2 cases, and to prove that a conditional statement is True, we have to prove that the conclusion of the conditional statement is True for both True and False values of the hypothesis.
– Prashin Jeevaganth
Jul 22 at 14:28
I don't know what you mean by "the hypothesis." There are a lot of different hypotheses floating around. (You never have to prove that anything is true for a false value of a hypothesis, though. A false statement implies anything.) You have to prove the conclusion is true if the hypothesis is true, just as in the proof of every theorem. In this particular example, it's a proof by cases.
– saulspatz
Jul 22 at 17:58
Oh I think I saw something. Do u mean that even though we assumed that P(k) is true from the inductive step(which is the entire conditional statement), we do not know the truth value for the hypothesis, hence there are 2 cases, and to prove that a conditional statement is True, we have to prove that the conclusion of the conditional statement is True for both True and False values of the hypothesis.
– Prashin Jeevaganth
Jul 22 at 14:28
Oh I think I saw something. Do u mean that even though we assumed that P(k) is true from the inductive step(which is the entire conditional statement), we do not know the truth value for the hypothesis, hence there are 2 cases, and to prove that a conditional statement is True, we have to prove that the conclusion of the conditional statement is True for both True and False values of the hypothesis.
– Prashin Jeevaganth
Jul 22 at 14:28
I don't know what you mean by "the hypothesis." There are a lot of different hypotheses floating around. (You never have to prove that anything is true for a false value of a hypothesis, though. A false statement implies anything.) You have to prove the conclusion is true if the hypothesis is true, just as in the proof of every theorem. In this particular example, it's a proof by cases.
– saulspatz
Jul 22 at 17:58
I don't know what you mean by "the hypothesis." There are a lot of different hypotheses floating around. (You never have to prove that anything is true for a false value of a hypothesis, though. A false statement implies anything.) You have to prove the conclusion is true if the hypothesis is true, just as in the proof of every theorem. In this particular example, it's a proof by cases.
– saulspatz
Jul 22 at 17:58
add a comment |Â
up vote
0
down vote
The key is that the base case was $n =1$. Not $n= 2$. And.... it's easier if I were to explain how I would have done it.
I'd start with base case $n=1$ so $p|x_1$ then $p|x_1$.
Then I'd do a second base case $n=2$ and prove if $p|x_1x_2$ then $p|x_1$ or $p|x_2$ and .... I'd basically do the stuff from step 12 on.
Now what I can't do is: Show it true for base case $n=1$ and then say: Well, I assumed it was true for $n=k$ and then for $n=k+1$ it is then $x_1....x_kx_k+1 = (x_1....x_k)(x_k+1)$ and that's really just two numbers so it is true that $p|(x_1....x_k)$ or $p|x_k+1$.
I can't say that because we haven't proven it for $2$ numbers! We proved (well, demonstrated) it for a base case of $1$! Not $2$!.
I must say this is kind of a weird in that the induction is used to dismiss the larger cases and the gyst is proving the case for two numbers. Normally that would be done by taking the base case of two and proving it in the base case.
====
This taking a proper base case is important. There's a famous false proof that all horses in a field are the same color. (I first heard it as marbles in a bag.)
Thats true for $n =1$.
If you assume it is true for $n= k$ then if you have a field of $n=k$ horse they are the same color. Walk a $k+1$th horse up to your field. Remove one of your old horses. The remaining horses are the same color. Put the new horse in. Youu have $n=k$ horses so the new horse must be the same color as all the old horses. Put the other horse back in and you have $n=k+1$ horses and they are all the same color.
Note: That in you base case $n= 1$ then that sentence the remaining horses are the same color refers to $n-1 = 0$ horses! There are no horses for the new horse to assimilate to. The new horse is the same color but it doesn't need to be the same color of the removed horse because once you remove the old horse there are no horses left to stay the original color.
answered Jul 22 at 16:17
fleablood
60.4k22575
add a comment |Â
up vote
0
down vote
The key is that the base case was $n =1$. Not $n= 2$. And.... it's easier if I were to explain how I would have done it.
I'd start with base case $n=1$ so $p|x_1$ then $p|x_1$.
Then I'd do a second base case $n=2$ and prove if $p|x_1x_2$ then $p|x_1$ or $p|x_2$ and .... I'd basically do the stuff from step 12 on.
Now what I can't do is: Show it true for base case $n=1$ and then say: Well, I assumed it was true for $n=k$ and then for $n=k+1$ it is then $x_1....x_kx_k+1 = (x_1....x_k)(x_k+1)$ and that's really just two numbers so it is true that $p|(x_1....x_k)$ or $p|x_k+1$.
I can't say that because we haven't proven it for $2$ numbers! We proved (well, demonstrated) it for a base case of $1$! Not $2$!.
I must say this is kind of a weird in that the induction is used to dismiss the larger cases and the gyst is proving the case for two numbers. Normally that would be done by taking the base case of two and proving it in the base case.
====
This taking a proper base case is important. There's a famous false proof that all horses in a field are the same color. (I first heard it as marbles in a bag.)
Thats true for $n =1$.
If you assume it is true for $n= k$ then if you have a field of $n=k$ horse they are the same color. Walk a $k+1$th horse up to your field. Remove one of your old horses. The remaining horses are the same color. Put the new horse in. Youu have $n=k$ horses so the new horse must be the same color as all the old horses. Put the other horse back in and you have $n=k+1$ horses and they are all the same color.
Note: That in you base case $n= 1$ then that sentence the remaining horses are the same color refers to $n-1 = 0$ horses! There are no horses for the new horse to assimilate to. The new horse is the same color but it doesn't need to be the same color of the removed horse because once you remove the old horse there are no horses left to stay the original color.
answered Jul 22 at 16:17
fleablood
60.4k22575
add a comment |Â
up vote
0
down vote
up vote
0
down vote
The key is that the base case was $n =1$. Not $n= 2$. And.... it's easier if I were to explain how I would have done it.
I'd start with base case $n=1$ so $p|x_1$ then $p|x_1$.
Then I'd do a second base case $n=2$ and prove if $p|x_1x_2$ then $p|x_1$ or $p|x_2$ and .... I'd basically do the stuff from step 12 on.
Now what I can't do is: Show it true for base case $n=1$ and then say: Well, I assumed it was true for $n=k$ and then for $n=k+1$ it is then $x_1....x_kx_k+1 = (x_1....x_k)(x_k+1)$ and that's really just two numbers so it is true that $p|(x_1....x_k)$ or $p|x_k+1$.
I can't say that because we haven't proven it for $2$ numbers! We proved (well, demonstrated) it for a base case of $1$! Not $2$!.
I must say this is kind of a weird in that the induction is used to dismiss the larger cases and the gyst is proving the case for two numbers. Normally that would be done by taking the base case of two and proving it in the base case.
====
This taking a proper base case is important. There's a famous false proof that all horses in a field are the same color. (I first heard it as marbles in a bag.)
Thats true for $n =1$.
If you assume it is true for $n= k$ then if you have a field of $n=k$ horse they are the same color. Walk a $k+1$th horse up to your field. Remove one of your old horses. The remaining horses are the same color. Put the new horse in. Youu have $n=k$ horses so the new horse must be the same color as all the old horses. Put the other horse back in and you have $n=k+1$ horses and they are all the same color.
Note: That in you base case $n= 1$ then that sentence the remaining horses are the same color refers to $n-1 = 0$ horses! There are no horses for the new horse to assimilate to. The new horse is the same color but it doesn't need to be the same color of the removed horse because once you remove the old horse there are no horses left to stay the original color.
answered Jul 22 at 16:17
fleablood
60.4k22575
The key is that the base case was $n =1$. Not $n= 2$. And.... it's easier if I were to explain how I would have done it.
I'd start with base case $n=1$ so $p|x_1$ then $p|x_1$.
Then I'd do a second base case $n=2$ and prove if $p|x_1x_2$ then $p|x_1$ or $p|x_2$ and .... I'd basically do the stuff from step 12 on.
Now what I can't do is: Show it true for base case $n=1$ and then say: Well, I assumed it was true for $n=k$ and then for $n=k+1$ it is then $x_1....x_kx_k+1 = (x_1....x_k)(x_k+1)$ and that's really just two numbers so it is true that $p|(x_1....x_k)$ or $p|x_k+1$.
I can't say that because we haven't proven it for $2$ numbers! We proved (well, demonstrated) it for a base case of $1$! Not $2$!.
I must say this is kind of a weird in that the induction is used to dismiss the larger cases and the gyst is proving the case for two numbers. Normally that would be done by taking the base case of two and proving it in the base case.
====
This taking a proper base case is important. There's a famous false proof that all horses in a field are the same color. (I first heard it as marbles in a bag.)
Thats true for $n =1$.
If you assume it is true for $n= k$ then if you have a field of $n=k$ horse they are the same color. Walk a $k+1$th horse up to your field. Remove one of your old horses. The remaining horses are the same color. Put the new horse in. Youu have $n=k$ horses so the new horse must be the same color as all the old horses. Put the other horse back in and you have $n=k+1$ horses and they are all the same color.
Note: That in you base case $n= 1$ then that sentence the remaining horses are the same color refers to $n-1 = 0$ horses! There are no horses for the new horse to assimilate to. The new horse is the same color but it doesn't need to be the same color of the removed horse because once you remove the old horse there are no horses left to stay the original color.
answered Jul 22 at 16:17
fleablood
60.4k22575
answered Jul 22 at 16:17
fleablood
60.4k22575
answered Jul 22 at 16:17
fleablood
60.4k22575
answered Jul 22 at 16:17
fleablood
60.4k22575
60.4k22575
add a comment |Â
add a comment |Â
up vote
0
down vote
Let $(x_k)_kinBbb N^+$ be any finite sequence of integers, $p$ be any prime integer, and $n$ be any positive integer.
let $X_n := prodlimits_kin [n]^+ x_k$ be the product of the first $n$ terms of that sequence.
Let $P(n)$ state that $(pmid X_n )toexists iin[n]^+:(pmid x_i)$ . Â That says: If $p$ is a factor of a product of a finite sequence integers, then it is a factor of at least one from the sequence.
Trivially, $P(1)$ does clearly hold. Â Because $X_1=x_1$ therefore $(pmid X_1)to exists iin[1]^+:(pmid x_i)$.
Assume $P(n)$ holds for any positive integer $n$.
Assume $(pmid X_n)$ or $(pmid x_n+1)$.
You need to use proof by cases to derive $exists iin[n+1]^+:(pmid x_i)$.- From that you may derive $(pmid X_nx_n+1)to exists iin[n+1]^+:(pmid x_i)$ .
- That is $P(n+1)$ can be derived from assuming $P(n)$ and either $(pmid X_n)$ or $(pmid x_n+1)$.
Assume $(pnmid X_n)$ and $(pnmid x_n+1)$.
You need to derive $negexists iin[n+1]^+:(pmid x_i)$ from the assumptions.- From you may derive $(pmid X_nx_n+1)to exists iin[n+1]^+:(pmid x_i)$
- That is $P(n+1)$ can be derived from assuming $P(n)$ and both $(pnmid X_n)$ and $(pnmid x_n+1)$.
That is $P(n+1)$ can be derived from assuming $P(n)$ in both the above. Do so.
Therefore $forall ngeq 1: (P(n)to P(n+1))$
$[n]^+=kinBbb N^+: kleq n$
answered Jul 23 at 5:09
Graham Kemp
80.1k43275
add a comment |Â
up vote
0
down vote
Let $(x_k)_kinBbb N^+$ be any finite sequence of integers, $p$ be any prime integer, and $n$ be any positive integer.
let $X_n := prodlimits_kin [n]^+ x_k$ be the product of the first $n$ terms of that sequence.
Let $P(n)$ state that $(pmid X_n )toexists iin[n]^+:(pmid x_i)$ . Â That says: If $p$ is a factor of a product of a finite sequence integers, then it is a factor of at least one from the sequence.
Trivially, $P(1)$ does clearly hold. Â Because $X_1=x_1$ therefore $(pmid X_1)to exists iin[1]^+:(pmid x_i)$.
Assume $P(n)$ holds for any positive integer $n$.
Assume $(pmid X_n)$ or $(pmid x_n+1)$.
You need to use proof by cases to derive $exists iin[n+1]^+:(pmid x_i)$.- From that you may derive $(pmid X_nx_n+1)to exists iin[n+1]^+:(pmid x_i)$ .
- That is $P(n+1)$ can be derived from assuming $P(n)$ and either $(pmid X_n)$ or $(pmid x_n+1)$.
Assume $(pnmid X_n)$ and $(pnmid x_n+1)$.
You need to derive $negexists iin[n+1]^+:(pmid x_i)$ from the assumptions.- From you may derive $(pmid X_nx_n+1)to exists iin[n+1]^+:(pmid x_i)$
- That is $P(n+1)$ can be derived from assuming $P(n)$ and both $(pnmid X_n)$ and $(pnmid x_n+1)$.
That is $P(n+1)$ can be derived from assuming $P(n)$ in both the above. Do so.
Therefore $forall ngeq 1: (P(n)to P(n+1))$
$[n]^+=kinBbb N^+: kleq n$
answered Jul 23 at 5:09
Graham Kemp
80.1k43275
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Let $(x_k)_kinBbb N^+$ be any finite sequence of integers, $p$ be any prime integer, and $n$ be any positive integer.
let $X_n := prodlimits_kin [n]^+ x_k$ be the product of the first $n$ terms of that sequence.
Let $P(n)$ state that $(pmid X_n )toexists iin[n]^+:(pmid x_i)$ . Â That says: If $p$ is a factor of a product of a finite sequence integers, then it is a factor of at least one from the sequence.
Trivially, $P(1)$ does clearly hold. Â Because $X_1=x_1$ therefore $(pmid X_1)to exists iin[1]^+:(pmid x_i)$.
Assume $P(n)$ holds for any positive integer $n$.
Assume $(pmid X_n)$ or $(pmid x_n+1)$.
You need to use proof by cases to derive $exists iin[n+1]^+:(pmid x_i)$.- From that you may derive $(pmid X_nx_n+1)to exists iin[n+1]^+:(pmid x_i)$ .
- That is $P(n+1)$ can be derived from assuming $P(n)$ and either $(pmid X_n)$ or $(pmid x_n+1)$.
Assume $(pnmid X_n)$ and $(pnmid x_n+1)$.
You need to derive $negexists iin[n+1]^+:(pmid x_i)$ from the assumptions.- From you may derive $(pmid X_nx_n+1)to exists iin[n+1]^+:(pmid x_i)$
- That is $P(n+1)$ can be derived from assuming $P(n)$ and both $(pnmid X_n)$ and $(pnmid x_n+1)$.
That is $P(n+1)$ can be derived from assuming $P(n)$ in both the above. Do so.
Therefore $forall ngeq 1: (P(n)to P(n+1))$
$[n]^+=kinBbb N^+: kleq n$
answered Jul 23 at 5:09
Graham Kemp
80.1k43275
Let $(x_k)_kinBbb N^+$ be any finite sequence of integers, $p$ be any prime integer, and $n$ be any positive integer.
let $X_n := prodlimits_kin [n]^+ x_k$ be the product of the first $n$ terms of that sequence.
Let $P(n)$ state that $(pmid X_n )toexists iin[n]^+:(pmid x_i)$ . Â That says: If $p$ is a factor of a product of a finite sequence integers, then it is a factor of at least one from the sequence.
Trivially, $P(1)$ does clearly hold. Â Because $X_1=x_1$ therefore $(pmid X_1)to exists iin[1]^+:(pmid x_i)$.
Assume $P(n)$ holds for any positive integer $n$.
Assume $(pmid X_n)$ or $(pmid x_n+1)$.
You need to use proof by cases to derive $exists iin[n+1]^+:(pmid x_i)$.- From that you may derive $(pmid X_nx_n+1)to exists iin[n+1]^+:(pmid x_i)$ .
- That is $P(n+1)$ can be derived from assuming $P(n)$ and either $(pmid X_n)$ or $(pmid x_n+1)$.
Assume $(pnmid X_n)$ and $(pnmid x_n+1)$.
You need to derive $negexists iin[n+1]^+:(pmid x_i)$ from the assumptions.- From you may derive $(pmid X_nx_n+1)to exists iin[n+1]^+:(pmid x_i)$
- That is $P(n+1)$ can be derived from assuming $P(n)$ and both $(pnmid X_n)$ and $(pnmid x_n+1)$.
That is $P(n+1)$ can be derived from assuming $P(n)$ in both the above. Do so.
Therefore $forall ngeq 1: (P(n)to P(n+1))$
$[n]^+=kinBbb N^+: kleq n$
answered Jul 23 at 5:09
Graham Kemp
80.1k43275
answered Jul 23 at 5:09
Graham Kemp
80.1k43275
answered Jul 23 at 5:09
Graham Kemp
80.1k43275
answered Jul 23 at 5:09
Graham Kemp
80.1k43275
80.1k43275
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%2f2859422%2fproving-a-conditional-statement-by-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
Just put the subscript in braces:
x_k+1gives $x_k+1$– saulspatz
Jul 22 at 13:55
I keep trying to edit it but you post an edit and forestall me. Stop editing it and I'll fix it.
– saulspatz
Jul 22 at 14:04
Sorry about that @saulspatz , saw ur comment and tried editing immediately, thanks for ur initiative.
– Prashin Jeevaganth
Jul 22 at 14:07
The symbol for ‘divides’ is obtained by the command
mid.– Bernard
Jul 22 at 14:09
1
@Peter
anmid bgives $anmid b$. If you right-click on a formula you get a pop-up that says "Show Math As" and then if you pick "TeX commands" you'll see the TeX commands that you just need to put inside $ signs. This has helped me a lot. Try it.– saulspatz
Jul 22 at 14:20