Can program be used to simplify algebraic expressions?

Question

We know 1+2+...+n is equal to n(n+1)/2.

But can we get the same result programatically if we don't know it in advance?

About why I have such a question.

Think of a more complex situation:

X1+X2+...+Xk=n, where Xi is integer and >= 0.

What's the Expectation of X1^2+...Xk^2?

The result is not obvious just by a glance, and we'll want to feed it to a program to reduce the algebra once we've worked out the (verbose)mathematical representation of Expectation of X1^2+...Xk^2

Answer 1

Perhaps you're thinking of a Computer algebra system (CAS)? WolframAlpha is a free online one that uses Mathematica (a very powerful CAS system) on it's backend. Here you can see it compute/simplify your expression: WolframAlpha.

Your example is just the sum of squares which has a pretty simple explicit formula: n(n+1)(2n+1)/6. More generally, you can use Faulhaber's formula to calculate Sum of n^p.

Answer 2

Okay, first some suggestions about the math part of the question and then some about the software development.

There's an e-book "A=B" by Marko Petkov·sek, Herbert S. Wilf and Doron Zeilberger which deals with solving (or showing there is no solution of) summation problems even more difficult than just polynomials. A review of the book by Ian Wanless is worth a quick reading. The e-book is freely downloadable, but bound copies can be purchased, e.g. from Amazon.

A 2004 Trans. of AMS paper Closed Form Summation of C-finite Sequences by Greene and Wilf is also available online.

In general you will need some basic CAS software to implement these algorithms, and it sounds like the goal is to develop such software yourself. I would recommend studying some of the open source CAS (computer algebra software) packages like Maxima or Axiom to get a feel for the scope of what is involved. Of course it's likely that a narrowly targeted application can do with only a fraction of what these fairly mature and high-end packages implement, but I don't feel that I can point you down a more directed path given the current phrasing of the question.

If "Expectation" of expressions is included in the scope of your project, there are a number of complications piled on top of mere algebraically manipulation. One certainly needs to be able to specify probability density functions to support expected values, and presumably some integration software (though potentially limiting the choice of parameterized distributions could lead to a simplified problem of looking up moments of those distributions). I do think this is a particularly nice application to jump into, as seemingly simple expressions (sums, max/min) of random variables can lead to nightmarish consideration of cases, well-suited to the patience of a computer.