This time not stupid math

Re: This time not stupid math



^^

Re: This time not stupid math

Good to know they have a name, but I'm struggling to find the formula through the horrendous font

Re: This time not stupid math

I believe the formulae can be found using generating functions but that is perhaps a little more difficult than what you would like. Just look up almost anything related to Riemann sum integration and you should be able to find the formula.

Re: This time not stupid math

Will do, but I think it might get hairy, since I need to get up to k^100
While wrecking my wrists, I'll find a different approach

Re: This time not stupid math

Well I skipped some parts to the solution of the "context":

So I got that part done with by leaving the actual solution open.

I'm still interested in the solution of the OP, though
Riemann sum integration's gonna take me a while to understand.

P.S.: (I love P.S.'es) I don't think I'm allowed to just add the two summations together and say it's (n+1)(on the formula in this post that is).
Edit: I changed the formula again. I got the actual "put into google to make it solve it" equation. Turning it into a formula isn't exactly the easiest thing...

Re: This time not stupid math

Here (third row, third picture) is a proof without words.

The sum of the first n cubed numbers is equal to the square of the first n numbers. Therefore,




There might be more proofs of this, but this is one I thought of immediately haha.

Re: This time not stupid math

You and your college education

Still, that's the second question answered. So thanks!
Yet, you made that third question a whole lot more difficult to see...

1.

2.

3.

HNNNNNG
Though I have a feeling even and odd powers follow different formulas

Re: This time not stupid math

For the third question, you can use generating functions and convolutions to determine this. This is a good practice problem for my Combinatorics midterm tomorrow :P

I'll get back onto that soon!

Re: This time not stupid math

That's interesting given that my current math class is combinatorics, only community college level

Re: This time not stupid math

As far as I know there is no easy way to go from one sum to the next (there isn't any nice recursion of that form). All you are probably going to find is closed-form representations where you can plug in n to get the sum of k^n. There is some useful info over at http://mathworld.wolfram.com/PowerSum.html

Re: This time not stupid math

Doesn't that mean that someone can graduate from college by figuring it out?

Re: This time not stupid math

I'd call that last one "snowman" numbers if I could, haha (you'd just have different sized cubes instead of spheres xP)

Re: This time not stupid math

Ok i think i have a shot at this.

iironiic got the formula for the sum of the first n cubes right, but it seems you're looking for a general formula for the sum of the first m-th powers in general, it's kind of convoluted.

Most of what i'm about to write is described in more detail here: http://www.cs.purdue.edu/homes/dglei...20calculus.pdf (skip section 2)

Your motivation: to find the sum of the first n m-th powers in general. So let's say you want to find the sum of the first n cubes, like you said in the OP. Wouldn't it be nice if writing the sum was a bit like writing an integral? You could pretend you're integrating x^3 instead of summing k^3 from 1 to n.

Unfortunately, that doesn't work. If you integrate x^3, you get x^4/4, and that's not the same as iironiic's formula x^2*(x+1)^2/4. Oh well. What do we do instead? Well it's pretty close, I mean you've got your 4th degree polynomial, and you've got your divide-by-4, so maybe you could find some way to rectify that situation.

Define the finite difference D f(x) of a function f(x) to be:
D f(x) = f(x+1) - f(x)
(the article uses a triangle symbol, but i'm seriously not bothered with getting out character map for this, so i'll stick with D)
It's a bit like taking the derivative by doing the difference quotient (f(x+h)-f(x))/h, except instead of letting h->0, you let h->1.

Examples:
What's D x? answer: D x = (x+1) - (x) = 1
What's D x(x-1)? answer: D x(x-1) = (x+1)x - x(x-1) = 2x
What's D x(x-1)(x-2)? answer: ok you can work it out yourself. it's 3x(x-1)
What's D x(x-1)(x-2)(x-3)? answer: it's 4x(x-1)(x-2)

It's a case of spot the pattern. You've got these things on the left that look like powers, but slightly different, and on the right, when you take the finite difference, they behave like you're doing a differentiation. It makes sense if you give these things a name. We call them "falling powers" and write x^k for x(x-1)(x-2)...(x-k+1). Then you get this rule

D x^k = k x^k-1

Proof: work it out yourself, or check theorem 3.1

Ok, so you've got your analogue of differentiation. What's integration? That's basically just summation. We distinguish between the indefinite sum and the definite sum (article says "discrete anti-derivative" for the latter... never heard of it). The indefinite sum is just your finite difference, but backwards.

sum k x^k-1 = x^k + Y, where Y is a constant which stands for "Y do we care?", because it's a complete irrelevance.

The definite sum is like this but you put limits in it. Here you have to be careful. It turns out that this is true:

sum from x=a to b D f(x) = f(b+1) - f(a).

There's a b+1 in the upper limit, not a b. That's because of the x+1 in the definition of the finite difference.
Proof: write D f(x) = f(x+1) - f(x) and write out the sum and then all the terms in the middle cancel out and you're left with f(b+1) from the upper limit and f(a) from the lower limit.

So now you've got the basic concepts of "differentiation and integration" down for this finite-difference case. What can we do with them? Read the article for more stuff about it, but you can create analogues of the product rule, and integration by parts, and e^x, and stuff, for the finite case. The falling-power formula also works for negative powers too. (see sections 3.5 and 3.6)

Back to what we started with: finding the sum of k^3 from 1 to n. The plan: rewrite k^3 in terms of falling powers, pretend to integrate them, and then rewrite your answer back in terms of normal-flavoured powers. That's all well and good, until you realise you don't have a general way to do the first step. Here's where Stirling numbers come in.

Stirling numbers: Define the Stirling number of the second kind {n,k} to be the coefficient of x^k in the falling power expansion of x^n. Like this:
x^n = sum from k=0 to n of {n,k}*x^k

I'll leave you to read the relevant bits of the article for the actual definition and a bunch of amazing properties that you automatically get with Stirling numbers of the second kind. For your purposes, here are the first few:

x^1 = x^1
x^2 = x^2 + x^1
x^3 = x^3 + 3 x^2 + x^1
x^4 = x^4 + 7 x^3 + 6 x^2 + x^1

and you get this nice little triangle (Stirling's triangle)
(k=... 1 2 3 4)
(n=1) 1
(n=2) 1 1
(n=3) 1 3 1
(n=4) 1 7 6 1
and to get {n,k} the formula is {n,k} = k*{n-1,k} + {n-1,k-1}. Have fun drawing the triangle out a bit like Pascal's triangle.

So if you wanted to find the sum of k^3 from 1 to n, you'd write:

x^3 = x^3 + 3 x^2 + x^1
pretend to integrate: x^4/4 + x^3 + x^2/2
your limits are 1 and n+1, but your lower limit 1 doesn't do anything because your falling powers all have a zero in them, so you get (n+1)^4/4 + (n+1)^3 + (n+1)^2/2
= (n+1)(n)(n-1)(n-2)/4 + (n+1)(n)(n-1) + (n+1)(n)/2
= (n+1)(n)[(n-1)(n-2)/4 + (n-1) + 1/2]
= (n+1)(n)[(n^2-3n+2)/4 + n - 1/2]
= (n+1)(n)[(n^2+n)/4]
= n^2*(n+1)^2/4

voila.

If you wanted to get the sum of k^4 from 1 to n, just... do the same thing, I guess. You should get:
n(n+1)(2n+1)(3n^2+3n+1)/30

But your question was about getting from one formlula to the next. So what you could do is do the above process backwards, then change the Stirling coefficients, then do it forwards again. But seriously, I can't see ANY REASON AT ALL as to WHY anyone would want to do that. It would be twice as fast to just get the formula straight off the above method for each case. (edit: Actually, no, ignore that. Finding the new Stirling numbers from the recursion is MUCH FASTER than working them straight out. Silly me.) (edit 2: Actually, no. Retract that edit, since you're going to need to do the Stirling number computation anyway to do step 1 of the below. So it's still twice the effort.) But I'm not one to question your motives, so here we go.


...

Ok, so for the answer to the question: How to get from one formula to the next?
answer:
(1) convert your answer into falling powers
(2) take the finite difference of each one (i.e. "pretend to differentiate")
(3) change the Stirling numbers according to the formula {n,k} = k*{n-1,k} + {n-1,k-1}
(4) take the indefinite sum of each one (i.e. "pretend to integrate")
(5) substitute x=n+1 and expand out (edit 5: on second thoughts this method is probably too impractical)

but seriously though. Why do you want to do this?




































edit 3: OH MY GOD. DAMN DAMN DAMN DAMN DAMN DAMN. I didn't realise you could do this: http://www.trans4mind.com/personal_d...ralNumbers.htm If you only wanted a recursive formula, you can basically forget everything I wrote in the rest of this post. I can't believe I just wasted like 30 mins.

*headdesk*

edit 4: typos and stuff

Re: This time not stupid math

Ouch, that's rough, but it was kind of what I was expecting.

The possible solutions for "x ∈ ℕ" people throwing a dice with "y ∈ ℕ" sides where a person wins on the first dice throw. Leaving out ties, obviously.



You can see where this is going; 4 people is going to take too long to type.

---

You can solve these by putting the summation in a calculator, sure. But it gets a bit long when you're working with 20 people and chances between 1 and 100. Or rather: "x ∈ ℕ" people with "y ∈ ℕ" options.
That's why I was trying to expand the already existing formulas of triangular numbers and square pyramidal numbers to figurate number sequences of n-dimensional pyramids.