Mixing
Is every sequence bounded by a sequence which can be represented in closed form?
$begingroup$
Let $X$ be the set of $mathbb{R}$-valued sequences, i.e. $X := mathbb{R}^{mathbb{N}}={f: mathbb{N} to mathbb{R}}$, and let $S$ the set of sequences which can be expressed in closed form, i.e.:
$$
S:= {f in mathbb{R}^mathbb{N} space | space f text{ is in closed form}} subseteq X
$$
Now since "closed form" is not well-defined: I basically mean the usual stuff. That is: $f$ is in closed form if there is a mathematical expression that can be evaluated in a finite number of operations. The allowed symbols in the expression are: constants, variables and applications of $!$ (factorial), $exp, ln$, the trigonometric and hyperbolic functions with their inverses, $lfloor cdot rfloor, lceil cdot rceil, [cdot]$.
For example, $(a_k)_{kinmathbb{N}}in S$ if $displaystyle a_k = e^{(k!)^2cdot sinleft(binom{2k}{k}right)}$.
Now we have $S subset X$, i.e. there are sequences which cannot be represented in closed form.
However, does at least the following statement hold?
$$
forall f in X: exists g in S: f leq g
$$
(i.e. every sequence is bounded by a sequence which can be expressed in closed form)
sequences-and-series closed-form
asked Jan 9 at 18:22
bruderjakob17bruderjakob17
1997
$endgroup$
add a comment |
$begingroup$
Let $X$ be the set of $mathbb{R}$-valued sequences, i.e. $X := mathbb{R}^{mathbb{N}}={f: mathbb{N} to mathbb{R}}$, and let $S$ the set of sequences which can be expressed in closed form, i.e.:
$$
S:= {f in mathbb{R}^mathbb{N} space | space f text{ is in closed form}} subseteq X
$$
Now since "closed form" is not well-defined: I basically mean the usual stuff. That is: $f$ is in closed form if there is a mathematical expression that can be evaluated in a finite number of operations. The allowed symbols in the expression are: constants, variables and applications of $!$ (factorial), $exp, ln$, the trigonometric and hyperbolic functions with their inverses, $lfloor cdot rfloor, lceil cdot rceil, [cdot]$.
For example, $(a_k)_{kinmathbb{N}}in S$ if $displaystyle a_k = e^{(k!)^2cdot sinleft(binom{2k}{k}right)}$.
Now we have $S subset X$, i.e. there are sequences which cannot be represented in closed form.
However, does at least the following statement hold?
$$
forall f in X: exists g in S: f leq g
$$
(i.e. every sequence is bounded by a sequence which can be expressed in closed form)
sequences-and-series closed-form
asked Jan 9 at 18:22
bruderjakob17bruderjakob17
1997
$endgroup$
$begingroup$
How about $a_1=3$, $a_{n+1}=a_n!$ ?
$endgroup$
– Mindlack
Jan 9 at 18:29
1
$begingroup$
Since you admit [arbitrary real] constants in the expressions deemed "closed-form", and there are continuum-many reals, there are at least so many sequences in $S$ (not that this makes difficulty in providing an answer).
$endgroup$
– John Bentin
Jan 9 at 18:54
$begingroup$
@JohnBentin oh...you are absolutely right. I'll correct that.
$endgroup$
– bruderjakob17
Jan 9 at 19:16
add a comment |
$begingroup$
Let $X$ be the set of $mathbb{R}$-valued sequences, i.e. $X := mathbb{R}^{mathbb{N}}={f: mathbb{N} to mathbb{R}}$, and let $S$ the set of sequences which can be expressed in closed form, i.e.:
$$
S:= {f in mathbb{R}^mathbb{N} space | space f text{ is in closed form}} subseteq X
$$
Now since "closed form" is not well-defined: I basically mean the usual stuff. That is: $f$ is in closed form if there is a mathematical expression that can be evaluated in a finite number of operations. The allowed symbols in the expression are: constants, variables and applications of $!$ (factorial), $exp, ln$, the trigonometric and hyperbolic functions with their inverses, $lfloor cdot rfloor, lceil cdot rceil, [cdot]$.
For example, $(a_k)_{kinmathbb{N}}in S$ if $displaystyle a_k = e^{(k!)^2cdot sinleft(binom{2k}{k}right)}$.
Now we have $S subset X$, i.e. there are sequences which cannot be represented in closed form.
However, does at least the following statement hold?
$$
forall f in X: exists g in S: f leq g
$$
(i.e. every sequence is bounded by a sequence which can be expressed in closed form)
sequences-and-series closed-form
asked Jan 9 at 18:22
bruderjakob17bruderjakob17
1997
$endgroup$
Let $X$ be the set of $mathbb{R}$-valued sequences, i.e. $X := mathbb{R}^{mathbb{N}}={f: mathbb{N} to mathbb{R}}$, and let $S$ the set of sequences which can be expressed in closed form, i.e.:
$$
S:= {f in mathbb{R}^mathbb{N} space | space f text{ is in closed form}} subseteq X
$$
Now since "closed form" is not well-defined: I basically mean the usual stuff. That is: $f$ is in closed form if there is a mathematical expression that can be evaluated in a finite number of operations. The allowed symbols in the expression are: constants, variables and applications of $!$ (factorial), $exp, ln$, the trigonometric and hyperbolic functions with their inverses, $lfloor cdot rfloor, lceil cdot rceil, [cdot]$.
For example, $(a_k)_{kinmathbb{N}}in S$ if $displaystyle a_k = e^{(k!)^2cdot sinleft(binom{2k}{k}right)}$.
Now we have $S subset X$, i.e. there are sequences which cannot be represented in closed form.
However, does at least the following statement hold?
$$
forall f in X: exists g in S: f leq g
$$
(i.e. every sequence is bounded by a sequence which can be expressed in closed form)
sequences-and-series closed-form
sequences-and-series closed-form
asked Jan 9 at 18:22
bruderjakob17bruderjakob17
1997
asked Jan 9 at 18:22
bruderjakob17bruderjakob17
1997
edited Jan 9 at 19:17
bruderjakob17
asked Jan 9 at 18:22
bruderjakob17bruderjakob17
1997
asked Jan 9 at 18:22
bruderjakob17bruderjakob17
1997
asked Jan 9 at 18:22
bruderjakob17bruderjakob17
1997
1997
$begingroup$
How about $a_1=3$, $a_{n+1}=a_n!$ ?
$endgroup$
– Mindlack
Jan 9 at 18:29
1
$begingroup$
Since you admit [arbitrary real] constants in the expressions deemed "closed-form", and there are continuum-many reals, there are at least so many sequences in $S$ (not that this makes difficulty in providing an answer).
$endgroup$
– John Bentin
Jan 9 at 18:54
$begingroup$
@JohnBentin oh...you are absolutely right. I'll correct that.
$endgroup$
– bruderjakob17
Jan 9 at 19:16
add a comment |
$begingroup$
How about $a_1=3$, $a_{n+1}=a_n!$ ?
$endgroup$
– Mindlack
Jan 9 at 18:29
1
$begingroup$
Since you admit [arbitrary real] constants in the expressions deemed "closed-form", and there are continuum-many reals, there are at least so many sequences in $S$ (not that this makes difficulty in providing an answer).
$endgroup$
– John Bentin
Jan 9 at 18:54
$begingroup$
@JohnBentin oh...you are absolutely right. I'll correct that.
$endgroup$
– bruderjakob17
Jan 9 at 19:16
$begingroup$
How about $a_1=3$, $a_{n+1}=a_n!$ ?
$endgroup$
– Mindlack
Jan 9 at 18:29
$begingroup$
How about $a_1=3$, $a_{n+1}=a_n!$ ?
$endgroup$
– Mindlack
Jan 9 at 18:29
1
1
$begingroup$
Since you admit [arbitrary real] constants in the expressions deemed "closed-form", and there are continuum-many reals, there are at least so many sequences in $S$ (not that this makes difficulty in providing an answer).
$endgroup$
– John Bentin
Jan 9 at 18:54
$begingroup$
Since you admit [arbitrary real] constants in the expressions deemed "closed-form", and there are continuum-many reals, there are at least so many sequences in $S$ (not that this makes difficulty in providing an answer).
$endgroup$
– John Bentin
Jan 9 at 18:54
$begingroup$
@JohnBentin oh...you are absolutely right. I'll correct that.
$endgroup$
– bruderjakob17
Jan 9 at 19:16
$begingroup$
@JohnBentin oh...you are absolutely right. I'll correct that.
$endgroup$
– bruderjakob17
Jan 9 at 19:16
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
I think your definition of closed form is equivalent to the primitive recursive functions. The Ackermann function eventually overtakes every primitive recursive function, so the answer is that no function in $S$ dominates it.
In particular, probably the fastest growing type of function in your library is $n^{n^{n^n}}$ for some finite height of the tower. Ackermann uses $2$'s instead of $n$'s, but makes the height increase without bound, so eventually it will be taller than whatever tower you pick.
answered Jan 9 at 18:42
Ross MillikanRoss Millikan
295k23198371
$endgroup$
add a comment |
$begingroup$
I think not. Since $S$ is countable, enumerate it as ${s(n)}$. Now create a sequence $t$ such that
$$
t(n)_n = 1 + max{ s(n)_k | k le n } .
$$.
This construction should work even if you allow constructions like repeated factorials $!^{n}$ as in @Mindlack 's comment.
answered Jan 9 at 18:34
Ethan BolkerEthan Bolker
42.5k549113
$endgroup$
$begingroup$
@SmileyCraft Any number that's not the $k$th term in $s(n)$.
$endgroup$
– Ethan Bolker
Jan 9 at 18:39
$begingroup$
You mean $t_n > s(n)_n$, not just unequal (and there's diagonalization in there too)?
$endgroup$
– Daniel Schepler
Jan 9 at 18:39
$begingroup$
I think it is useful to give $t$ explicitly, for example by $t(n)_k:=max{s(n)_l:1leq lleq k}+1$.
$endgroup$
– SmileyCraft
Jan 9 at 18:40
$begingroup$
@SmileyCraft Thanks. Used your suggestion.
$endgroup$
– Ethan Bolker
Jan 9 at 18:44
$begingroup$
Interestingly this also proves that you can not define a bijection from $mathbb{N}$ to $S$.
$endgroup$
– SmileyCraft
Jan 9 at 18:47
|
show 3 more comments
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%2f3067789%2fis-every-sequence-bounded-by-a-sequence-which-can-be-represented-in-closed-form%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I think your definition of closed form is equivalent to the primitive recursive functions. The Ackermann function eventually overtakes every primitive recursive function, so the answer is that no function in $S$ dominates it.
In particular, probably the fastest growing type of function in your library is $n^{n^{n^n}}$ for some finite height of the tower. Ackermann uses $2$'s instead of $n$'s, but makes the height increase without bound, so eventually it will be taller than whatever tower you pick.
answered Jan 9 at 18:42
Ross MillikanRoss Millikan
295k23198371
$endgroup$
add a comment |
$begingroup$
I think your definition of closed form is equivalent to the primitive recursive functions. The Ackermann function eventually overtakes every primitive recursive function, so the answer is that no function in $S$ dominates it.
In particular, probably the fastest growing type of function in your library is $n^{n^{n^n}}$ for some finite height of the tower. Ackermann uses $2$'s instead of $n$'s, but makes the height increase without bound, so eventually it will be taller than whatever tower you pick.
answered Jan 9 at 18:42
Ross MillikanRoss Millikan
295k23198371
$endgroup$
add a comment |
$begingroup$
I think your definition of closed form is equivalent to the primitive recursive functions. The Ackermann function eventually overtakes every primitive recursive function, so the answer is that no function in $S$ dominates it.
In particular, probably the fastest growing type of function in your library is $n^{n^{n^n}}$ for some finite height of the tower. Ackermann uses $2$'s instead of $n$'s, but makes the height increase without bound, so eventually it will be taller than whatever tower you pick.
answered Jan 9 at 18:42
Ross MillikanRoss Millikan
295k23198371
$endgroup$
I think your definition of closed form is equivalent to the primitive recursive functions. The Ackermann function eventually overtakes every primitive recursive function, so the answer is that no function in $S$ dominates it.
In particular, probably the fastest growing type of function in your library is $n^{n^{n^n}}$ for some finite height of the tower. Ackermann uses $2$'s instead of $n$'s, but makes the height increase without bound, so eventually it will be taller than whatever tower you pick.
answered Jan 9 at 18:42
Ross MillikanRoss Millikan
295k23198371
edited Jan 9 at 20:39
answered Jan 9 at 18:42
Ross MillikanRoss Millikan
295k23198371
answered Jan 9 at 18:42
Ross MillikanRoss Millikan
295k23198371
answered Jan 9 at 18:42
Ross MillikanRoss Millikan
295k23198371
295k23198371
add a comment |
add a comment |
$begingroup$
I think not. Since $S$ is countable, enumerate it as ${s(n)}$. Now create a sequence $t$ such that
$$
t(n)_n = 1 + max{ s(n)_k | k le n } .
$$.
This construction should work even if you allow constructions like repeated factorials $!^{n}$ as in @Mindlack 's comment.
answered Jan 9 at 18:34
Ethan BolkerEthan Bolker
42.5k549113
$endgroup$
$begingroup$
@SmileyCraft Any number that's not the $k$th term in $s(n)$.
$endgroup$
– Ethan Bolker
Jan 9 at 18:39
$begingroup$
You mean $t_n > s(n)_n$, not just unequal (and there's diagonalization in there too)?
$endgroup$
– Daniel Schepler
Jan 9 at 18:39
$begingroup$
I think it is useful to give $t$ explicitly, for example by $t(n)_k:=max{s(n)_l:1leq lleq k}+1$.
$endgroup$
– SmileyCraft
Jan 9 at 18:40
$begingroup$
@SmileyCraft Thanks. Used your suggestion.
$endgroup$
– Ethan Bolker
Jan 9 at 18:44
$begingroup$
Interestingly this also proves that you can not define a bijection from $mathbb{N}$ to $S$.
$endgroup$
– SmileyCraft
Jan 9 at 18:47
|
show 3 more comments
$begingroup$
I think not. Since $S$ is countable, enumerate it as ${s(n)}$. Now create a sequence $t$ such that
$$
t(n)_n = 1 + max{ s(n)_k | k le n } .
$$.
This construction should work even if you allow constructions like repeated factorials $!^{n}$ as in @Mindlack 's comment.
answered Jan 9 at 18:34
Ethan BolkerEthan Bolker
42.5k549113
$endgroup$
$begingroup$
@SmileyCraft Any number that's not the $k$th term in $s(n)$.
$endgroup$
– Ethan Bolker
Jan 9 at 18:39
$begingroup$
You mean $t_n > s(n)_n$, not just unequal (and there's diagonalization in there too)?
$endgroup$
– Daniel Schepler
Jan 9 at 18:39
$begingroup$
I think it is useful to give $t$ explicitly, for example by $t(n)_k:=max{s(n)_l:1leq lleq k}+1$.
$endgroup$
– SmileyCraft
Jan 9 at 18:40
$begingroup$
@SmileyCraft Thanks. Used your suggestion.
$endgroup$
– Ethan Bolker
Jan 9 at 18:44
$begingroup$
Interestingly this also proves that you can not define a bijection from $mathbb{N}$ to $S$.
$endgroup$
– SmileyCraft
Jan 9 at 18:47
|
show 3 more comments
$begingroup$
I think not. Since $S$ is countable, enumerate it as ${s(n)}$. Now create a sequence $t$ such that
$$
t(n)_n = 1 + max{ s(n)_k | k le n } .
$$.
This construction should work even if you allow constructions like repeated factorials $!^{n}$ as in @Mindlack 's comment.
answered Jan 9 at 18:34
Ethan BolkerEthan Bolker
42.5k549113
$endgroup$
I think not. Since $S$ is countable, enumerate it as ${s(n)}$. Now create a sequence $t$ such that
$$
t(n)_n = 1 + max{ s(n)_k | k le n } .
$$.
This construction should work even if you allow constructions like repeated factorials $!^{n}$ as in @Mindlack 's comment.
answered Jan 9 at 18:34
Ethan BolkerEthan Bolker
42.5k549113
edited Jan 9 at 18:44
answered Jan 9 at 18:34
Ethan BolkerEthan Bolker
42.5k549113
answered Jan 9 at 18:34
Ethan BolkerEthan Bolker
42.5k549113
answered Jan 9 at 18:34
Ethan BolkerEthan Bolker
42.5k549113
42.5k549113
$begingroup$
@SmileyCraft Any number that's not the $k$th term in $s(n)$.
$endgroup$
– Ethan Bolker
Jan 9 at 18:39
$begingroup$
You mean $t_n > s(n)_n$, not just unequal (and there's diagonalization in there too)?
$endgroup$
– Daniel Schepler
Jan 9 at 18:39
$begingroup$
I think it is useful to give $t$ explicitly, for example by $t(n)_k:=max{s(n)_l:1leq lleq k}+1$.
$endgroup$
– SmileyCraft
Jan 9 at 18:40
$begingroup$
@SmileyCraft Thanks. Used your suggestion.
$endgroup$
– Ethan Bolker
Jan 9 at 18:44
$begingroup$
Interestingly this also proves that you can not define a bijection from $mathbb{N}$ to $S$.
$endgroup$
– SmileyCraft
Jan 9 at 18:47
|
show 3 more comments
$begingroup$
@SmileyCraft Any number that's not the $k$th term in $s(n)$.
$endgroup$
– Ethan Bolker
Jan 9 at 18:39
$begingroup$
You mean $t_n > s(n)_n$, not just unequal (and there's diagonalization in there too)?
$endgroup$
– Daniel Schepler
Jan 9 at 18:39
$begingroup$
I think it is useful to give $t$ explicitly, for example by $t(n)_k:=max{s(n)_l:1leq lleq k}+1$.
$endgroup$
– SmileyCraft
Jan 9 at 18:40
$begingroup$
@SmileyCraft Thanks. Used your suggestion.
$endgroup$
– Ethan Bolker
Jan 9 at 18:44
$begingroup$
Interestingly this also proves that you can not define a bijection from $mathbb{N}$ to $S$.
$endgroup$
– SmileyCraft
Jan 9 at 18:47
$begingroup$
@SmileyCraft Any number that's not the $k$th term in $s(n)$.
$endgroup$
– Ethan Bolker
Jan 9 at 18:39
$begingroup$
@SmileyCraft Any number that's not the $k$th term in $s(n)$.
$endgroup$
– Ethan Bolker
Jan 9 at 18:39
$begingroup$
You mean $t_n > s(n)_n$, not just unequal (and there's diagonalization in there too)?
$endgroup$
– Daniel Schepler
Jan 9 at 18:39
$begingroup$
You mean $t_n > s(n)_n$, not just unequal (and there's diagonalization in there too)?
$endgroup$
– Daniel Schepler
Jan 9 at 18:39
$begingroup$
I think it is useful to give $t$ explicitly, for example by $t(n)_k:=max{s(n)_l:1leq lleq k}+1$.
$endgroup$
– SmileyCraft
Jan 9 at 18:40
$begingroup$
I think it is useful to give $t$ explicitly, for example by $t(n)_k:=max{s(n)_l:1leq lleq k}+1$.
$endgroup$
– SmileyCraft
Jan 9 at 18:40
$begingroup$
@SmileyCraft Thanks. Used your suggestion.
$endgroup$
– Ethan Bolker
Jan 9 at 18:44
$begingroup$
@SmileyCraft Thanks. Used your suggestion.
$endgroup$
– Ethan Bolker
Jan 9 at 18:44
$begingroup$
Interestingly this also proves that you can not define a bijection from $mathbb{N}$ to $S$.
$endgroup$
– SmileyCraft
Jan 9 at 18:47
$begingroup$
Interestingly this also proves that you can not define a bijection from $mathbb{N}$ to $S$.
$endgroup$
– SmileyCraft
Jan 9 at 18:47
|
show 3 more comments
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%2f3067789%2fis-every-sequence-bounded-by-a-sequence-which-can-be-represented-in-closed-form%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$
How about $a_1=3$, $a_{n+1}=a_n!$ ?
$endgroup$
– Mindlack
Jan 9 at 18:29
1
$begingroup$
Since you admit [arbitrary real] constants in the expressions deemed "closed-form", and there are continuum-many reals, there are at least so many sequences in $S$ (not that this makes difficulty in providing an answer).
$endgroup$
– John Bentin
Jan 9 at 18:54
$begingroup$
@JohnBentin oh...you are absolutely right. I'll correct that.
$endgroup$
– bruderjakob17
Jan 9 at 19:16