Sequences with divisibility
$begingroup$
A sequence is such that $a_o =1, a_1= 1, a_{n+1}
=a_{n}a_{n-1}+1$ so we have to comment on divisibilty of $a_{2007} $ by 4.
I found out first few values in sequence as
1,1,2,3,7,22, .... which told me that only $a_{3n} $ is even.
But can there be some other elaborative method?
sequences-and-series
edited Dec 26 '18 at 17:51
Bernard
121k740116
asked Dec 26 '18 at 17:42
mavericmaveric
73412
$endgroup$
add a comment |
$begingroup$
A sequence is such that $a_o =1, a_1= 1, a_{n+1}
=a_{n}a_{n-1}+1$ so we have to comment on divisibilty of $a_{2007} $ by 4.
I found out first few values in sequence as
1,1,2,3,7,22, .... which told me that only $a_{3n} $ is even.
But can there be some other elaborative method?
sequences-and-series
edited Dec 26 '18 at 17:51
Bernard
121k740116
asked Dec 26 '18 at 17:42
mavericmaveric
73412
$endgroup$
add a comment |
$begingroup$
A sequence is such that $a_o =1, a_1= 1, a_{n+1}
=a_{n}a_{n-1}+1$ so we have to comment on divisibilty of $a_{2007} $ by 4.
I found out first few values in sequence as
1,1,2,3,7,22, .... which told me that only $a_{3n} $ is even.
But can there be some other elaborative method?
sequences-and-series
edited Dec 26 '18 at 17:51
Bernard
121k740116
asked Dec 26 '18 at 17:42
mavericmaveric
73412
$endgroup$
A sequence is such that $a_o =1, a_1= 1, a_{n+1}
=a_{n}a_{n-1}+1$ so we have to comment on divisibilty of $a_{2007} $ by 4.
I found out first few values in sequence as
1,1,2,3,7,22, .... which told me that only $a_{3n} $ is even.
But can there be some other elaborative method?
sequences-and-series
sequences-and-series
edited Dec 26 '18 at 17:51
Bernard
121k740116
asked Dec 26 '18 at 17:42
mavericmaveric
73412
edited Dec 26 '18 at 17:51
Bernard
121k740116
asked Dec 26 '18 at 17:42
mavericmaveric
73412
edited Dec 26 '18 at 17:51
Bernard
121k740116
edited Dec 26 '18 at 17:51
Bernard
121k740116
edited Dec 26 '18 at 17:51
Bernard
121k740116
121k740116
asked Dec 26 '18 at 17:42
mavericmaveric
73412
asked Dec 26 '18 at 17:42
mavericmaveric
73412
asked Dec 26 '18 at 17:42
mavericmaveric
73412
73412
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
The sequence $a_nbmod 4$ is eventually periodic with a readily determined period ...
answered Dec 26 '18 at 17:44
Hagen von EitzenHagen von Eitzen
279k23271503
$endgroup$
add a comment |
$begingroup$
Hint $ $ There are $j<k$ with $,(a_j,a_{j+1})equiv (a_k,a_{k+1}),pmod{!4} $ since there are only finitely many such pairs $!bmod {!4}$. The recurrence depends only on the pair of prior values so this leads to cyclic behavior.
answered Dec 26 '18 at 18:39
Bill DubuqueBill Dubuque
210k29192645
$endgroup$
$begingroup$
For more on this idea see my posts on reinventing the wheel (cycle)
$endgroup$
– Bill Dubuque
Dec 26 '18 at 18:42
add a comment |
$begingroup$
Questions regarding divisibility in general are often a lot easier to tackle using modulaic algebra since we don't care about precisely what values the numbers will assume. In case you don't know what the modulo k operator is, it is basically the remainder that you get after you divide a number by k. If a number is divisible by k, so in our case 4, then it is zero in mod 4 since there is no rest.
So in this case we can translate the first values that you got into mod 4 as follows: 1,1,2,3,3,2 ... Now let's multiply a number in mod 2 by a number in mod 3. These numbers can be written as a=(4c+2) and b=(4d+3), so the result of their multiplication is 4d+6. However, we should add an extra one in the sequence, which will give us 4d+7. As you can verify, this number is indeed 3 in mod 4. Whenever we multiply two numbers that are 3 in mod 4, the next number in the sequence will be 2.
Therefore we can conjecture that no element in the entire sequence will be divisible by 4 since each one of them will be either 2 or 3 in mod 4.
answered Dec 26 '18 at 18:13
tyler1tyler1
92
$endgroup$
add a 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%2f3053142%2fsequences-with-divisibility%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The sequence $a_nbmod 4$ is eventually periodic with a readily determined period ...
answered Dec 26 '18 at 17:44
Hagen von EitzenHagen von Eitzen
279k23271503
$endgroup$
add a comment |
$begingroup$
The sequence $a_nbmod 4$ is eventually periodic with a readily determined period ...
answered Dec 26 '18 at 17:44
Hagen von EitzenHagen von Eitzen
279k23271503
$endgroup$
add a comment |
$begingroup$
The sequence $a_nbmod 4$ is eventually periodic with a readily determined period ...
answered Dec 26 '18 at 17:44
Hagen von EitzenHagen von Eitzen
279k23271503
$endgroup$
The sequence $a_nbmod 4$ is eventually periodic with a readily determined period ...
answered Dec 26 '18 at 17:44
Hagen von EitzenHagen von Eitzen
279k23271503
edited Dec 26 '18 at 17:49
answered Dec 26 '18 at 17:44
Hagen von EitzenHagen von Eitzen
279k23271503
answered Dec 26 '18 at 17:44
Hagen von EitzenHagen von Eitzen
279k23271503
answered Dec 26 '18 at 17:44
Hagen von EitzenHagen von Eitzen
279k23271503
279k23271503
add a comment |
add a comment |
$begingroup$
Hint $ $ There are $j<k$ with $,(a_j,a_{j+1})equiv (a_k,a_{k+1}),pmod{!4} $ since there are only finitely many such pairs $!bmod {!4}$. The recurrence depends only on the pair of prior values so this leads to cyclic behavior.
answered Dec 26 '18 at 18:39
Bill DubuqueBill Dubuque
210k29192645
$endgroup$
$begingroup$
For more on this idea see my posts on reinventing the wheel (cycle)
$endgroup$
– Bill Dubuque
Dec 26 '18 at 18:42
add a comment |
$begingroup$
Hint $ $ There are $j<k$ with $,(a_j,a_{j+1})equiv (a_k,a_{k+1}),pmod{!4} $ since there are only finitely many such pairs $!bmod {!4}$. The recurrence depends only on the pair of prior values so this leads to cyclic behavior.
answered Dec 26 '18 at 18:39
Bill DubuqueBill Dubuque
210k29192645
$endgroup$
$begingroup$
For more on this idea see my posts on reinventing the wheel (cycle)
$endgroup$
– Bill Dubuque
Dec 26 '18 at 18:42
add a comment |
$begingroup$
Hint $ $ There are $j<k$ with $,(a_j,a_{j+1})equiv (a_k,a_{k+1}),pmod{!4} $ since there are only finitely many such pairs $!bmod {!4}$. The recurrence depends only on the pair of prior values so this leads to cyclic behavior.
answered Dec 26 '18 at 18:39
Bill DubuqueBill Dubuque
210k29192645
$endgroup$
Hint $ $ There are $j<k$ with $,(a_j,a_{j+1})equiv (a_k,a_{k+1}),pmod{!4} $ since there are only finitely many such pairs $!bmod {!4}$. The recurrence depends only on the pair of prior values so this leads to cyclic behavior.
answered Dec 26 '18 at 18:39
Bill DubuqueBill Dubuque
210k29192645
answered Dec 26 '18 at 18:39
Bill DubuqueBill Dubuque
210k29192645
answered Dec 26 '18 at 18:39
Bill DubuqueBill Dubuque
210k29192645
answered Dec 26 '18 at 18:39
Bill DubuqueBill Dubuque
210k29192645
210k29192645
$begingroup$
For more on this idea see my posts on reinventing the wheel (cycle)
$endgroup$
– Bill Dubuque
Dec 26 '18 at 18:42
add a comment |
$begingroup$
For more on this idea see my posts on reinventing the wheel (cycle)
$endgroup$
– Bill Dubuque
Dec 26 '18 at 18:42
$begingroup$
For more on this idea see my posts on reinventing the wheel (cycle)
$endgroup$
– Bill Dubuque
Dec 26 '18 at 18:42
$begingroup$
For more on this idea see my posts on reinventing the wheel (cycle)
$endgroup$
– Bill Dubuque
Dec 26 '18 at 18:42
add a comment |
$begingroup$
Questions regarding divisibility in general are often a lot easier to tackle using modulaic algebra since we don't care about precisely what values the numbers will assume. In case you don't know what the modulo k operator is, it is basically the remainder that you get after you divide a number by k. If a number is divisible by k, so in our case 4, then it is zero in mod 4 since there is no rest.
So in this case we can translate the first values that you got into mod 4 as follows: 1,1,2,3,3,2 ... Now let's multiply a number in mod 2 by a number in mod 3. These numbers can be written as a=(4c+2) and b=(4d+3), so the result of their multiplication is 4d+6. However, we should add an extra one in the sequence, which will give us 4d+7. As you can verify, this number is indeed 3 in mod 4. Whenever we multiply two numbers that are 3 in mod 4, the next number in the sequence will be 2.
Therefore we can conjecture that no element in the entire sequence will be divisible by 4 since each one of them will be either 2 or 3 in mod 4.
answered Dec 26 '18 at 18:13
tyler1tyler1
92
$endgroup$
add a comment |
$begingroup$
Questions regarding divisibility in general are often a lot easier to tackle using modulaic algebra since we don't care about precisely what values the numbers will assume. In case you don't know what the modulo k operator is, it is basically the remainder that you get after you divide a number by k. If a number is divisible by k, so in our case 4, then it is zero in mod 4 since there is no rest.
So in this case we can translate the first values that you got into mod 4 as follows: 1,1,2,3,3,2 ... Now let's multiply a number in mod 2 by a number in mod 3. These numbers can be written as a=(4c+2) and b=(4d+3), so the result of their multiplication is 4d+6. However, we should add an extra one in the sequence, which will give us 4d+7. As you can verify, this number is indeed 3 in mod 4. Whenever we multiply two numbers that are 3 in mod 4, the next number in the sequence will be 2.
Therefore we can conjecture that no element in the entire sequence will be divisible by 4 since each one of them will be either 2 or 3 in mod 4.
answered Dec 26 '18 at 18:13
tyler1tyler1
92
$endgroup$
add a comment |
$begingroup$
Questions regarding divisibility in general are often a lot easier to tackle using modulaic algebra since we don't care about precisely what values the numbers will assume. In case you don't know what the modulo k operator is, it is basically the remainder that you get after you divide a number by k. If a number is divisible by k, so in our case 4, then it is zero in mod 4 since there is no rest.
So in this case we can translate the first values that you got into mod 4 as follows: 1,1,2,3,3,2 ... Now let's multiply a number in mod 2 by a number in mod 3. These numbers can be written as a=(4c+2) and b=(4d+3), so the result of their multiplication is 4d+6. However, we should add an extra one in the sequence, which will give us 4d+7. As you can verify, this number is indeed 3 in mod 4. Whenever we multiply two numbers that are 3 in mod 4, the next number in the sequence will be 2.
Therefore we can conjecture that no element in the entire sequence will be divisible by 4 since each one of them will be either 2 or 3 in mod 4.
answered Dec 26 '18 at 18:13
tyler1tyler1
92
$endgroup$
Questions regarding divisibility in general are often a lot easier to tackle using modulaic algebra since we don't care about precisely what values the numbers will assume. In case you don't know what the modulo k operator is, it is basically the remainder that you get after you divide a number by k. If a number is divisible by k, so in our case 4, then it is zero in mod 4 since there is no rest.
So in this case we can translate the first values that you got into mod 4 as follows: 1,1,2,3,3,2 ... Now let's multiply a number in mod 2 by a number in mod 3. These numbers can be written as a=(4c+2) and b=(4d+3), so the result of their multiplication is 4d+6. However, we should add an extra one in the sequence, which will give us 4d+7. As you can verify, this number is indeed 3 in mod 4. Whenever we multiply two numbers that are 3 in mod 4, the next number in the sequence will be 2.
Therefore we can conjecture that no element in the entire sequence will be divisible by 4 since each one of them will be either 2 or 3 in mod 4.
answered Dec 26 '18 at 18:13
tyler1tyler1
92
answered Dec 26 '18 at 18:13
tyler1tyler1
92
answered Dec 26 '18 at 18:13
tyler1tyler1
92
answered Dec 26 '18 at 18:13
tyler1tyler1
92
92
add a comment |
add a 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%2f3053142%2fsequences-with-divisibility%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
