# Summing fom 1 to n^x for various values of x **URL:** \ **Category:** Factual Questions\ **Created:** [February 18, 2006, 5:23am UTC](https://boards.straightdope.com/t/summing-fom-1-to-n-x-for-various-values-of-x/345055 "2006-02-18T05:23:46Z")\ **Posts on this page:** 16\ **Page:** 1
**Author:** ![Captain\_Carrot](https://avatars.discourse-cdn.com/v4/letter/c/f0a364/32.png) [@Captain\_Carrot](https://boards.straightdope.com/u/Captain_Carrot)\ **Post date:** [February 18, 2006, 5:23am UTC](https://boards.straightdope.com/t/summing-fom-1-to-n-x-for-various-values-of-x/345055/1 "2006-02-18T05:23:46Z")
I’ve been working on and off on a formula that will generate the sum of n^x from 1 to n, given n and x. (This morning, I borrowed a classmate’s TI-92 and got x=4-10 formulas. I must have this calculator!) I looked on Wikipedia, and they said that the function to do that is [recursive](http://en.wikipedia.org/wiki/Summation) ([indirectly](http://en.wikipedia.org/wiki/Bernoulli_number)). Is that proven? ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [February 18, 2006, 5:56am UTC](https://boards.straightdope.com/t/summing-fom-1-to-n-x-for-various-values-of-x/345055/2 "2006-02-18T05:56:30Z")
Every Turing-computable function in **N** -\> **N** is [recursive](http://en.wikipedia.org/wiki/Recursive_function). ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [February 18, 2006, 6:11am UTC](https://boards.straightdope.com/t/summing-fom-1-to-n-x-for-various-values-of-x/345055/3 "2006-02-18T06:11:55Z")
Note the double meaning of “recursive.” Def. 1: Something defined or computed in terms of itself. Def. 2: Computable by a Turing machine (or equivalent) that halts on all inputs. (In the 1920s, some people thought all computable functions could be defined in terms of simple recursion. Hence the historical basis for using “recursive” to mean “computable.”) The first definition applies here. The Bernoulli numbers _can be_ computed recursively. But they don’t have to be. In fact, nothing has to be computed recursively at all so there can never be a proof that states that recursion is required to compute anything. (And it is usually a Very Good Thing to avoid recursion for efficiency reasons.) ---
**Author:** ![Mathochist](https://avatars.discourse-cdn.com/v4/letter/m/c89c15/32.png) [@Mathochist](https://boards.straightdope.com/u/Mathochist)\ **Post date:** [February 18, 2006, 8:05am UTC](https://boards.straightdope.com/t/summing-fom-1-to-n-x-for-various-values-of-x/345055/4 "2006-02-18T08:05:24Z")
> [@ftg](#): > > (In the 1920s, some people thought all computable functions could be defined in terms of simple recursion. Hence the historical basis for using “recursive” to mean “computable.”) Define “simple recursion”. The fact that Lambda calculi and Turing machines are equivalent proves that their classes of computable functions are identical, and (AFAIK) nobody’s come up with a more general sense of computability. ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [February 18, 2006, 12:47pm UTC](https://boards.straightdope.com/t/summing-fom-1-to-n-x-for-various-values-of-x/345055/5 "2006-02-18T12:47:18Z")
> [@Mathochist](#): > > Define “simple recursion”. The fact that Lambda calculi and Turing machines are equivalent proves that their classes of computable functions are identical, and (AFAIK) nobody’s come up with a more general sense of computability. One (of several) methods to define a **subset** of computable functions using recursion are the [primitive recursive functions](http://en.wikipedia.org/wiki/Primitive_recursive). A proof of a computable non-primitive recursive function was given by [Ackermann](http://en.wikipedia.org/wiki/Ackermann_function) in 1928. ---
**Author:** ![Mathochist](https://avatars.discourse-cdn.com/v4/letter/m/c89c15/32.png) [@Mathochist](https://boards.straightdope.com/u/Mathochist)\ **Post date:** [February 18, 2006, 4:36pm UTC](https://boards.straightdope.com/t/summing-fom-1-to-n-x-for-various-values-of-x/345055/6 "2006-02-18T16:36:54Z")
> [@ftg](#): > > One (of several) methods to define a **subset** of computable functions using recursion are the [primitive recursive functions](http://en.wikipedia.org/wiki/Primitive_recursive). A proof of a computable non-primitive recursive function was given by [Ackermann](http://en.wikipedia.org/wiki/Ackermann_function) in 1928. I still think your implication that the use of the term “recursive” for “computable” is less than accurate is somewhat misleading. The Ackermann function may not be primitive-recursive, but it _is_ recursive. Every computable function is, unless you’ve got a revolutionary discovery you’re keeping from the rest of us. ---
**Author:** ![chrisk](https://avatars.discourse-cdn.com/v4/letter/c/6de8d8/32.png) [@chrisk](https://boards.straightdope.com/u/chrisk)\ **Post date:** [February 18, 2006, 4:40pm UTC](https://boards.straightdope.com/t/summing-fom-1-to-n-x-for-various-values-of-x/345055/7 "2006-02-18T16:40:05Z")
> [@Mathochist](#): > > I still think your implication that the use of the term “recursive” for “computable” is less than accurate is somewhat misleading. The Ackermann function may not be primitive-recursive, but it _is_ recursive. Every computable function is, unless you’ve got a revolutionary discovery you’re keeping from the rest of us. Yes, but you asked him to define ‘simple recursion’ and he presented primitive-recursion, which seems to fit the distinction he was implying earlier on. Can we agree to handshake and make nice at this point? 😉 ---
**Author:** ![Mathochist](https://avatars.discourse-cdn.com/v4/letter/m/c89c15/32.png) [@Mathochist](https://boards.straightdope.com/u/Mathochist)\ **Post date:** [February 18, 2006, 4:55pm UTC](https://boards.straightdope.com/t/summing-fom-1-to-n-x-for-various-values-of-x/345055/8 "2006-02-18T16:55:58Z")
> [@chrisk](#): > > Yes, but you asked him to define ‘simple recursion’ and he presented primitive-recursion, which seems to fit the distinction he was implying earlier on. Oh, I agree that he defined the term I was asking about. That’s not the point. > [@ftg](#): > > In the 1920s, some people thought all computable functions could be defined in terms of simple recursion. Hence the historical basis for using “recursive” to mean “computable.” This parses as “It’s inaccurate to use ‘recursive’ to mean ‘computable’, but we do anyway because someone made a mistake way back”. If the assertion was that it’s inaccurate to use _“primitive recursive”_ to mean computable, that would be fine. “Recursive” is more general than “primitive recursive”, however. The basis for using “recursive” to mean “computable” is (a) the well-established equivalence of the Lambda calculus (general recursive functions) and Turing machines (Turing computable functions) (b) the Church-Turing Theses that these two equivalent classes of functions are the only ones that can be computed in any meaningful sense. Bringing up the mistake people made about primitive recursion can only serve to slam recursion in general, when in fact it’s a particularly elegant mode of computation. **ftg** may not like it in practice for various reasons, but it runs rings 'round Turing’s approach in a number of theoretical uses, such as proving fixed-point theorems. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [February 18, 2006, 5:05pm UTC](https://boards.straightdope.com/t/summing-fom-1-to-n-x-for-various-values-of-x/345055/9 "2006-02-18T17:05:28Z")
> [@Mathochist](#): > > **ftg** may not like it in practice for various reasons, but it runs rings 'round Turing’s approach in a number of theoretical uses, such as proving fixed-point theorems. **ftg** ’s not talking about recursion as a model of computation. He’s talking about recursion as a programming practice, where it really is best to avoid it wherever possible. ---
**Author:** ![Mathochist](https://avatars.discourse-cdn.com/v4/letter/m/c89c15/32.png) [@Mathochist](https://boards.straightdope.com/u/Mathochist)\ **Post date:** [February 18, 2006, 5:12pm UTC](https://boards.straightdope.com/t/summing-fom-1-to-n-x-for-various-values-of-x/345055/10 "2006-02-18T17:12:00Z")
> [@ultrafilter](#): > > **ftg** ’s not talking about recursion as a model of computation. He’s talking about recursion as a programming practice, where it really is best to avoid it wherever possible. He was at the end of his post, but his claim about “historical basis” was blatantly false. “Recursive = Computable” is _not_ about programming practice. Further, the OP was questioning that a given function was called “recursive” in the computability-theory sense, not in a practical sense. ---
**Author:** ![Capt.Ridley\_s\_Shooting\_Party](https://avatars.discourse-cdn.com/v4/letter/c/cc9497/32.png) [@Capt.Ridley\_s\_Shooting\_Party](https://boards.straightdope.com/u/Capt.Ridley_s_Shooting_Party)\ **Post date:** [February 18, 2006, 5:29pm UTC](https://boards.straightdope.com/t/summing-fom-1-to-n-x-for-various-values-of-x/345055/11 "2006-02-18T17:29:35Z")
> [@ultrafilter](#): > > **ftg** ’s not talking about recursion as a model of computation. He’s talking about recursion as a programming practice, where it really is best to avoid it wherever possible. In some languages, perhaps 😉 ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [February 18, 2006, 10:52pm UTC](https://boards.straightdope.com/t/summing-fom-1-to-n-x-for-various-values-of-x/345055/12 "2006-02-18T22:52:51Z")
**Mathochist** : You have completely and totally misread both my posts. What you think I said and what I actually said are two different things. Note in particular your use of the word “implication”. You definitely are making a mistake there. The mistakes you are “finding” are in your misreading, not in my posts. ---
**Author:** ![Captain\_Carrot](https://avatars.discourse-cdn.com/v4/letter/c/f0a364/32.png) [@Captain\_Carrot](https://boards.straightdope.com/u/Captain_Carrot)\ **Post date:** [February 19, 2006, 4:36am UTC](https://boards.straightdope.com/t/summing-fom-1-to-n-x-for-various-values-of-x/345055/13 "2006-02-19T04:36:19Z")
I wish I’d known about the other meaning of recursive when I first posted this thread, to avoid this mess. I meant that (it looked like) they said it could only be done recursively. I’ve used Mathematica and Excel to generate the summation formulas for x up to 16, and I’ve noticed a whole lot of patterns in the coefficients of the completely expanded formulas. (They all come from Pascal’s triangle) ---
**Author:** ![Mathochist](https://avatars.discourse-cdn.com/v4/letter/m/c89c15/32.png) [@Mathochist](https://boards.straightdope.com/u/Mathochist)\ **Post date:** [February 19, 2006, 4:47pm UTC](https://boards.straightdope.com/t/summing-fom-1-to-n-x-for-various-values-of-x/345055/14 "2006-02-19T16:47:50Z")
> [@ftg](#): > > **Mathochist** : You have completely and totally misread both my posts. What you think I said and what I actually said are two different things. Note in particular your use of the word “implication”. You definitely are making a mistake there. > > The mistakes you are “finding” are in your misreading, not in my posts. Okay, then would you more clearly explain yourself? You assert that the fact that “in the 1920s, some people thought all computable functions could be defined in terms of simple recursion” is “the historical basis for using ‘recursive’ to mean ‘computable’”, do you not? What is the purpose of this parenthetical other than to explain a (false) distinction between your two given definitions? In fact, let’s look at those, which were really the core of your post: > [@](#): > > Note the double meaning of “recursive.” > > Def. 1: Something defined or computed in terms of itself. > > Def. 2: Computable by a Turing machine (or equivalent) that halts on all inputs. Now, definition 1 is rather fuzzy, but I don’t see how it differs from the method of an untyped lambda calculus. If that’s the case, then it _is_ equivalent to a Turing machine, so there’s no difference in your definitions at all. Really it comes down to this: do you assert that there’s any difference between the classes of recursive functions and (Turing-)computable functions? If so, what exact difference do you see? ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [February 19, 2006, 8:58pm UTC](https://boards.straightdope.com/t/summing-fom-1-to-n-x-for-various-values-of-x/345055/15 "2006-02-19T20:58:58Z")
```auto int function Forever(int n) { return Forever(n); } ``` Forever is recursive in that it calls itself. It is not recursive in being computable by a Turing machine/Lambda calculus/Post system/mu-recursive system, etc. The [Arithmetical hierarchy](http://en.wikipedia.org/wiki/Arithmetical_hierarchy) itself is defined recursively! Words can have two meanings, in this case, very close meanings that make sense if you know the history. ---
**Author:** ![Mathochist](https://avatars.discourse-cdn.com/v4/letter/m/c89c15/32.png) [@Mathochist](https://boards.straightdope.com/u/Mathochist)\ **Post date:** [February 19, 2006, 10:47pm UTC](https://boards.straightdope.com/t/summing-fom-1-to-n-x-for-various-values-of-x/345055/16 "2006-02-19T22:47:11Z")
> [@ftg](#): > > ```auto > > int function Forever(int n) > { > return Forever(n); > } > > ``` Ah, _there’s_ the distinction. My mistake was reading your “functions defined in terms of themselves” the way everyone seems to use it casually, with various unspoken riders about either well-definedness or bottoming-out. Also, I assumed that you meant both definitions as technical senses applicable to the situation at hand rather than one a technical definition and one a general one.