[Monte314]

I had thought about using the Binomial Theorem, but it made my eyes glaze over. Perhaps I should reconsider...

[Latro]

Originally Posted by roninpro To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.

I just wanted to add a little more commentary about this approach and draw a bonus conclusion about the sum of consecutive cubes. [HIDE="Commentary"] What this method shows us is that the sum of the first n consecutive k-th powers is that the sum can be represented by a (k + 1)-degree polynomial. Knowing this, we can convert the problem to a polynomial fitting problem. To illustrate this, we can try it on the sum of the first consecutive cubes. From the previous method, we already know that the sum will be represented by a degree four polynomial. Using Lagrange Interpolation, we only need to sample five sums, and we can recover the polynomial. Let S[n] be the sum of the first n cubes. By direct computation, we have S[1] = 1 S[2] = 9 S[3] = 36 S[4] = 100 S[5] = 225 Running the interpolation procedure gives S[n] = n^4 / 4 + n ^3 / 2 + n^2 / 4 = [n (n + 1) / 2]^2 which is the well-known formula for this sum. This method translates our problem about arbitrary sums to one that involves concrete sums. It also converts everything into a problem about Linear Algebra, which is pretty well-understood, so there are a lot of tools to work with. I don't know if this method would necessarily lead to an explicit formula for all powers k, since it would require knowing expressions for the values of S[n] from 1 to k + 2. It would also involve trying to deal with a Vandermonde matrix, which may or may not have an obvious structure (it is dependent on the expression for S[n]). [/HIDE]

The biggest spoiler so far here:

( Show Spoiler )

This interpolation approach is in fact the approach I used. It does lead to an explicit formula if you're clever about it. Technically the Lagrange form already is an explicit formula, but it's not the one I have in mind, as it is extremely cumbersome to work with.

Also, K27:

( Show Spoiler )

As we discussed before, you can use the binomial theorem to relate f(n,k) to values of f for smaller k if k is odd, so if you have a general solution for when k is even you can construct a general solution for when k is odd as well (though it is recursive).

[roninpro]

Originally Posted by K27 To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.

[HIDE="spoiler"] The first column is the position, the second column is the actual odd number series, the third is the sum of the numbers in the second column UP TO THAT POSITION. 1 1 1 ^2 ^4 ^6 2 3 4 ^2 3 5 9 ^2 4 7 16 ^2 ^4 5 9 25 ^2 6 11 36 ^2 7 13 49 ^2 8 15 64 ^2 ^6 9 17 81 ^2 ^4 10 19 100 ^2 Observe that by adding up the third column you get the sum of the first squares. So essentially, looking at the odd number series, you are adding 1st, then 1st to 2nd, then 1st to 3rd, etc. etc. For n^4, you are adding1, 1st to 4th, then 1st to 9th, which is the series of the squares ... You see the pattern. I don't know how to translate this into equation though ...[/HIDE] ---------- Post added 05-30-2012 at 12:37 AM ---------- [HIDE="nailed the one for even k"] To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts. [/HIDE] ---------- Post added 05-30-2012 at 12:53 AM ---------- Oh and forget my odd number series hypothesis for odd k's. I have just found that it is not true. Hypothesis discarded.

Okay, I actually think that I see what you were referring to. I think that it could work.

[HIDE="Commentary"]
The relationship you are referring to is well-known: the sum of the first n consecutive odd numbers is n^2. More formally,

1 + 3 + 5 + ... + (2n - 1) = n^2

To prove this, you can reduce it to summing 1 + 2 + 3 + ... + n. It might be a nice exercise to try.

Let S[n] = Sum[i^2, {i, 1, n}]. From the above, we know that i^2 = 1 + 3 + 5 + ... + (2i - 1) = Sum[(2j - 1), {j, 1, i}]. Therefore,

S[n] = Sum[ Sum[(2j - 1), {j, 1, i}], {i, 1, n} ]

