1
$\begingroup$

My question is: are expressions utilizing summation, $\Sigma$, and product, $\Pi$, operators considered 'closed-form'? To be more precise if the bounds in our summation/product operators contain variable quantities, is the expression still considered closed form?

For example, suppose that $f$ is a polynomial with real coefficients, and for every positive integer $n$, $P(n)$ is the set of all $n$-tuples $(k_1,\dots ,k_n) \in \mathbb{N_0}^n$ such that $k_1+2k_2+\dots+nk_n = n$, then is the expression $$\sum_{k \in P(n)}f(k_1+k_2+\dots+k_n)$$ considered a 'closed form expression', where $n$ is not an explicit positive integer, but say some positive integer valued variable. Say we define $g : \mathbb{N} \to \mathbb{R}$ by $$g(n) = \sum_{k \in P(n)}f(k_1+k_2+\dots+k_n)$$ and $g$ is the solution to some recurrence relation. Is $g$ a closed-form solution?

How about expressions like this? $$g(n) = \sum_{k_1=1}^{f_1(n)}\sum_{k_2=1}^{f_2(n)}\dots\sum_{k_n=1}^{f_n(n)}k_1+k_2+\dots+k_n$$ This type of expression can be rewritten as a single summation taken over a particular set whose elements depend on $n$ so it's equivalent to something like the first example, but would one only be considered closed form if the other was?

If they don't count as closed-form, are they considered analytic expressions?

I'm having trouble finding a definitive answer to these types of questions, is it really just vague and not agreed upon by the mathematical community what the precise formal definitions of things like 'closed-form expression', 'analytic expression', etc... should be?

Thank you for your time. Your input is very much appreciated.

$\endgroup$

closed as off-topic by Matthew Towers, Daniel W. Farlow, Shailesh, ml0105, user223391 Jul 21 '16 at 4:45

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Matthew Towers, Daniel W. Farlow, Shailesh, ml0105, Community
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Obligatory link: en.wikipedia.org/wiki/Closed-form_expression $\endgroup$ – Clement C. Jul 17 '16 at 16:46
  • $\begingroup$ Yes, I've read that article. But, if we have a finite summation like $\sum_{k=1}^{10}k$, then that's closed-form, or at least equivalent since it can be written as a sum of $10$ terms, but it doesn't address variable dependent bounds of summation. $\endgroup$ – DAS Jul 17 '16 at 17:38
3
$\begingroup$

The answer to your first question is: No, these are not closed forms. But as far as I know there is no standardised definition of closed-form.

It could be helpful to look what the experts tell us about it. We can read the following in section 1.2 of Concrete Mathematics written by D.E. Knuth, R.L. Graham and O. Patashnik:

D. Knuth, et al.: ... Incidentally we've been talking about closed forms without explicitely saying what we mean. Usually it's pretty clear.

Recurrences like \begin{align*} T_0&=0\\ T_n&=2T_{n-1}+1\qquad\qquad n>0 \end{align*} are not in closed form - they express a quantity in terms of itself; but solutions like \begin{align*} T_n=2^n-1\qquad\qquad n\geq 0 \end{align*} are. Sums like $$1+2+\cdots+n$$ are not in closed form - they cheat by using $\ldots$; but expressions like \begin{align*} \frac{n(n+1)}{2} \end{align*} are.

We could give a rough definition like this: An expression for quantity $f(n)$ is in closed form if we can compute it using at most a fixed number of well known standard operations, independent of $n$. For example, $2^n-1$ and $n(n+1)/2$ are closed forms because they involve only addition, subtraction, multiplication, division, and exponentiation, in explicit ways.

The total number of simple closed forms is limited, and there are recurrences that don't have simple forms. When such recurrences turn out to be important, because they arise repeatedly, we add new operations to our repertoire; this can greatly extend the range of problems solvable in simple closed form.

For example, the product of the first $n$ integers, $n!$, has proved to be so important that we now consider it a basic operation. The formula $n!$ is therefore in closed form, although its equivalent $1\cdot 2\cdots n$ is not.

$\endgroup$
  • $\begingroup$ Good answer. Do you think we would include things like $\sum_{k=1}^{1000}\log(k)$? I mean, if we view such an iterated operation with an explicit number of operations as a 'shorthand' for an expression consisting of $1000$ $\log$ terms and $999$ $+$ signs, which would be closed-form if it were written out? Not really feasible to write by hand. I've been operating under the assumption that such expressions are closed-form, just so long as there are no variable quantities in the bounds of the summation. $\endgroup$ – DAS Jul 17 '16 at 17:47
  • $\begingroup$ @DAS: You're welcome. Expressions using sigma or product symbols are not considered to be in closed form. Expressions with running indices are considered to be of the same type as expressions with $\ldots$ in Knuths answer. $\endgroup$ – Markus Scheuer Jul 17 '16 at 17:52
  • 1
    $\begingroup$ I'd upvote you twice if I could. Thank you! $\endgroup$ – DAS Jul 17 '16 at 17:53

Not the answer you're looking for? Browse other questions tagged or ask your own question.