|
|
#1 | |
|
Spun a twirly fruitcake,
Join Date: Feb 2009
Age: 28
Posts: 3,730
|
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.
__________________
Quote:
Last edited by SKG_Scintill; 03-20-2013 at 08:25 AM.. |
|
|
|
|
|
|
#2 | ||
|
Sic itur ad astra
|
Quote:
Quote:
^^
__________________
RIP Steve Van Ness <3 |
||
|
|
|
|
|
#3 | |
|
Spun a twirly fruitcake,
Join Date: Feb 2009
Age: 28
Posts: 3,730
|
Good to know they have a name, but I'm struggling to find the formula through the horrendous font
![]()
__________________
Quote:
|
|
|
|
|
|
|
#4 |
|
2 is poo
Join Date: Sep 2005
Age: 28
Posts: 6,620
|
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.
|
|
|
|
|
|
#5 | |
|
Spun a twirly fruitcake,
Join Date: Feb 2009
Age: 28
Posts: 3,730
|
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
__________________
Quote:
|
|
|
|
|
|
|
#6 | |
|
Spun a twirly fruitcake,
Join Date: Feb 2009
Age: 28
Posts: 3,730
|
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...
__________________
Quote:
Last edited by SKG_Scintill; 03-20-2013 at 12:22 PM.. |
|
|
|
|
|
|
#7 |
|
D6 FFR Legacy Player
Join Date: Jan 2009
Age: 29
Posts: 4,211
|
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. |
|
|
|
|
|
#8 | |
|
Spun a twirly fruitcake,
Join Date: Feb 2009
Age: 28
Posts: 3,730
|
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
__________________
Quote:
Last edited by SKG_Scintill; 03-20-2013 at 12:41 PM.. |
|
|
|
|
|
|
#9 |
|
D6 FFR Legacy Player
Join Date: Jan 2009
Age: 29
Posts: 4,211
|
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! |
|
|
|
|
|
#10 | |
|
Spun a twirly fruitcake,
Join Date: Feb 2009
Age: 28
Posts: 3,730
|
That's interesting given that my current math class is combinatorics, only community college level
__________________
Quote:
|
|
|
|
|
|
|
#11 |
|
stepmania archaeologist
|
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
|
|
|
|
|
|
#12 | |
|
Spun a twirly fruitcake,
Join Date: Feb 2009
Age: 28
Posts: 3,730
|
Doesn't that mean that someone can graduate from college by figuring it out?
![]()
__________________
Quote:
|
|
|
|
|
|
|
#13 |
|
Kawaii Desu Ne?
Join Date: Dec 2007
Location: The Kawaiian Island~
Age: 27
Posts: 4,130
|
I'd call that last one "snowman" numbers if I could, haha (you'd just have different sized cubes instead of spheres xP)
|
|
|
|
|
|
#14 |
|
FFR Player
Join Date: Sep 2012
Location: England
Posts: 466
|
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
__________________
![]() Theorem: If you have a large enough number of monkeys, and a large enough number of computer keyboards, one of them will sight-read AAA death piano on stealth. And the ffr community will forever worship it. Proof Example ask me anything here mashed FCs: 329 Last edited by Zapmeister; 03-20-2013 at 03:10 PM.. |
|
|
|
|
|
#15 | |
|
Spun a twirly fruitcake,
Join Date: Feb 2009
Age: 28
Posts: 3,730
|
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.
__________________
Quote:
Last edited by SKG_Scintill; 03-20-2013 at 02:05 PM.. |
|
|
|
|
|
|
#16 |
|
FFR Player
Join Date: Sep 2012
Location: England
Posts: 466
|
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
__________________
![]() Theorem: If you have a large enough number of monkeys, and a large enough number of computer keyboards, one of them will sight-read AAA death piano on stealth. And the ffr community will forever worship it. Proof Example ask me anything here mashed FCs: 329 |
|
|
|
|
|
#17 |
|
x'); DROP TABLE FFR;--
Join Date: Nov 2010
Posts: 6,334
|
lol
Last edited by Reincarnate; 09-8-2014 at 09:00 PM.. |
|
|
|
|
|
#18 |
|
x'); DROP TABLE FFR;--
Join Date: Nov 2010
Posts: 6,334
|
lol
Last edited by Reincarnate; 09-8-2014 at 09:00 PM.. |
|
|
|
|
|
#19 |
|
x'); DROP TABLE FFR;--
Join Date: Nov 2010
Posts: 6,334
|
lol
Last edited by Reincarnate; 09-8-2014 at 08:59 PM.. |
|
|
|
|
|
#20 |
|
FFR Player
Join Date: Sep 2012
Location: England
Posts: 466
|
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.
__________________
![]() Theorem: If you have a large enough number of monkeys, and a large enough number of computer keyboards, one of them will sight-read AAA death piano on stealth. And the ffr community will forever worship it. Proof Example ask me anything here mashed FCs: 329 |
|
|
|
![]() |
| Currently Active Users Viewing This Thread: 1 (0 members and 1 guests) | |
|
|