Go Back   Flash Flash Revolution: Community Forums > General Discussion > Critical Thinking
Register FAQ Community Calendar Today's Posts Search

Reply
 
Thread Tools Display Modes
Old 03-20-2013, 07:27 AM   #1
SKG_Scintill
Spun a twirly fruitcake,
FFR Simfile AuthorFFR Veteran
 
SKG_Scintill's Avatar
 
Join Date: Feb 2009
Age: 28
Posts: 3,730
Default 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.
__________________





Quote:
Originally Posted by bluguerilla
So Sexy Robotnik (SKG_Scintill) {.0001/10} [--]
___
. RHYTHMS PR LAYERING
. ZOMG I HAD TO QUIT OUT TERRIBLE
.

Last edited by SKG_Scintill; 03-20-2013 at 08:25 AM..
SKG_Scintill is offline   Reply With Quote
Old 03-20-2013, 09:29 AM   #2
Netjet!
Sic itur ad astra
FFR Simfile AuthorFFR Veteran
 
Netjet!'s Avatar
 
Join Date: Jan 2008
Location: Ottawa, Canada
Age: 27
Posts: 4,692
Send a message via AIM to Netjet! Send a message via Skype™ to Netjet!
Default Re: This time not stupid math

Quote:
Originally Posted by SKG_Scintill View Post
(Does it have a name?) numbers:
And so on and so on, each time increasing the power.

