![]() |
This time not stupid math
But it is a problem.
I'll leave out the context, because it's a bit extensive. These are the sequences I'm using: Triangular numbers: Square pyramidal numbers: (Does it have a name?) numbers: And so on and so on, each time increasing the power. --- These are (respectively) the formulas for the first two sequences: Triangular numbers: Square pyramidal numbers: Now what I want to know: 1. Does the third sequence have a name? :P 2. What is the formula for the third sequence? 3. How do you translate the formula of one sequence into the formula of the next sequence? I've tried a trial-and-error method, but that's prone to fail anyway. Does anyone know how to do it mathematically? --- P.S.: why are \cdots acting up? Solved it, not sure how. |
Re: This time not stupid math
Quote:
Quote:
^^ |
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 :p
|
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 :p
While wrecking my wrists, I'll find a different approach |
Re: This time not stupid math
Quote:
So I got that part done with by leaving the actual solution open. I'm still interested in the solution of the OP, though :p 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! :D 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? :p
|
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.
Quote:
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. |
Re: This time not stupid math
I wonder if you saw my 3rd edit at the end of my post while you were writing that. :P
Ok, so if you just wanted to sum x^19 from x=1 to 99, then you'd probably be best drawing out the Stirling triangle and doing the method I described. The recursion method I linked to in "edit 3" won't help you much, unless you wanted to know all the cases n=18, 17, 16, ... Good luck. :P |
Re: This time not stupid math
lol
|
Re: This time not stupid math
lol
|
Re: This time not stupid math
lol
|
Re: This time not stupid math
What the literal fuck O__O
That is so much neater than whatever methods have come up so far (generating functions and finite calculus and whatever). I can't see an obvious proof as to why that works, but hey, you might have just won this thread. |
Re: This time not stupid math
Oh jeez, I can't even watch sitcoms anymore or I'm behind with the times.
Ehhm, I'll have something to read on my free night tonight :p |
Re: This time not stupid math
What R did in his lengthy post looks familiar with what I know on this subject regarding generating functions, etc... of course, if you wanted to go through those steps 100 times... let's just say you'd rather eat lead. That program is definitely tidy.
|
Re: This time not stupid math
lol
|
Re: This time not stupid math
lol
|
Re: This time not stupid math
You can also use
http://en.wikipedia.org/wiki/Faulhaber%27s_formula With the recursive definition for the Bernoulli numbers defined here http://en.wikipedia.org/wiki/Bernoul...ive_definition But I mean it may as well just be this... Code:
def brute(x,y): |
Re: This time not stupid math
Hey Reincarnate, do you have a proof or at least a brief explanation for why the method you posted on the first page works?
|
Re: This time not stupid math
lol
|
Re: This time not stupid math
You learn something new every day. That page on Wolfram is actually quite enlightening! Thanks for posting.
|
| All times are GMT -5. The time now is 11:20 PM. |
Powered by vBulletin® Version 3.8.1
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.
Copyright FlashFlashRevolution