Sum of Powers

In the sum of powers problem, we are looking for the sum of the p^th power of the first n integers. In this post, we consider the problem of determining a polynomial expression in n for a given power. The best known case is for p = 1, namely,

More generally, we should like a formula for a polynomial f_p such that

We will begin by defining a function and proceed to prove that it satisfies the above equality. We define:

Proposition 1. For all real numbers \(n\) and natural numbers \(p\),

Proof:  First we observe that (n + 1) – n = 1 = (n + 1)⁰, so that we have our induction base set. Suppose that for any real number n > 0 and a given natural number p we have,

Now, given any real number n > 0,

which completes the argument.■

Proposition 2. For all natural numbers \(n\) and \(p\)

$$f_p(n) = \sum_{i=1}^n{i^p}$$

Proof: First we see from the definition both that \(f_0(1) = 1\) and, for any \(p > 1\)

$$f_{p}(1) = p \Big(\int_0^1 f_{p-1}(x) \mathrm{d}x - 1 \int_0^1 f_{p-1}(x) \mathrm{d}x\Big) + 1 = 1,$$

which establishes \(1 \in S\). Suppose that \(n \in S\). Then

$$f_p(n) = \sum_{i=1}^n{i^p},$$

and from proposition 1

$$f_p(n+1) - f_p(n) = (n + 1)^p$$

which rearranges to

$$f_p(n+1) = f_p(n) + (n+1)^p$$

$$= \sum_{i=1}^n{i^p} + (n+1)^p  = \sum_{i=1}^{n+1}{i^p}$$

■

The formula we have given for f_p allows us to calculate the first p sum of powers polynomials in time O(p²) which is a big improvement when compared to solving a system of linear equations to find the largest of them, which would require time O(p³) (to find all of them using a system of linear equations requires O(p⁴)).

The following Maxima program and its output, gives a demonstration of how to implement the above formula:
f[0]: n$ for p: 1 thru 100 do ( f[p]: integrate(expand(p*f[p-1]),n), C: 1 - ev(subst([n=1],f[p])), f[p]: f[p] + n*C )$ [f[0],f[1],f[2],f[3],f[4],f[5]];

[n,n^2/2+n/2,n^3/3+n^2/2+n/6,n^4/4+n^3/2+n^2/4,n^5/5+n^4/2+n^3/3-n/30,n^6/6+n^5/2+(5*n^4)/12-n^2/12]

The Un-Pyramid

In previous posts I've discussed truncated pyramids and irregular triangular prisms, but I hadn't at that time thought to consider a "really irregular triangular prism" before.  I was searching on the general notions of these topics on the internet to see what people were thinking about with respect to them and found someone had something different in mind:  A 5 sided solid with a non-constant triangular cross-section and no faces (guaranteed) parallel with each other.

The first thing to note about this shape is the characterization of the faces.  The two "ends" are triangular faces. There are three quadrilateral faces which form the boundaries of the non-constant triangular cross-section. The three edges shared by the quadrilateral faces are not parallel with each other and the quadrilaterals could be completely irregular. Here is a quick video of a Sketchup model of just such a shape:


The Un-Pyramid from Darren Irvine on Vimeo.

Since the consecutive pairs of "side" edges are part of a quadrilateral (they are proper "faces"—no twists), they are certainly coplanar. In a previous post, I demonstrated that two parallel faces with edges joining corresponding vertices with consecutive edges being coplanar, the parallel faces are necessarily similar. I also demonstrated (Proposition 4) that the projected side edges intersect at a common point, which we may call the apex.

The un-pyramid does not have the two parallel faces that formed the starting point in that post. However, it does have the consecutive coplanar edges. And although we have not been given a "top" face parallel with the bottom, we can certainly make one. We establish a cutting plane through the closest vertex (or vertices—there could be two at the same level) of the "top" face which is parallel with the larger "bottom" face. (We can turn the un-pyramid around to make the names fit if it comes to us upside down or sideways.) Now we can be sure that the side edges can be projected to a common apex as per 3D Analogue to the Trapezoid (part 3).