That is, we have written S[n] in terms of a double sum. Now we can try to change the order of integration to try to get something we can compute. (It follows the same scheme as changing the order of a double integral, if you've done some multivariable calculus.) We have

S[n] = Sum[ Sum[(2j - 1), {i, j, n}], {j, 1, n} ]

Now the interior sum does not depend on i at all, and there are (n - j + 1) terms, so it is

Sum[(2j - 1), {i, j, n}] = (2j - 1)(n - j + 1)

and we have

S[n] = Sum[ (2j - 1)(n - j + 1) , {j, 1, n} ]

Expanding the product and collecting terms gives

S[n] = Sum[ -2j^2 + j(2n + 3) - n - 1 , {j, 1, n} ]

which can be separated:

S[n] = -2 Sum[ j^2, {j, 1, n} ] + (2n + 3) Sum[ j, {j, 1, n}] - (n + 1) Sum[ 1, {j, 1, n} ]
= -2 S[n] + (2n + 3) n (n + 1) / 2 - (n + 1)n

Now we wish to find S[n]. so we can add -2 S[n] to the other side:

3 S[n] = (2n + 3) n (n + 1) / 2 - (n + 1)n

Dividing through by three and rearranging gives our result!

S[n] = n (n + 1) (2n + 1) / 6

It's a nice calculus / combinatorial method.
[/HIDE]

[Latro]

Well, since roninpro has already zoomed in on the key idea, I'll show the step that gives my formula:

( Show Spoiler )

The key idea is that f(n,k) is a polynomial in n of degree k+1. This method does not rely on proving this in advance, but if this assumption is valid, then it is necessarily the unique interpolating degree k+1 interpolating polynomial through k+2 function values. It is slightly easier to choose to extend f's first argument to include 0, and then interpolate the points:
(0,0)
(1,1^k)
(2,1^k+2^k)
...
(k+1,f(k+1,k))
A very powerful technique for performing this interpolation is the Newton divided difference method. Our first two columns are basically already written up there, and as is this looks pretty intimidating. It's actually less intimidating once you compute the third column, which is just
1^k
2^k
...
(k+1)^k
So the first term of the polynomial is n. (Actually the first term was 0.) I'll show a couple iterations to illustrate the pattern. The fourth column is
(2^k-1)/2
(3^k-2^k)/2
...
((k+1)^k - k^k)/2
So the second term is (2^k-1)/2 n(n-1). Two more columns to really show the pattern:
(3^k-2*2^k+1)/6
(4^k-2*3^k+2^k)/6
...
((k+1)^k-2*k^k+(k-1)^k)/6
So the third term is (3^k-2*2^k+1)/6 n(n-1)(n-2). The next column:
(4^k-3*3^k+3*2^k-1)/24
...
((k+1)^k-3*k^k+3*(k-1)^k-(k-2)^k)/24
So the fourth term is (4^k-3*3^k+3*2^k-1)/24 n(n-1)(n-2)(n-3). Note the coefficients: 1, 1 1, 1 2 1, 1 3 3 1. If you pay careful attention to the way the combinations work out, it is clear that the coefficients here are binomial coefficients. It is also clear that the dividing factors and the terms involving n can be combined together into another binomial coefficient. This gives the explicit formula as a double sum:

f(n,k) = sum from i=1 to k+1 of (C(n,i) sum from j=1 to i of (-1)^(i+j) C(i-1,j-1) j^k)

where C(a,b) is a binomial coefficient. (To get the exponent on the -1, note i=1=j should give a positive result, from earlier.)

Notice that the inner sum is independent of n, which means that it can be explicitly computed for various k. For example, i=1,k=1 gives (-1)^2 C(0,0) 1^1 = 1, i=2,k=1 gives (-1)^(3) C(1,0) 1^1 + (-1)^4 C(1,1) 2^1 = 2-1=1, so f(n,1) = C(n,1) + C(n,2) = n + n(n-1)/2 = n(n+1)/2.

[Monte314]

I read roninpro and Latro's spoilers... great stuff! I wasn't going in that direction at all.

[HIDE="Spoiler option..."]If you don't like the Newton Interpolating Polynomial algorithm, you can use the more intuitive construction called the Lagrange Interpolating Polynomial algorithm. By uniqueness, it gives the same result, but is less opaque (in my opinion). [/HIDE]

[Latro]

	Originally Posted by Monte314 To view links or images in this forum your post count must be 2 or greater. You currently have 0 posts.
	I read roninpro and Latro's spoilers... great stuff! I wasn't going in that direction at all. [HIDE="Spoiler option..."]If you don't like the Newton Interpolating Polynomial algorithm, you can use the more intuitive construction called the Lagrange Interpolating Polynomial algorithm. By uniqueness, it gives the same result, but is less opaque (in my opinion). [/HIDE]

( Show Spoiler )

The Lagrange method was mentioned a little earlier, and yes, it works too. The Newton algorithm is "denser" in the sense that more background is required for it to work, but at the same time it gives a "better" result--especially for numerics, but even for situations like these where there is insight to be had in the final form.

Incidentally, is the Newton algorithm actually equivalent to an LU factorization of the Vandermonde matrix with respect to the special basis used by the Newton algorithm? The structure of the algorithm feels somewhat similar to the forward-backward substitution that is done after an LU factorization is computed.

A bonus question: derive a formula or algorithm for computing f(n,k) which represents it as

( Show Spoiler )

a sum of powers of n

. The "canonical" solution I mentioned earlier (which is significantly different from any of the solutions presented so far, but is closest to roninpro's initial approach, with the final formula being superficially similar to my final result) has this form.