# How to integrate simple discrete function

Let $n\in\mathbb{Z}^+$ I have a simple discrete function: $$\mathrm{acc}(n) = 8n$$

The discrete integral (is that the right term?) of that is: $$\mathrm{vel}(n) = \sum_{i=0}^n \mathrm{acc}(i)$$ the formula for which is: $$\mathrm{vel}(n) = 4(n^2+n)$$

Now my question. What's the discrete integral of $\mathrm{vel}(n)$ $$\mathrm{pos}(n) = \sum_{i=0}^n \mathrm{vel}(i)$$

What is the formula for directly calculating $pos(n)$? The normal rules of integration I learned at school don't seem to apply here.

-
@joriki: I deleted the "integration" tag. –  Américo Tavares Jun 18 '11 at 0:18
Take a look at Brian Hamrick's article on Discrete Calculus. –  Rahul Jun 18 '11 at 1:23
@Américo Tavares. Why delete the "integration" tag? According to Brian Hamrick's paper (link in the comment above) this is a discrete integral. –  Rocketmagnet Jun 20 '11 at 8:58
The current definition of "integration" is "All aspects of integration, including the definition of the integral and computing indefinite integrals (antiderivatives)." I was unsure about deleting it. If you think it should be restored, please do it, or let me know. –  Américo Tavares Jun 20 '11 at 18:10
I posted this meta question. –  Américo Tavares Jun 21 '11 at 9:19

Here's a list of summations that are useful for this sort of thing. For your case, you need $4$ times the sum of the results for $i^2$ and $i$, so you get

$$4\left(\frac{n(n+1)(2n+1)}{6}+\frac{n(n+1)}{2}\right)=2n(n+1)\left(\frac{2n+1}{3}+1\right)=\frac{4}{3}n(n+1)(n+2)\;.$$

-

I will tell a story. We have $n+2$ people, and their ages are $1$, $2$, $3$, $4$, and so on up to $n+2$.

We want to choose $3$ people from these $n+2$ people. The number of ways to do this is $$\binom{n+2}{3}=\frac{(n+2)(n+1)(n)}{3!}$$

Let us count the number of ways of choosing the $3$ people in another way.

Let us first count the number of ways to choose the $3$ people, if the youngest person chosen is to be the $1$ year-old. Then we must choose $2$ people to go with the $1$ year-old, and this can be done in $\binom{n+1}{2}$ ways.

Now count the number of ways to choose the people, if the youngest person chosen is to be $2$ years old. We must choose $2$ people from the $n$ people who are older than $2$. This can be done in $\binom{n}{2}$ ways.

Now count the number of ways to choose the people, if the youngest person chosen is to be $3$ years old. We must choose $2$ people from the $n-1$ people who are older than $3$. This can be done in $\binom{n-1}{2}$ ways.

Go on, and on. Finally, count the number of ways to choose $3$ people, if the youngest person chosen is $n$ years old. There is only $1$ way, of course, but for consistency I will call the number of ways $\binom{2}{2}$.

We conclude that $$\binom{n+2}{3}=\binom{n+1}{2}+\binom{n}{2}+\binom{n-1}{2}+\cdots +\binom{2}{2}$$

Now $\binom{n+1}{2}=\frac{(n+1)(n)}{2!}$, and $\binom{n}{2}=\frac{(n)(n-1)}{2!}$, and so on. Thus

$$\frac{(n+1)(n)}{2!}+ \frac{(n)(n-1)}{2!}+ \cdots +\frac{(2)(1)}{2!}=\frac{(n+2)(n+1)(n)}{3!}$$ Note that $2!=2$ and $3!=6$. Multiply both sides of our expression by $2$, and reverse the order of summation. We get $$\sum_0^n(i+1)(i)=\sum_1^n (i+1)(i)=\frac{(n+2)(n+1)(n)}{3}$$

So we have found an expression for our sum.

Comment: Almost exactly the same idea works in general, for computing related sums, such as $\sum_1^n (i+2)(i+1)(i)$. It turns out that finding sums of this type by the technique just described is far easier than, for example, multiplying $(i+2)(i+1)(i)$ out and using formulas for sums of powers. Combinatorial ideas are powerful!

It turns out that the easiest way to find formulas for sums of powers is to express these in terms of the sums we have just shown how to evaluate.

In some sense, a sum like $\sum_1^n (i+1)(i)$ is a more "natural" object than the more familiar $\sum_1^n i^2$.

-

There is a technique that would suffice as "discrete integration". It is described in this short paper.

Here is how you would solve this specific problem:

$$\sum_{i=0}^{n} 4(i^2+i)$$

First we need to transform the space of summation into the following form.

$$\sum_{i: 0 \rightarrow n+1} 4(i^2+i)$$

The reason for the n+1 is because the fundamental theorem of discrete calculus requires this (as shown in the paper: $\sum_{i=a}^{n} f(i) = \sum_{i: a\rightarrow n+1} f(i)$)

First isolate the constant, then transform the exponents of $n$ to falling powers:

$$4\sum_{i: 0 \rightarrow n+1} (i^{\underline{2}}+2i^{\underline{1}})$$ Where $$i^{\underline{2}} = i\cdot (i-1)$$ $$i^{\underline{1}} = i$$ Observe that $$i^{\underline{2}}+2i^{\underline{1}} = i^2-i+2i = i^2+i$$

Now we just integrate like we normally would, and evaluate: $$\left.4(\frac{i^{\underline{3}}}{3}+\frac{2}{2}i^{\underline{2}}) \right|_{i=0}^{n+1}$$ $$\left.4(\frac{i (i-1)(i-2)}{3}+i(i-1)) \right|_{i=0}^{n+1}$$ Factoring out: $$\left.4(\frac{(i-2)}{3}+1)i(i-1) \right|_{i=0}^{n+1}$$ Finally evaluating: $$4(\frac{(n-1)}{3}+1)(n+1)(n) - 4(0)$$

$$\Rightarrow pos(n) = 4(\frac{(n-1)}{3}+1)(n+1)(n) = \frac{4}{3}n(n+1)(n+2)$$

-