Proof of triangles made with n lines where m of them are parallel
$begingroup$
So suppose that you have n lines where m of them are parallel. I know that the equation is $${{n-m}choose3} + m{{n-m}choose2}$$
However I am confused on how I can prove this using induction. Would I have to use double induction and prove n when I set m and prove m when I set n or is there a way to prove this without double induction?
I know for the base case I would have to prove when $n = 3$ and when $m = 0$ but how would you prove this using induction. And when I say induction I mean that I can incorporate explanations and observations into the proof, this proof is not supposed to be algebraic or anything. However it should have the base cases, inductive hypothesis and inductive step.
discrete-mathematics
asked Dec 1 '18 at 0:21
GeraltGeralt
8917
$endgroup$
add a comment |
$begingroup$
So suppose that you have n lines where m of them are parallel. I know that the equation is $${{n-m}choose3} + m{{n-m}choose2}$$
However I am confused on how I can prove this using induction. Would I have to use double induction and prove n when I set m and prove m when I set n or is there a way to prove this without double induction?
I know for the base case I would have to prove when $n = 3$ and when $m = 0$ but how would you prove this using induction. And when I say induction I mean that I can incorporate explanations and observations into the proof, this proof is not supposed to be algebraic or anything. However it should have the base cases, inductive hypothesis and inductive step.
discrete-mathematics
asked Dec 1 '18 at 0:21
GeraltGeralt
8917
$endgroup$
add a comment |
$begingroup$
So suppose that you have n lines where m of them are parallel. I know that the equation is $${{n-m}choose3} + m{{n-m}choose2}$$
However I am confused on how I can prove this using induction. Would I have to use double induction and prove n when I set m and prove m when I set n or is there a way to prove this without double induction?
I know for the base case I would have to prove when $n = 3$ and when $m = 0$ but how would you prove this using induction. And when I say induction I mean that I can incorporate explanations and observations into the proof, this proof is not supposed to be algebraic or anything. However it should have the base cases, inductive hypothesis and inductive step.
discrete-mathematics
asked Dec 1 '18 at 0:21
GeraltGeralt
8917
$endgroup$
So suppose that you have n lines where m of them are parallel. I know that the equation is $${{n-m}choose3} + m{{n-m}choose2}$$
However I am confused on how I can prove this using induction. Would I have to use double induction and prove n when I set m and prove m when I set n or is there a way to prove this without double induction?
I know for the base case I would have to prove when $n = 3$ and when $m = 0$ but how would you prove this using induction. And when I say induction I mean that I can incorporate explanations and observations into the proof, this proof is not supposed to be algebraic or anything. However it should have the base cases, inductive hypothesis and inductive step.
discrete-mathematics
discrete-mathematics
asked Dec 1 '18 at 0:21
GeraltGeralt
8917
asked Dec 1 '18 at 0:21
GeraltGeralt
8917
edited Dec 1 '18 at 0:26
Geralt
asked Dec 1 '18 at 0:21
GeraltGeralt
8917
asked Dec 1 '18 at 0:21
GeraltGeralt
8917
asked Dec 1 '18 at 0:21
GeraltGeralt
8917
8917
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Let $T(n,m)$ be the number of triangles made with $n$ lines, $m$ of which are parallel.
Here's how to prove your formula using a single induction. Let $P(k)$ be the following proposition:
$P(k)$: For all $mge 2$, and $m=0$, $T(m+k,m)= binom{k}3+mbinom{k}2. $
Using a single induction, you can show that $P(k)$ is true for all $kge 0$.
To do this, use the fact that
$$
T(n+1,m) = T(n,m)+m(n-m)+binom{n-m}2
$$
because adding a new line creates $m(n-m)$ triangles involving a parallel line, and $binom{n-m}2$ triangles not involving a parallel line. I think you should be able to use the above to show $P(k)$ implies $P(k+1)$.
answered Dec 1 '18 at 1:11
Mike EarnestMike Earnest
21.3k11951
$endgroup$
$begingroup$
Wouldn't m have to be either 0 or greater than 1 and not equal to 1 because you can't have 1 parallel line. Parallel lines have to be at least a pair or you don't have parallel lines.
$endgroup$
– Geralt
Dec 1 '18 at 1:28
$begingroup$
Also, wouldnt k have to be at least 3 because otherwise you wouldn't have any triangles to count.
$endgroup$
– Geralt
Dec 1 '18 at 1:30
$begingroup$
@Geralt The formula works for all $kge 0$; when $k=0$ or $1$, the formula correctly says there are $0$ triangles. When $k=2$, the formula correctly says there are $m$ triangles, which is zero when $m=0$.
$endgroup$
– Mike Earnest
Dec 1 '18 at 1:36
$begingroup$
@Geralt I've changed the condition on $m$ because of your comment.
$endgroup$
– Mike Earnest
Dec 1 '18 at 1:41
$begingroup$
I am a bit confused on the proposition P(k). How can you say that P(k) is true for m greater than 1 and equal to 0 without proving that first. Or is it unnecessary?
$endgroup$
– Geralt
Dec 1 '18 at 14:05
|
show 1 more comment
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3020847%2fproof-of-triangles-made-with-n-lines-where-m-of-them-are-parallel%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Let $T(n,m)$ be the number of triangles made with $n$ lines, $m$ of which are parallel.
Here's how to prove your formula using a single induction. Let $P(k)$ be the following proposition:
$P(k)$: For all $mge 2$, and $m=0$, $T(m+k,m)= binom{k}3+mbinom{k}2. $
Using a single induction, you can show that $P(k)$ is true for all $kge 0$.
To do this, use the fact that
$$
T(n+1,m) = T(n,m)+m(n-m)+binom{n-m}2
$$
because adding a new line creates $m(n-m)$ triangles involving a parallel line, and $binom{n-m}2$ triangles not involving a parallel line. I think you should be able to use the above to show $P(k)$ implies $P(k+1)$.
answered Dec 1 '18 at 1:11
Mike EarnestMike Earnest
21.3k11951
$endgroup$
$begingroup$
Wouldn't m have to be either 0 or greater than 1 and not equal to 1 because you can't have 1 parallel line. Parallel lines have to be at least a pair or you don't have parallel lines.
$endgroup$
– Geralt
Dec 1 '18 at 1:28
$begingroup$
Also, wouldnt k have to be at least 3 because otherwise you wouldn't have any triangles to count.
$endgroup$
– Geralt
Dec 1 '18 at 1:30
$begingroup$
@Geralt The formula works for all $kge 0$; when $k=0$ or $1$, the formula correctly says there are $0$ triangles. When $k=2$, the formula correctly says there are $m$ triangles, which is zero when $m=0$.
$endgroup$
– Mike Earnest
Dec 1 '18 at 1:36
$begingroup$
@Geralt I've changed the condition on $m$ because of your comment.
$endgroup$
– Mike Earnest
Dec 1 '18 at 1:41
$begingroup$
I am a bit confused on the proposition P(k). How can you say that P(k) is true for m greater than 1 and equal to 0 without proving that first. Or is it unnecessary?
$endgroup$
– Geralt
Dec 1 '18 at 14:05
|
show 1 more comment
$begingroup$
Let $T(n,m)$ be the number of triangles made with $n$ lines, $m$ of which are parallel.
Here's how to prove your formula using a single induction. Let $P(k)$ be the following proposition:
$P(k)$: For all $mge 2$, and $m=0$, $T(m+k,m)= binom{k}3+mbinom{k}2. $
Using a single induction, you can show that $P(k)$ is true for all $kge 0$.
To do this, use the fact that
$$
T(n+1,m) = T(n,m)+m(n-m)+binom{n-m}2
$$
because adding a new line creates $m(n-m)$ triangles involving a parallel line, and $binom{n-m}2$ triangles not involving a parallel line. I think you should be able to use the above to show $P(k)$ implies $P(k+1)$.
answered Dec 1 '18 at 1:11
Mike EarnestMike Earnest
21.3k11951
$endgroup$
$begingroup$
Wouldn't m have to be either 0 or greater than 1 and not equal to 1 because you can't have 1 parallel line. Parallel lines have to be at least a pair or you don't have parallel lines.
$endgroup$
– Geralt
Dec 1 '18 at 1:28
$begingroup$
Also, wouldnt k have to be at least 3 because otherwise you wouldn't have any triangles to count.
$endgroup$
– Geralt
Dec 1 '18 at 1:30
$begingroup$
@Geralt The formula works for all $kge 0$; when $k=0$ or $1$, the formula correctly says there are $0$ triangles. When $k=2$, the formula correctly says there are $m$ triangles, which is zero when $m=0$.
$endgroup$
– Mike Earnest
Dec 1 '18 at 1:36
$begingroup$
@Geralt I've changed the condition on $m$ because of your comment.
$endgroup$
– Mike Earnest
Dec 1 '18 at 1:41
$begingroup$
I am a bit confused on the proposition P(k). How can you say that P(k) is true for m greater than 1 and equal to 0 without proving that first. Or is it unnecessary?
$endgroup$
– Geralt
Dec 1 '18 at 14:05
|
show 1 more comment
$begingroup$
Let $T(n,m)$ be the number of triangles made with $n$ lines, $m$ of which are parallel.
Here's how to prove your formula using a single induction. Let $P(k)$ be the following proposition:
$P(k)$: For all $mge 2$, and $m=0$, $T(m+k,m)= binom{k}3+mbinom{k}2. $
Using a single induction, you can show that $P(k)$ is true for all $kge 0$.
To do this, use the fact that
$$
T(n+1,m) = T(n,m)+m(n-m)+binom{n-m}2
$$
because adding a new line creates $m(n-m)$ triangles involving a parallel line, and $binom{n-m}2$ triangles not involving a parallel line. I think you should be able to use the above to show $P(k)$ implies $P(k+1)$.
answered Dec 1 '18 at 1:11
Mike EarnestMike Earnest
21.3k11951
$endgroup$
Let $T(n,m)$ be the number of triangles made with $n$ lines, $m$ of which are parallel.
Here's how to prove your formula using a single induction. Let $P(k)$ be the following proposition:
$P(k)$: For all $mge 2$, and $m=0$, $T(m+k,m)= binom{k}3+mbinom{k}2. $
Using a single induction, you can show that $P(k)$ is true for all $kge 0$.
To do this, use the fact that
$$
T(n+1,m) = T(n,m)+m(n-m)+binom{n-m}2
$$
because adding a new line creates $m(n-m)$ triangles involving a parallel line, and $binom{n-m}2$ triangles not involving a parallel line. I think you should be able to use the above to show $P(k)$ implies $P(k+1)$.
answered Dec 1 '18 at 1:11
Mike EarnestMike Earnest
21.3k11951
edited Dec 1 '18 at 1:40
answered Dec 1 '18 at 1:11
Mike EarnestMike Earnest
21.3k11951
answered Dec 1 '18 at 1:11
Mike EarnestMike Earnest
21.3k11951
answered Dec 1 '18 at 1:11
Mike EarnestMike Earnest
21.3k11951
21.3k11951
$begingroup$
Wouldn't m have to be either 0 or greater than 1 and not equal to 1 because you can't have 1 parallel line. Parallel lines have to be at least a pair or you don't have parallel lines.
$endgroup$
– Geralt
Dec 1 '18 at 1:28
$begingroup$
Also, wouldnt k have to be at least 3 because otherwise you wouldn't have any triangles to count.
$endgroup$
– Geralt
Dec 1 '18 at 1:30
$begingroup$
@Geralt The formula works for all $kge 0$; when $k=0$ or $1$, the formula correctly says there are $0$ triangles. When $k=2$, the formula correctly says there are $m$ triangles, which is zero when $m=0$.
$endgroup$
– Mike Earnest
Dec 1 '18 at 1:36
$begingroup$
@Geralt I've changed the condition on $m$ because of your comment.
$endgroup$
– Mike Earnest
Dec 1 '18 at 1:41
$begingroup$
I am a bit confused on the proposition P(k). How can you say that P(k) is true for m greater than 1 and equal to 0 without proving that first. Or is it unnecessary?
$endgroup$
– Geralt
Dec 1 '18 at 14:05
|
show 1 more comment
$begingroup$
Wouldn't m have to be either 0 or greater than 1 and not equal to 1 because you can't have 1 parallel line. Parallel lines have to be at least a pair or you don't have parallel lines.
$endgroup$
– Geralt
Dec 1 '18 at 1:28
$begingroup$
Also, wouldnt k have to be at least 3 because otherwise you wouldn't have any triangles to count.
$endgroup$
– Geralt
Dec 1 '18 at 1:30
$begingroup$
@Geralt The formula works for all $kge 0$; when $k=0$ or $1$, the formula correctly says there are $0$ triangles. When $k=2$, the formula correctly says there are $m$ triangles, which is zero when $m=0$.
$endgroup$
– Mike Earnest
Dec 1 '18 at 1:36
$begingroup$
@Geralt I've changed the condition on $m$ because of your comment.
$endgroup$
– Mike Earnest
Dec 1 '18 at 1:41
$begingroup$
I am a bit confused on the proposition P(k). How can you say that P(k) is true for m greater than 1 and equal to 0 without proving that first. Or is it unnecessary?
$endgroup$
– Geralt
Dec 1 '18 at 14:05
$begingroup$
Wouldn't m have to be either 0 or greater than 1 and not equal to 1 because you can't have 1 parallel line. Parallel lines have to be at least a pair or you don't have parallel lines.
$endgroup$
– Geralt
Dec 1 '18 at 1:28
$begingroup$
Wouldn't m have to be either 0 or greater than 1 and not equal to 1 because you can't have 1 parallel line. Parallel lines have to be at least a pair or you don't have parallel lines.
$endgroup$
– Geralt
Dec 1 '18 at 1:28
$begingroup$
Also, wouldnt k have to be at least 3 because otherwise you wouldn't have any triangles to count.
$endgroup$
– Geralt
Dec 1 '18 at 1:30
$begingroup$
Also, wouldnt k have to be at least 3 because otherwise you wouldn't have any triangles to count.
$endgroup$
– Geralt
Dec 1 '18 at 1:30
$begingroup$
@Geralt The formula works for all $kge 0$; when $k=0$ or $1$, the formula correctly says there are $0$ triangles. When $k=2$, the formula correctly says there are $m$ triangles, which is zero when $m=0$.
$endgroup$
– Mike Earnest
Dec 1 '18 at 1:36
$begingroup$
@Geralt The formula works for all $kge 0$; when $k=0$ or $1$, the formula correctly says there are $0$ triangles. When $k=2$, the formula correctly says there are $m$ triangles, which is zero when $m=0$.
$endgroup$
– Mike Earnest
Dec 1 '18 at 1:36
$begingroup$
@Geralt I've changed the condition on $m$ because of your comment.
$endgroup$
– Mike Earnest
Dec 1 '18 at 1:41
$begingroup$
@Geralt I've changed the condition on $m$ because of your comment.
$endgroup$
– Mike Earnest
Dec 1 '18 at 1:41
$begingroup$
I am a bit confused on the proposition P(k). How can you say that P(k) is true for m greater than 1 and equal to 0 without proving that first. Or is it unnecessary?
$endgroup$
– Geralt
Dec 1 '18 at 14:05
$begingroup$
I am a bit confused on the proposition P(k). How can you say that P(k) is true for m greater than 1 and equal to 0 without proving that first. Or is it unnecessary?
$endgroup$
– Geralt
Dec 1 '18 at 14:05
|
show 1 more comment
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3020847%2fproof-of-triangles-made-with-n-lines-where-m-of-them-are-parallel%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
