Given is a sequence of natural numbers: $1,2,…,n$.
I want to choose two elements $a,b$ of this sequence, calculate $c=ab+a+b$ and write $c$ back to the sequence. After $n-1$ iterations, there is only one element left. When I choose $n=10$ this element is: $39916799$
I have written this algorithm in Haskell:
foldl (\a b -> a*b+a+b) 0 [1..10]
and in Scala:
((1 to 10) foldLeft 0) {(a,b) => a*b+a+b}
Both work fine. Now I want to define this algorithm, which uses a fold, in mathematics. I came to this:
$$f: [1,n]n\in \mathbb N \rightarrow \mathbb N$$
$$f(p)=\cases{p_0p_1+p_0+p_1, &if\ |p|=2\cr f(p_0p_1+p_0+p_1+\sum\limits_{i=2}^n i), & else}$$
I don't think this is completely correct. For example, a interval is defined on $\mathbb R$ not $\mathbb N$ thus I don't know if it is possible to narrow it on $\mathbb N$. Can someone say me if it is possible to write a fold in mathematics and if yes, how?
Notice: I know, the fold is unnecessary because the result can be calculated with $(n+1)!-1$, but I want to know how to write such a fold in mathematics.
Best Answer
It is unclear what you mean by "represent the idea in mathematics", but I suspect that you're working from too high an assumption about of what mathematics requires. Except for a few very specialized fields, mathematics is not code. When you're writing mathematics, you're writing for people, and the only thing that matters is getting your point across as clearly as possible. Sometimes this calls for the use of formulas and symbolism; at other times it doesn't.
In this case, your initial informal presentation is quite understandable and therefore fine to use in an argument. The reader will, however, wonder whether it makes a difference for the result how you choose the two elements to operate on; you owe him some kind of proof that it doesn't. The most straightforward way to do this is to prove that the operation $(x,y)\mapsto xy+x+y$ is associative and commutative. With many audiences it will actually suffice just to assert that the operation is associative and commitative, leaving it to the reader to carry out the simple proofs if he doubts it. But you do have to at least assert it explicitly.
If you don't want to deal with the freedom to do the operation in different orders, you could say something like
Unless you're in a classroom setting where you're supposed to demonstrate that you know how to unfold "$\ldots$" into formally recursive definitions, this is perfectly acceptable, and much easier on the reader than the explicit recursion that you'd have to use to make yourself understood by a computer.