Simple Sequences and Series

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Excalibur0998
Posts: 14
Joined: Wed Sep 24, 2008 4:48 am UTC

Simple Sequences and Series

Postby Excalibur0998 » Wed Aug 26, 2009 12:33 am UTC

I've never been all that great at sequences and series...so I ran into a little bit of trouble when my roommate and I came up with a simple problem. The problem is an expression for the number of cups in beer pong based on how many rows there are. Just by guess and check, I found the expression [math]\sum_{i=1}^n i = \frac{n(n+1)} {2}[/math] Not too bad so far. By this time I remembered a friend of mine who made a pyramid of mountain dew cans (four sided pyramid) and I began trying to figure out how many cans there are based on how many rows of cans there are. I found that this problem was closely related to the previous problem and that the number of cans can be represented by [math]\frac{1}{2} \left ( \sum_{i=1}^n i + \sum_{i=1}^n i^2 \right )[/math] So now I had to find an expression for the sum of [imath]i^2[/imath] which we, after like an hour longer than it should've taken, found to be [math]\sum_{i=1}^n i^2 = \frac{2n^3 + 3n^2 + n} {6} = \frac{n(2n+1)(n+1)}{6}[/math] which means (I think) that the solution to the pyramid of cans problem would be [math]\frac{n^3 + 3n^2 + 2n} {6}[/math] And although I don't know if there's any 4th dimensional analog to what we were doing with the beer pong cups and the soda can pyramid, it got me thinking about an expression for [math]\sum_{i=1}^n i^b[/math] for any b. I've already noticed that it's going to be a polynomial of degree b, but that's about it.

So, how would I even go about thinking about expressing that? And also, how can I approach problems like these so that I don't spend hours filling whiteboards with guesses and random theories about how to go about finding a solution? Thanks.

User avatar
t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

Re: Simple Sequences and Series

Postby t0rajir0u » Wed Aug 26, 2009 1:36 am UTC

Excalibur0998 wrote:So, how would I even go about thinking about expressing that? And also, how can I approach problems like these so that I don't spend hours filling whiteboards with guesses and random theories about how to go about finding a solution? Thanks.

Since you've already figured out that it has to be a polynomial (although of one higher degree than you suggested), one way to approach this problem is to write down the coefficients of the polynomial and set up a system of linear equations for those coefficients based on the first few terms.

Of course, this is a lot of tedious algebra and doesn't generalize easily. The general formula for all [imath]b[/imath] is rather complex and proving it is surprisingly difficult; let me just point you towards a really nice way to cut down the computations you have to do for the above to work using Newton polynomials, which I also discuss here. Essentially what you're doing is triangularizing the system you would get above using the method of finite differences. One way to think about this theory is that sums are "discrete integration."

User avatar
Talith
Proved the Goldbach Conjecture
Posts: 848
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

Re: Simple Sequences and Series

Postby Talith » Wed Aug 26, 2009 1:45 am UTC

As t0rajir0u has said, the formula you're looking for is surprisingly difficult to form. If all you want is the general formula then i've spoilered it below, however if you want to know how to find the formula then I suggest following the links you've been provided.

Spoiler:
[math]\sum_{i=0}^n i^p = \frac{(n+1)^{p+1}}{p+1} + \sum_{k=1}^p\frac{B_k}{p-k+1}{p\choose k}(n+1)^{p-k+1}[/math] where [imath]B_k[/imath] is the ''k''th Bernoulli number

User avatar
antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: Simple Sequences and Series

Postby antonfire » Wed Aug 26, 2009 6:17 am UTC

Perhaps somewhat surprisingly, the formula for the number of cups in an k-dimensional pyramids of edge length n is a lot simpler. Hint: factor the polynomials in the answers you've already gotten.

Also, spending hours filling whiteboards with guesses and random theories is at least half the fun.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

Excalibur0998
Posts: 14
Joined: Wed Sep 24, 2008 4:48 am UTC

Re: Simple Sequences and Series

Postby Excalibur0998 » Wed Aug 26, 2009 6:10 pm UTC

antonfire wrote:Perhaps somewhat surprisingly, the formula for the number of cups in an k-dimensional pyramids of edge length n is a lot simpler. Hint: factor the polynomials in the answers you've already gotten.

Also, spending hours filling whiteboards with guesses and random theories is at least half the fun.


Dang. That solution that Talith posted is way more complicated than I could have imagined. Thanks for the links and info. So for the number of cups in a k-dimensional pyramid problem, I factored the term we found and got [math]\frac{n^3 + 3n^2 + 2n} {6} = \frac{n(n+1)(n+2)}{6}[/math] So, just looking at patterns, it looks like the general solution might be [math]\prod_{i=0}^k \frac{(n+k)}{k!}[/math]

Edit: clarification.

DavCrav
Posts: 251
Joined: Tue Aug 12, 2008 3:04 pm UTC
Location: Oxford, UK

Re: Simple Sequences and Series

Postby DavCrav » Fri Aug 28, 2009 10:26 am UTC

The one for the sum of cubes is quite fun, because it is the square of the sum of integers. That is,
[math]\sum_{i=1}^n i^3=\left(\sum_{i=1}^n i\right)^2.[/math]

User avatar
Talith
Proved the Goldbach Conjecture
Posts: 848
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

Re: Simple Sequences and Series

Postby Talith » Fri Aug 28, 2009 11:24 am UTC

DavCrav wrote:The one for the sum of cubes is quite fun, because it is the square of the sum of integers. That is,
[math]\sum_{i=1}^n i^3=\left(\sum_{i=1}^n i\right)^2.[/math]

Such a useful identity because the triangular number formula is easy enough to derive in 2 minutes, so if you want to know the sum of the frist 3 powers you only need to momeorise the quadratic.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 14 guests