Closed form for recursive sequence mod p
$begingroup$
When we have recursive sequences, we often seek to define them in a closed form if possible. Yet sometimes, these recursive sequences don't have closed forms. So my question is, is there any recursively defined sequence which doesn't have a closed form, but does have a closed form mod p? ie, ($a_n$) doesn't have a closed form, but ($a_n(mod p)$) does?
sequences-and-series
asked Dec 21 '18 at 3:58
johnrolfejohnrolfe
111
$endgroup$
add a comment |
$begingroup$
When we have recursive sequences, we often seek to define them in a closed form if possible. Yet sometimes, these recursive sequences don't have closed forms. So my question is, is there any recursively defined sequence which doesn't have a closed form, but does have a closed form mod p? ie, ($a_n$) doesn't have a closed form, but ($a_n(mod p)$) does?
sequences-and-series
asked Dec 21 '18 at 3:58
johnrolfejohnrolfe
111
$endgroup$
1
$begingroup$
what does "closed form" mean?
$endgroup$
– Siong Thye Goh
Dec 21 '18 at 4:39
$begingroup$
Closed form means we can write $a_n = $something not in terms of the other $a_i$. Like the closed form for the fibonacci sequence $F_n=frac{(1+sqrt(5))^n-(1-sqrt(5))^n}{2^nsqrt(5)}$. mathworld.wolfram.com/FibonacciNumber.html
$endgroup$
– johnrolfe
Dec 21 '18 at 4:49
add a comment |
$begingroup$
When we have recursive sequences, we often seek to define them in a closed form if possible. Yet sometimes, these recursive sequences don't have closed forms. So my question is, is there any recursively defined sequence which doesn't have a closed form, but does have a closed form mod p? ie, ($a_n$) doesn't have a closed form, but ($a_n(mod p)$) does?
sequences-and-series
asked Dec 21 '18 at 3:58
johnrolfejohnrolfe
111
$endgroup$
When we have recursive sequences, we often seek to define them in a closed form if possible. Yet sometimes, these recursive sequences don't have closed forms. So my question is, is there any recursively defined sequence which doesn't have a closed form, but does have a closed form mod p? ie, ($a_n$) doesn't have a closed form, but ($a_n(mod p)$) does?
sequences-and-series
sequences-and-series
asked Dec 21 '18 at 3:58
johnrolfejohnrolfe
111
asked Dec 21 '18 at 3:58
johnrolfejohnrolfe
111
asked Dec 21 '18 at 3:58
johnrolfejohnrolfe
111
asked Dec 21 '18 at 3:58
johnrolfejohnrolfe
111
asked Dec 21 '18 at 3:58
johnrolfejohnrolfe
111
111
1
$begingroup$
what does "closed form" mean?
$endgroup$
– Siong Thye Goh
Dec 21 '18 at 4:39
$begingroup$
Closed form means we can write $a_n = $something not in terms of the other $a_i$. Like the closed form for the fibonacci sequence $F_n=frac{(1+sqrt(5))^n-(1-sqrt(5))^n}{2^nsqrt(5)}$. mathworld.wolfram.com/FibonacciNumber.html
$endgroup$
– johnrolfe
Dec 21 '18 at 4:49
add a comment |
1
$begingroup$
what does "closed form" mean?
$endgroup$
– Siong Thye Goh
Dec 21 '18 at 4:39
$begingroup$
Closed form means we can write $a_n = $something not in terms of the other $a_i$. Like the closed form for the fibonacci sequence $F_n=frac{(1+sqrt(5))^n-(1-sqrt(5))^n}{2^nsqrt(5)}$. mathworld.wolfram.com/FibonacciNumber.html
$endgroup$
– johnrolfe
Dec 21 '18 at 4:49
1
1
$begingroup$
what does "closed form" mean?
$endgroup$
– Siong Thye Goh
Dec 21 '18 at 4:39
$begingroup$
what does "closed form" mean?
$endgroup$
– Siong Thye Goh
Dec 21 '18 at 4:39
$begingroup$
Closed form means we can write $a_n = $something not in terms of the other $a_i$. Like the closed form for the fibonacci sequence $F_n=frac{(1+sqrt(5))^n-(1-sqrt(5))^n}{2^nsqrt(5)}$. mathworld.wolfram.com/FibonacciNumber.html
$endgroup$
– johnrolfe
Dec 21 '18 at 4:49
$begingroup$
Closed form means we can write $a_n = $something not in terms of the other $a_i$. Like the closed form for the fibonacci sequence $F_n=frac{(1+sqrt(5))^n-(1-sqrt(5))^n}{2^nsqrt(5)}$. mathworld.wolfram.com/FibonacciNumber.html
$endgroup$
– johnrolfe
Dec 21 '18 at 4:49
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
It is really much harder than you think to nail down precisely what "closed form" means. Your definition in the comments is really not sufficient: for example, does "$a_n = 1$ if $n$ is prime and $0$ otherwise" count as a closed form?
Anyway, assuming you're only asking about one prime, the answer is yes for dumb reasons. Consider, for example, the recurrence
$$a_n = p a_{n-1}^3 + 1, a_0 = 1.$$
As far as I know, this doesn't have a closed form in any reasonable sense, but $bmod p$ the recurrence reduces to $a_n = 1$, so this sequence is constant $bmod p$.
answered Dec 21 '18 at 23:00
Qiaochu YuanQiaochu Yuan
282k32597944
$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%2f3048160%2fclosed-form-for-recursive-sequence-mod-p%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$
It is really much harder than you think to nail down precisely what "closed form" means. Your definition in the comments is really not sufficient: for example, does "$a_n = 1$ if $n$ is prime and $0$ otherwise" count as a closed form?
Anyway, assuming you're only asking about one prime, the answer is yes for dumb reasons. Consider, for example, the recurrence
$$a_n = p a_{n-1}^3 + 1, a_0 = 1.$$
As far as I know, this doesn't have a closed form in any reasonable sense, but $bmod p$ the recurrence reduces to $a_n = 1$, so this sequence is constant $bmod p$.
answered Dec 21 '18 at 23:00
Qiaochu YuanQiaochu Yuan
282k32597944
$endgroup$
add a comment |
$begingroup$
It is really much harder than you think to nail down precisely what "closed form" means. Your definition in the comments is really not sufficient: for example, does "$a_n = 1$ if $n$ is prime and $0$ otherwise" count as a closed form?
Anyway, assuming you're only asking about one prime, the answer is yes for dumb reasons. Consider, for example, the recurrence
$$a_n = p a_{n-1}^3 + 1, a_0 = 1.$$
As far as I know, this doesn't have a closed form in any reasonable sense, but $bmod p$ the recurrence reduces to $a_n = 1$, so this sequence is constant $bmod p$.
answered Dec 21 '18 at 23:00
Qiaochu YuanQiaochu Yuan
282k32597944
$endgroup$
add a comment |
$begingroup$
It is really much harder than you think to nail down precisely what "closed form" means. Your definition in the comments is really not sufficient: for example, does "$a_n = 1$ if $n$ is prime and $0$ otherwise" count as a closed form?
Anyway, assuming you're only asking about one prime, the answer is yes for dumb reasons. Consider, for example, the recurrence
$$a_n = p a_{n-1}^3 + 1, a_0 = 1.$$
As far as I know, this doesn't have a closed form in any reasonable sense, but $bmod p$ the recurrence reduces to $a_n = 1$, so this sequence is constant $bmod p$.
answered Dec 21 '18 at 23:00
Qiaochu YuanQiaochu Yuan
282k32597944
$endgroup$
It is really much harder than you think to nail down precisely what "closed form" means. Your definition in the comments is really not sufficient: for example, does "$a_n = 1$ if $n$ is prime and $0$ otherwise" count as a closed form?
Anyway, assuming you're only asking about one prime, the answer is yes for dumb reasons. Consider, for example, the recurrence
$$a_n = p a_{n-1}^3 + 1, a_0 = 1.$$
As far as I know, this doesn't have a closed form in any reasonable sense, but $bmod p$ the recurrence reduces to $a_n = 1$, so this sequence is constant $bmod p$.
answered Dec 21 '18 at 23:00
Qiaochu YuanQiaochu Yuan
282k32597944
answered Dec 21 '18 at 23:00
Qiaochu YuanQiaochu Yuan
282k32597944
answered Dec 21 '18 at 23:00
Qiaochu YuanQiaochu Yuan
282k32597944
answered Dec 21 '18 at 23:00
Qiaochu YuanQiaochu Yuan
282k32597944
282k32597944
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%2f3048160%2fclosed-form-for-recursive-sequence-mod-p%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
1
$begingroup$
what does "closed form" mean?
$endgroup$
– Siong Thye Goh
Dec 21 '18 at 4:39
$begingroup$
Closed form means we can write $a_n = $something not in terms of the other $a_i$. Like the closed form for the fibonacci sequence $F_n=frac{(1+sqrt(5))^n-(1-sqrt(5))^n}{2^nsqrt(5)}$. mathworld.wolfram.com/FibonacciNumber.html
$endgroup$
– johnrolfe
Dec 21 '18 at 4:49