Fig. 1.  A really irregular triangular pyramid? Hmm...

Calculating the volume of this shape requires a bit of calculation just to figure out how to break it up into pieces. If you want to program a solution to this problem, you are probably going to take in A₁, B₁, C₁, A₂, B₂, and C₂ as the parameters. To verify you have valid data establish that:

• A₁A₂ is coplanar with B₁B₂
• B₁B₂ is coplanar with C₁C₂
• C₁C₂ is coplanar with A₁A₂
• Also, make sure these same edges don't intersect each other (meaning the lines projected through them should intersect outside of the boundaries of the line segments).

You also need to determine whether the apex is closer to A₁B₁C₁ or A₂B₂C₂. Then reorder or relabel the end faces as necessary. The face further away is the base (say ₁). Now determine which of the top vertices is closest to the base and establish a cutting plane through it, parallel to the base.

(Hint: It will be convenient to reorder or relabel your points so that A₂ is the closest point, B₂ next, and C₂ furthest; this avoids polluting your code with cases. Don't forget to reorder the points in the base. You may have a job making the relabeling of previous calculation results work properly. Making clear code that does minimal recalculations is probably the most challenging aspect of this problem if treated as a programming challenge.)

Now we can calculate the volume as a sum of two volumes:

1. Frustum of a (slanted) pyramid with base A₁B₁C₁ and top A₂BC.
• For the overall formula, see 3D Analogue to the Trapezoid (part 2)
• To find the areas of the top and bottom, use the cross-product method (see Area of Triangle Given Coordinates)
• To find the height, find the component of vector (A₂ – A₁) perpendicular to the base (also used in Volume of a Tetrahedron)
2. Slanted pyramid with base BB₂C₂C and apex A₂
• Find the area of the base
• watch out for B = B₂ and C = C₂ which changes the shape of the base
• If both are true, then you've dodged the bullet—there's no volume to worry about.
• If B = B₂, then either it is at the same level as C₂ or the same level as A₂. But in either case, you have a triangular base.
• Very possibly neither of these will be true. Break the quadrilateral up into two triangles using the diagonal of your choice.
• Find the height of the pyramid using the component method as for finding the height of the first volume.

But, what should we call it?

1. triangular un-pyramid
2. really irregular triangular prism
3. skew-cut slanted triangular pyramid
• alternatively, skew-cut slanted pyramid with triangular base

I guess I like 1) for the advertizing, 2) for the baffling rhetorical effect, and 3) for half a hope of conveying what the shape really is.

Find the Intersection of a Plane with a Line

We can represent a plane with four numbers, the coefficients of the general equation of a plane, as ax + by + cz + d = 0.  For convenience, we can represent this also as

where n = (a, b, c) and r = (x, y, z) is a point on the plane.

We take a line through two points, A and B, in vector form as

        L(t) = A + (B–A)t

We want to find the intersection of the line with the plane.  That is, we need f, such that

Then,

And so

The desired point is L(f), since it on the plane and on the line.

Notice that the calculation of f requires only the evaluation of the general equation of the plane using A and B as the points. The results will not be zero unless A and B are on the plane, in which case we would already have the result. If the line is parallel with the plane, then the denominator will be zero giving an indeterminate result. This fits with the geometric interpretation of the plane evaluation. The point of the last step in our derivation is that it simplifies the coding of the problem somewhat by reducing it to two plane evaluations. (If you observe carefully, you will see it makes the difference not of two additions but only of one.)

Evaluating the equation of a plane using a point not on the plane gives a result which is proportional to the distance between the planes. If the normal vector (n = (a, b, c)), has a magnitude of 1, then it yields the distance. However, in the formula we have derived, we have not depended on the equation of the plane being normalized. The constant of proportionality in the numerator cancels with itself in the denominator (I mean "behind the scenes" or if you derived it using a different approach) to produce the simple result for f above.

The idea for this solution came from initially viewing it as a linear interpolation problem, which, of course, it is. Similar triangles also are an acceptable approach the problem, though it may be more difficult to deal with the signs. The above derivation deals with sign transparently.