Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
@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

2 Answers 2

up vote 5 down vote accepted

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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