5
$\begingroup$

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.

  • 0
    I posted [this](http://meta.math.stackexchange.com/questions/2393/does-the-discrete-integral-belong-to-the-integration-tag) meta question.2011-06-21

3 Answers 3

6

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)\;.$

5

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$.

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) $