Timeline for Closed formula for the factorial over naturals
Current License: CC BY-SA 4.0
39 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| 2 hours ago | comment | added | LSpice | I am confused: your comment says "Bad news, my son said that he doesn't allow division over $\mathbb N$", but your later edit says "In particular, I do not allow integer parts (floors or ceilings), except that the division function returns the integral quotient, so it does hide a sort of floor operation, which is allowed in this form." Am I misinterpreting, or are these in conflict? Which one should govern? | |
| 8 hours ago | history | edited | Emil Jeřábek | CC BY-SA 4.0 |
link to the question on reals
|
| 11 hours ago | history | edited | domotorp | CC BY-SA 4.0 |
clearified that the quesiton is about naturals, division returns the quotient
|
| 12 hours ago | comment | added | Anixx | @TimothyChow I think that possibly this answer is even more fitting: math.stackexchange.com/a/1424027/2513 | |
| 12 hours ago | comment | added | Timothy Chow | @Anixx I already linked to that math.SE question in my comment. | |
| 12 hours ago | history | edited | domotorp | CC BY-SA 4.0 |
added naturals to the title
|
| 12 hours ago | vote | accept | domotorp | ||
| 12 hours ago | comment | added | Anixx | Does this answer your question? math.stackexchange.com/a/1394130/2513 | |
| 12 hours ago | vote | accept | domotorp | ||
| 12 hours ago | |||||
| 13 hours ago | comment | added | Anixx | A fun fact: you can express factorial in umbral calculus using exponentiation and evaluation operation (finding standard part): $\Gamma(x)=\text{eval }\left(\frac{(B+x)^{B+x}}{ e^{B+x}}\right)$ | |
| 16 hours ago | history | became hot network question | |||
| 17 hours ago | comment | added | Emil Jeřábek | Given the amount of attention the question already received, I think it’s better to keep it as one question, while specifying that it has two variants. | |
| 17 hours ago | answer | added | Emil Jeřábek | timeline score: 46 | |
| 17 hours ago | comment | added | domotorp | Bad news, my son said that he doesn't allow division over $\mathbb N$... The formula should work over $\mathbb R$. Should I make a fork and create different questions for the two variants? | |
| 17 hours ago | comment | added | domotorp | @Emil You are right, over $\mathbb N$ where division is defined as $\lfloor a/b\rfloor$, that is a perfect solution. | |
| 17 hours ago | history | edited | domotorp | CC BY-SA 4.0 |
added more explanation
|
| 18 hours ago | comment | added | Emil Jeřábek | Though for $n!$, one does not need the general result; the simple explicit construction in Akiva Weinberger’s comment](math.stackexchange.com/questions/4605121/…) mentioned above by te4 does the job. | |
| 18 hours ago | comment | added | Emil Jeřábek | @StevenClark I’m not sure you understand what I wrote. The class of Kalmár elementary functions does allow bounded recursion, bounded sums, and products, hence it trivially contains $n!$. By results of the paper I mentioned, any such function can be constructed without recursion using just composition of basic integer functions $n+m$, $n\cdot m$, $n\mathbin{\dot{\smash-}}m$, $\lfloor n/m\rfloor$, $2^n$ (and even some of its subsets). This is a highly nontrivial result, and answers the question if the $-$ and $/$ operations are intended to be interpreted as the operations on $\mathbb N$. | |
| 22 hours ago | comment | added | Timothy Chow | Does this answer your question? Proof that the factorial is nonelementary and Expanded concept of elementary function? | |
| 23 hours ago | comment | added | Steven Clark | You reject the simple product representation $n! = \prod_{i=1}^{n} i$ which is generally considered to be closed form because it consists of a finite number of multiplication operations. If you're not allowing loop structures or tests on variables, this would also seem to prohibit sum or nested sum representations. You don't allow substitutions into functions with multiple variables. You can probably add enough restrictions to prohibit a solution, but the question seems rather artificial to me. | |
| yesterday | comment | added | Steven Clark | @EmilJeřábek You mention a paper about recursive functions. $n!$ can be evaluated as $f(n,1)$ where $f(n,r)$ is defined recursively as $f(n,r)=\left\{\begin{array}{cc} f(n-1,n r) & n>1 \\ r & \text{n=1} \\ \end{array}\right.$. | |
| yesterday | comment | added | Martin Brandenburg | @SamHopkins in an earlier comment you mentioned rational generating functions, but they don't cover $n^n$ for example (which is allowed). | |
| yesterday | comment | added | Martin Brandenburg | @SamHopkins That's a question from a different user from 2010. And the OP made clear that all these interpretations of formulas don't fit. | |
| yesterday | comment | added | Sam Hopkins | @MartinBrandenburg Is this really so clear from what the OP wrote? The sentence of the first link in their post says "I know that the Fibonacci sequence can be described via the Binet's formula." Of course, that formula uses constants other than natural numbers. So if the point is to show that $n!$ does not have a formula like the one for Fibonacci numbers, your interpretation might be too narrow. | |
| yesterday | history | edited | Martin Brandenburg | CC BY-SA 4.0 |
added 27 characters in body
|
| yesterday | comment | added | Martin Brandenburg | @te4 From the context it is absolutely clear that no complex numbers are allowed. I also made this clear in my edit now, I think the OP will agree. The OP wants a formula suitable for a 9-old (or rather a proof that such a formula doesn't exist). | |
| yesterday | comment | added | Martin Brandenburg | I have made a big edit (please revert if you don't approve) that I think will prevent further misunderstandings, downvotes, and close votes. | |
| yesterday | history | edited | Martin Brandenburg | CC BY-SA 4.0 |
deleted 211 characters in body; edited title
|
| yesterday | comment | added | Zach Teitler | Factorial grows faster than any polynomial in $n$ and faster than any exponential with constant base, so any closed form will need to involve something like $n^n$. But then it grows too fast. (I know that this is not a proof, just thinking out loud.) | |
| yesterday | history | edited | domotorp | CC BY-SA 4.0 |
added clarification
|
| yesterday | comment | added | te4 | I suppose your set $S$ is the minimal set of $f:\mathbb N\to k$ such that: i. Every constant function is in $S$. ii. $f(n)=n$ is in $S$. iii. If $f,g\in S$, then any of $f+g$, $-f$, $fg$, $1/f$, $f^g$ is in $S$ whenever well-defined for all $n\in\mathbb N$. In my opinion, the main issue with the question is that you haven't specified $k$. Namely, if $k=\mathbb C$, then $\exp(2\pi in/m)$ is periodic modulo $m$, so, by some geometric series, one concludes that $f-g[f/g]$ is in $S$ for $f,g\in S$, and then so is $n!$ by math.stackexchange.com/q/4605121/#comment9702994_4605121 | |
| yesterday | comment | added | Emil Jeřábek | It’s not clear to me whether you consider the basic operations on reals or on natural numbers. In the latter case, i.e., if the allowed operations are $n+m$, $n\cdot m$, $n\mathbin{\dot{\smash-}}m$, $\lfloor n/m\rfloor$, $n^m$ for $n,m\in\mathbb N$, there does exist such a closed formula for $n!$; in fact, such a closed formula exists for every Kalmár elementary function. This is apparently proved in Mazzanti, Plain bases for classes of primitive recursive functions, but I can’t access the paper at the moment. | |
| yesterday | comment | added | Carlo Beenakker | is differentiation allowed? $n!=\frac{d^n x^n}{dx^n}$ | |
| yesterday | comment | added | Sam Hopkins | I still don't completely understand what class of sequences you are trying to define, but maybe it is the same as those with rational generating functions (in other words, those satisfying a linear recurrence with constant coefficients)? | |
| yesterday | comment | added | domotorp | I agree with you all, as I wrote, I also don't expect that a closed formula would exist. What I want is a proof that it doesn't exist. | |
| yesterday | comment | added | Qiaochu Yuan | If you don't allow the use of constants such as $\pi$ and $e$ then I think you could attempt to argue that no such closed formula can have the correct asymptotics as given by Stirling's formula. | |
| yesterday | comment | added | domotorp | Because it uses the product symbol. I think I was quite precise. | |
| yesterday | comment | added | Sam Hopkins | I think you need to be very precise with your question for it to have a meaningful answer. You write "I am interested in the existence of a closed formula that uses only the four basic operations and exponential powers" but it is unclear why the definitional formula $n! = \prod_{j=1}^{n} j$ does not qualify according to this "definition." | |
| yesterday | history | asked | domotorp | CC BY-SA 4.0 |