Quote:
100 = 13 + 23 + 33 + 43 = 102, a square and also a sum of consecutive cubes. If you add more cubes, the results are always squares: 100+53 = 225 = 152; 225+63 = 441 = 212; 441+73 = 784 = 282, and so on. These numbers (1, 9, 36, 100, 225, 441, 784, ...) are "hyper-pyramidal" numbers (Sloane's A0537 or MCS3872). Their square roots (1, 3, 6, 10, 15, 21, 28, ...) are the triangular numbers.
http://oeis.org/A000537
^^
__________________
RIP Steve Van Ness <3
Netjet! is offline   Reply With Quote
Old 03-20-2013, 09:53 AM   #3
SKG_Scintill
Spun a twirly fruitcake,
FFR Simfile AuthorFFR Veteran
 
SKG_Scintill's Avatar
 
Join Date: Feb 2009
Age: 28
Posts: 3,730
Default 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
__________________





Quote:
Originally Posted by bluguerilla
So Sexy Robotnik (SKG_Scintill) {.0001/10} [--]
___
. RHYTHMS PR LAYERING
. ZOMG I HAD TO QUIT OUT TERRIBLE
.
SKG_Scintill is offline   Reply With Quote
Old 03-20-2013, 11:03 AM   #4
smartdude1212
2 is poo
FFR Simfile AuthorD7 Elite KeysmasherFFR Veteran
 
smartdude1212's Avatar
 
Join Date: Sep 2005
Age: 28
Posts: 6,620
Default 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.
smartdude1212 is offline   Reply With Quote
Old 03-20-2013, 11:05 AM   #5
SKG_Scintill
Spun a twirly fruitcake,
FFR Simfile AuthorFFR Veteran
 
SKG_Scintill's Avatar
 
Join Date: Feb 2009
Age: 28
Posts: 3,730
Default 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
__________________





Quote:
Originally Posted by bluguerilla
So Sexy Robotnik (SKG_Scintill) {.0001/10} [--]
___
. RHYTHMS PR LAYERING
. ZOMG I HAD TO QUIT OUT TERRIBLE
.
SKG_Scintill is offline   Reply With Quote
Old 03-20-2013, 11:58 AM   #6
SKG_Scintill
Spun a twirly fruitcake,
FFR Simfile AuthorFFR Veteran
 
SKG_Scintill's Avatar
 
Join Date: Feb 2009
Age: 28
Posts: 3,730
Default Re: This time not stupid math

Quote:
Originally Posted by SKG_Scintill View Post
I'll leave out the context, because it's a bit extensive.
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:
Originally Posted by bluguerilla
So Sexy Robotnik (SKG_Scintill) {.0001/10} [--]
___
. RHYTHMS PR LAYERING
. ZOMG I HAD TO QUIT OUT TERRIBLE
.

Last edited by SKG_Scintill; 03-20-2013 at 12:22 PM..
SKG_Scintill is offline   Reply With Quote
Old 03-20-2013, 12:06 PM   #7
iironiic
D6 FFR Legacy Player
FFR Simfile AuthorFFR Veteran
 
iironiic's Avatar
 
Join Date: Jan 2009
Age: 29
Posts: 4,211
Default 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.
iironiic is offline   Reply With Quote
Old 03-20-2013, 12:23 PM   #8
SKG_Scintill
Spun a twirly fruitcake,
FFR Simfile AuthorFFR Veteran
 
SKG_Scintill's Avatar
 
Join Date: Feb 2009
Age: 28
Posts: 3,730
Default 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
__________________





Quote:
Originally Posted by bluguerilla
So Sexy Robotnik (SKG_Scintill) {.0001/10} [--]
___
. RHYTHMS PR LAYERING
. ZOMG I HAD TO QUIT OUT TERRIBLE
.

Last edited by SKG_Scintill; 03-20-2013 at 12:41 PM..
SKG_Scintill is offline   Reply With Quote
Old 03-20-2013, 12:45 PM   #9
iironiic
D6 FFR Legacy Player
FFR Simfile AuthorFFR Veteran
 
iironiic's Avatar
 
Join Date: Jan 2009
Age: 29
Posts: 4,211
Default 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!
iironiic is offline   Reply With Quote
Old 03-20-2013, 12:51 PM   #10
SKG_Scintill
Spun a twirly fruitcake,
FFR Simfile AuthorFFR Veteran
 
SKG_Scintill's Avatar
 
Join Date: Feb 2009
Age: 28
Posts: 3,730
Default Re: This time not stupid math

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





Quote:
Originally Posted by bluguerilla
So Sexy Robotnik (SKG_Scintill) {.0001/10} [--]
___
. RHYTHMS PR LAYERING
. ZOMG I HAD TO QUIT OUT TERRIBLE
.
SKG_Scintill is offline   Reply With Quote
Old 03-20-2013, 12:56 PM   #11
qqwref
stepmania archaeologist
FFR Simfile AuthorFFR Veteran
 
qqwref's Avatar
 
Join Date: Aug 2005
Age: 31
Posts: 4,079
Send a message via AIM to qqwref Send a message via Skype™ to qqwref
Default 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
__________________
Stepmania Song Search - 1518 packs and counting!

Quote:
Originally Posted by jimerax View Post
Repeating, please no retarded files that aren't even going with the song
qqwref is offline   Reply With Quote
Old 03-20-2013, 01:18 PM   #12
SKG_Scintill
Spun a twirly fruitcake,
FFR Simfile AuthorFFR Veteran
 
SKG_Scintill's Avatar
 
Join Date: Feb 2009
Age: 28
Posts: 3,730
Default Re: This time not stupid math

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





Quote:
Originally Posted by bluguerilla
So Sexy Robotnik (SKG_Scintill) {.0001/10} [--]
___
. RHYTHMS PR LAYERING
. ZOMG I HAD TO QUIT OUT TERRIBLE
.
SKG_Scintill is offline   Reply With Quote
Old 03-20-2013, 01:33 PM   #13
reuben_tate
Kawaii Desu Ne?
Sectional ModeratorFFR Veteran
 
reuben_tate's Avatar
 
Join Date: Dec 2007
Location: The Kawaiian Island~
Age: 27
Posts: 4,130
Default 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)
__________________
AMA: http://ask.fm/benguino

Not happening now! Don't click to join!



Quote:
Originally Posted by Spenner View Post
(^)> peck peck says the heels
Quote:
Originally Posted by Xx{Midnight}xX
And god made ben, and realized he was doomed to miss. And said it was good.
Quote:
Originally Posted by Zakvvv666
awww :< crushing my dreams; was looking foward to you attempting to shoot yourself point blank and missing
reuben_tate is offline   Reply With Quote
Old 03-20-2013, 01:34 PM   #14
Zapmeister
FFR Player
 
Join Date: Sep 2012
Location: England
Posts: 466
Default 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
__________________

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

r1: 5
r2: 4
r3: 6
r4: 8
r5: 3
r6: 5
r7: 15
final position: 4th

