For any integer $n > 0$, when exactly is $x_1 oplus x_2 oplus cdots oplus x_n$, satisfied? Find a pattern,...
$begingroup$
For any integer $n > 0$, when exactly is $x_1 oplus x_2 oplus cdots oplus x_n$, satisfied?
Find a pattern, then use induction to prove
The pattern I found is its true if odd number of $1's$
$P(n): $ for string of n variable $x_1 oplus x_2 oplus cdots oplus x_n$ is true if and only if it has odd $#$ of $1's$
Attempt of proving withing induction
Base Case:
let $n = 1$
$1 oplus 0$ holds and $0 oplus 1$ holds (this is n = 2 nvm)
EDIT: Single variable and has to have odd number of $1's$ so it's 1 only meaning it holds
Inductive step: Let $n > 1$. Suppose $P(n)$ holds whenever $1 leq j < n$
WTP: $P(n)$
Two cases $x_1 = 0$ and $x_1 = 1$
could someone tell if the pattern is correct and how to go about this? Thank you.
case 1: $x_1 = 0 to $ odd $1's$ from $x_2$ to $x_n$
$0 oplus 1$ by IH it'll total to $1$, so holds
case 2: $x_1 = 1 to $ even $1's$ from $x_2$ to $x_n$
$1 oplus 0$ since there are only 0's, this holds
logic
asked Dec 7 '18 at 4:55
Tree GarenTree Garen
36219
$endgroup$
add a comment |
$begingroup$
For any integer $n > 0$, when exactly is $x_1 oplus x_2 oplus cdots oplus x_n$, satisfied?
Find a pattern, then use induction to prove
The pattern I found is its true if odd number of $1's$
$P(n): $ for string of n variable $x_1 oplus x_2 oplus cdots oplus x_n$ is true if and only if it has odd $#$ of $1's$
Attempt of proving withing induction
Base Case:
let $n = 1$
$1 oplus 0$ holds and $0 oplus 1$ holds (this is n = 2 nvm)
EDIT: Single variable and has to have odd number of $1's$ so it's 1 only meaning it holds
Inductive step: Let $n > 1$. Suppose $P(n)$ holds whenever $1 leq j < n$
WTP: $P(n)$
Two cases $x_1 = 0$ and $x_1 = 1$
could someone tell if the pattern is correct and how to go about this? Thank you.
case 1: $x_1 = 0 to $ odd $1's$ from $x_2$ to $x_n$
$0 oplus 1$ by IH it'll total to $1$, so holds
case 2: $x_1 = 1 to $ even $1's$ from $x_2$ to $x_n$
$1 oplus 0$ since there are only 0's, this holds
logic
asked Dec 7 '18 at 4:55
Tree GarenTree Garen
36219
$endgroup$
$begingroup$
Your base case doesn’t match it’s proof (you’re the proving $n=2 case here). The proof so far seems fine, although you may need a slightly stronger $P(n)$ (try turning it into an if-and-only-if).
$endgroup$
– platty
Dec 7 '18 at 5:00
$begingroup$
Took your advice and attempted the inductive step
$endgroup$
– Tree Garen
Dec 7 '18 at 5:10
$begingroup$
I recommend starting base cases at $0$ (strengthening the theorem a bit in this case). This is often simpler and the exercise of figuring out what the theorem means for $n=0$ is often enlightening.
$endgroup$
– Derek Elkins
Dec 7 '18 at 5:11
$begingroup$
The question states $n > 0$
$endgroup$
– Tree Garen
Dec 7 '18 at 5:13
1
$begingroup$
@TreeGaren Yes, hence my parenthetical comment about strengthening the theorem. If you've proven the theorem for $ngeq 0$, you've proven it for $n>0$ too.
$endgroup$
– Derek Elkins
Dec 7 '18 at 5:54
add a comment |
$begingroup$
For any integer $n > 0$, when exactly is $x_1 oplus x_2 oplus cdots oplus x_n$, satisfied?
Find a pattern, then use induction to prove
The pattern I found is its true if odd number of $1's$
$P(n): $ for string of n variable $x_1 oplus x_2 oplus cdots oplus x_n$ is true if and only if it has odd $#$ of $1's$
Attempt of proving withing induction
Base Case:
let $n = 1$
$1 oplus 0$ holds and $0 oplus 1$ holds (this is n = 2 nvm)
EDIT: Single variable and has to have odd number of $1's$ so it's 1 only meaning it holds
Inductive step: Let $n > 1$. Suppose $P(n)$ holds whenever $1 leq j < n$
WTP: $P(n)$
Two cases $x_1 = 0$ and $x_1 = 1$
could someone tell if the pattern is correct and how to go about this? Thank you.
case 1: $x_1 = 0 to $ odd $1's$ from $x_2$ to $x_n$
$0 oplus 1$ by IH it'll total to $1$, so holds
case 2: $x_1 = 1 to $ even $1's$ from $x_2$ to $x_n$
$1 oplus 0$ since there are only 0's, this holds
logic
asked Dec 7 '18 at 4:55
Tree GarenTree Garen
36219
$endgroup$
For any integer $n > 0$, when exactly is $x_1 oplus x_2 oplus cdots oplus x_n$, satisfied?
Find a pattern, then use induction to prove
The pattern I found is its true if odd number of $1's$
$P(n): $ for string of n variable $x_1 oplus x_2 oplus cdots oplus x_n$ is true if and only if it has odd $#$ of $1's$
Attempt of proving withing induction
Base Case:
let $n = 1$
$1 oplus 0$ holds and $0 oplus 1$ holds (this is n = 2 nvm)
EDIT: Single variable and has to have odd number of $1's$ so it's 1 only meaning it holds
Inductive step: Let $n > 1$. Suppose $P(n)$ holds whenever $1 leq j < n$
WTP: $P(n)$
Two cases $x_1 = 0$ and $x_1 = 1$
could someone tell if the pattern is correct and how to go about this? Thank you.
case 1: $x_1 = 0 to $ odd $1's$ from $x_2$ to $x_n$
$0 oplus 1$ by IH it'll total to $1$, so holds
case 2: $x_1 = 1 to $ even $1's$ from $x_2$ to $x_n$
$1 oplus 0$ since there are only 0's, this holds
logic
logic
asked Dec 7 '18 at 4:55
Tree GarenTree Garen
36219
asked Dec 7 '18 at 4:55
Tree GarenTree Garen
36219
edited Dec 7 '18 at 5:09
Tree Garen
asked Dec 7 '18 at 4:55
Tree GarenTree Garen
36219
asked Dec 7 '18 at 4:55
Tree GarenTree Garen
36219
asked Dec 7 '18 at 4:55
Tree GarenTree Garen
36219
36219
$begingroup$
Your base case doesn’t match it’s proof (you’re the proving $n=2 case here). The proof so far seems fine, although you may need a slightly stronger $P(n)$ (try turning it into an if-and-only-if).
$endgroup$
– platty
Dec 7 '18 at 5:00
$begingroup$
Took your advice and attempted the inductive step
$endgroup$
– Tree Garen
Dec 7 '18 at 5:10
$begingroup$
I recommend starting base cases at $0$ (strengthening the theorem a bit in this case). This is often simpler and the exercise of figuring out what the theorem means for $n=0$ is often enlightening.
$endgroup$
– Derek Elkins
Dec 7 '18 at 5:11
$begingroup$
The question states $n > 0$
$endgroup$
– Tree Garen
Dec 7 '18 at 5:13
1
$begingroup$
@TreeGaren Yes, hence my parenthetical comment about strengthening the theorem. If you've proven the theorem for $ngeq 0$, you've proven it for $n>0$ too.
$endgroup$
– Derek Elkins
Dec 7 '18 at 5:54
add a comment |
$begingroup$
Your base case doesn’t match it’s proof (you’re the proving $n=2 case here). The proof so far seems fine, although you may need a slightly stronger $P(n)$ (try turning it into an if-and-only-if).
$endgroup$
– platty
Dec 7 '18 at 5:00
$begingroup$
Took your advice and attempted the inductive step
$endgroup$
– Tree Garen
Dec 7 '18 at 5:10
$begingroup$
I recommend starting base cases at $0$ (strengthening the theorem a bit in this case). This is often simpler and the exercise of figuring out what the theorem means for $n=0$ is often enlightening.
$endgroup$
– Derek Elkins
Dec 7 '18 at 5:11
$begingroup$
The question states $n > 0$
$endgroup$
– Tree Garen
Dec 7 '18 at 5:13
1
$begingroup$
@TreeGaren Yes, hence my parenthetical comment about strengthening the theorem. If you've proven the theorem for $ngeq 0$, you've proven it for $n>0$ too.
$endgroup$
– Derek Elkins
Dec 7 '18 at 5:54
$begingroup$
Your base case doesn’t match it’s proof (you’re the proving $n=2 case here). The proof so far seems fine, although you may need a slightly stronger $P(n)$ (try turning it into an if-and-only-if).
$endgroup$
– platty
Dec 7 '18 at 5:00
$begingroup$
Your base case doesn’t match it’s proof (you’re the proving $n=2 case here). The proof so far seems fine, although you may need a slightly stronger $P(n)$ (try turning it into an if-and-only-if).
$endgroup$
– platty
Dec 7 '18 at 5:00
$begingroup$
Took your advice and attempted the inductive step
$endgroup$
– Tree Garen
Dec 7 '18 at 5:10
$begingroup$
Took your advice and attempted the inductive step
$endgroup$
– Tree Garen
Dec 7 '18 at 5:10
$begingroup$
I recommend starting base cases at $0$ (strengthening the theorem a bit in this case). This is often simpler and the exercise of figuring out what the theorem means for $n=0$ is often enlightening.
$endgroup$
– Derek Elkins
Dec 7 '18 at 5:11
$begingroup$
I recommend starting base cases at $0$ (strengthening the theorem a bit in this case). This is often simpler and the exercise of figuring out what the theorem means for $n=0$ is often enlightening.
$endgroup$
– Derek Elkins
Dec 7 '18 at 5:11
$begingroup$
The question states $n > 0$
$endgroup$
– Tree Garen
Dec 7 '18 at 5:13
$begingroup$
The question states $n > 0$
$endgroup$
– Tree Garen
Dec 7 '18 at 5:13
1
1
$begingroup$
@TreeGaren Yes, hence my parenthetical comment about strengthening the theorem. If you've proven the theorem for $ngeq 0$, you've proven it for $n>0$ too.
$endgroup$
– Derek Elkins
Dec 7 '18 at 5:54
$begingroup$
@TreeGaren Yes, hence my parenthetical comment about strengthening the theorem. If you've proven the theorem for $ngeq 0$, you've proven it for $n>0$ too.
$endgroup$
– Derek Elkins
Dec 7 '18 at 5:54
add a comment |
0
active
oldest
votes
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%2f3029478%2ffor-any-integer-n-0-when-exactly-is-x-1-oplus-x-2-oplus-cdots-oplus-x%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3029478%2ffor-any-integer-n-0-when-exactly-is-x-1-oplus-x-2-oplus-cdots-oplus-x%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
$begingroup$
Your base case doesn’t match it’s proof (you’re the proving $n=2 case here). The proof so far seems fine, although you may need a slightly stronger $P(n)$ (try turning it into an if-and-only-if).
$endgroup$
– platty
Dec 7 '18 at 5:00
$begingroup$
Took your advice and attempted the inductive step
$endgroup$
– Tree Garen
Dec 7 '18 at 5:10
$begingroup$
I recommend starting base cases at $0$ (strengthening the theorem a bit in this case). This is often simpler and the exercise of figuring out what the theorem means for $n=0$ is often enlightening.
$endgroup$
– Derek Elkins
Dec 7 '18 at 5:11
$begingroup$
The question states $n > 0$
$endgroup$
– Tree Garen
Dec 7 '18 at 5:13
1
$begingroup$
@TreeGaren Yes, hence my parenthetical comment about strengthening the theorem. If you've proven the theorem for $ngeq 0$, you've proven it for $n>0$ too.
$endgroup$
– Derek Elkins
Dec 7 '18 at 5:54