Assignment 13

Advanced Placement Computer Science AB:
Assignment 13: Sums of Powers Of N
Sewickley Academy, 2000-2001

Date Assigned:	Fri Oct-13
Date Due:	Mon Oct-16

It is well known that the sum of the first N positive integers is N * (N+1) / 2. Thus,

1 + 2 + 3 + 4 + 5 = 5 * (5+1) / 2 = 5 * 3 = 15.

It is less well known, but equally true, that the sum of the squares of the first N positive integers is (N * (N+1) * (2N+1))/6. Thus,

1² + 2² + 3² + 4² + 5² = (5 * (5+1) * (2*5+1)) / 6 = (5 * 6 * 11)/6 = 55.

So, turns out (you can trust me on this one) that the sum of the first N positive integers raised to the k power is a (k+1) polynomial. So, you get:

1^k + 2^k + 3^k + ... + N^k = a_k+1N^k+1 + a_kN^k + a_k-1N^k-1 + ... + a₁N¹ + a₀

Let's express the two cases mentioned (k=1 and k=2) in this form:

k=1:

1¹+ 2¹ + 3¹ + ... + N¹ = N * (N+1) / 2 = (1/2) N² + (1/2) N¹ + 0
Hence: a₂ = 1/2, a₁ = 1/2, a₀ = 0

k=2:

1²+ 2² + 3² + ... + N² = (N * (N+1) * (2N+1))/6 = (1/3) N³ + (1/2) N² + (1/6) N¹ + 0
Hence: a₃ = 1/3, a₂ = 1/2, a₁ = 1/6, a₀ = 0

So far, so good. Now, to compute this polynomial for arbitrary k, note the following: To solve for the k+2 coefficients (a_k+1 to a₀), you need k+2 equations. But you can generate these using the first k+2 positive integers -- from N=1 to N=k+2. So, when N=1:

1^k= a_k+11^k+1 + a_k1^k + a_k-11^k-1 + ... + a₁1¹ + a₀= a_k+1 + a_k + a_k-1 + ... + a₁ + a₀

So when N=2:

1^k + 2^k = a_k+12^k+1 + a_k2^k + a_k-12^k-1 + ... + a₁2¹ + a₀

Continue in this fashion until you have created k+2 equations in k+2 unknowns. Special optional note (this may be safely ignored, and you will still get the right answer): consider the case when N=0. Here, all the a_i are eliminated except for a₀, and we also conclude that a₀ always equals 0 for any k. Thus, if you want, you can drop a₀ from your equations and use k+1 equations (from N=1 to N=k+1) in the remaining k+1 unknowns.

NOW... You use your Gaussian Elimination code from a previous assignment to solve for these k+2 variables. Output the polynomial in as natural and readable a form as you can muster.

You may want to confirm this polynomial actually works with a few randomly chosen N as well.

See Course Home Page.