Last edited by Zapmeister; 03-20-2013 at 03:10 PM..
Zapmeister is offline   Reply With Quote
Old 03-20-2013, 02:01 PM   #15
SKG_Scintill
Spun a twirly fruitcake,
FFR Simfile AuthorFFR Veteran
 
SKG_Scintill's Avatar
 
Join Date: Feb 2009
Age: 28
Posts: 3,730
Default Re: This time not stupid math

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

Quote:
Originally Posted by Zapmeister View Post
but seriously though. Why do you want to do this?
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.

11 12 13 14 15 16
21 22 23 24 25 26
31 32 33 34 35 36
41 42 43 44 45 46
51 52 53 54 55 56
61 62 63 64 65 66

1+2+3+4+5

111 112 113 114 115 116
121 122 123 124 125 126
131 132 133 134 135 136
141 142 143 144 145 146
151 152 153 154 155 156
161 162 163 164 165 166

211 212 213 214 215 216
221 222 223 224 225 226
231 232 233 234 235 236
241 242 243 244 245 246
251 252 253 254 255 256
261 262 263 264 265 266

311 312 313 314 315 316
321 322 323 324 325 326
331 332 333 334 335 336
341 342 343 344 345 346
351 352 353 354 355 356
361 362 363 364 365 366

411 412 413 414 415 416
421 422 423 424 425 426
431 432 433 434 435 436
441 442 443 444 445 446
451 452 453 454 455 456
461 462 463 464 465 466

511 512 513 514 515 516
521 522 523 524 525 526
531 532 533 534 535 536
541 542 543 544 545 546
551 552 553 554 555 556
561 562 563 564 565 566

611 612 613 614 615 616
621 622 623 624 625 626
631 632 633 634 635 636
641 642 643 644 645 646
651 652 653 654 655 656
661 662 663 664 665 666

1+4+9+16+25

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:
Originally Posted by bluguerilla
So Sexy Robotnik (SKG_Scintill) {.0001/10} [--]
___
. RHYTHMS PR LAYERING
. ZOMG I HAD TO QUIT OUT TERRIBLE
.

Last edited by SKG_Scintill; 03-20-2013 at 02:05 PM..
SKG_Scintill is offline   Reply With Quote
Old 03-20-2013, 02:07 PM   #16
Zapmeister
FFR Player
 
Join Date: Sep 2012
Location: England
Posts: 466
Default 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
__________________

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

r1: 5
r2: 4
r3: 6
r4: 8
r5: 3
r6: 5
r7: 15
final position: 4th
Zapmeister is offline   Reply With Quote
Old 03-20-2013, 02:17 PM   #17
Reincarnate
x'); DROP TABLE FFR;--
Sectional ModeratorFFR Veteran
 
Reincarnate's Avatar
 
Join Date: Nov 2010
Posts: 6,334
Default Re: This time not stupid math

lol

Last edited by Reincarnate; 09-8-2014 at 09:00 PM..
Reincarnate is offline   Reply With Quote
Old 03-20-2013, 02:52 PM   #18
Reincarnate
x'); DROP TABLE FFR;--
Sectional ModeratorFFR Veteran
 
Reincarnate's Avatar
 
Join Date: Nov 2010
Posts: 6,334
Default Re: This time not stupid math

lol

Last edited by Reincarnate; 09-8-2014 at 09:00 PM..
Reincarnate is offline   Reply With Quote
Old 03-20-2013, 03:13 PM   #19
Reincarnate
x'); DROP TABLE FFR;--
Sectional ModeratorFFR Veteran
 
Reincarnate's Avatar
 
Join Date: Nov 2010
Posts: 6,334
Default Re: This time not stupid math

lol

Last edited by Reincarnate; 09-8-2014 at 08:59 PM..
Reincarnate is offline   Reply With Quote
Old 03-20-2013, 03:23 PM   #20
Zapmeister
FFR Player
 
Join Date: Sep 2012
Location: England
Posts: 466
Default 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.
__________________

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

r1: 5
r2: 4
r3: 6
r4: 8
r5: 3
r6: 5
r7: 15
final position: 4th
Zapmeister is offline   Reply With Quote
Reply


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump



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