Can program be used to simplify algebraic expressions?

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 开发者_C百科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

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.

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.

EDIT, due to your recent clarification of the post.

You won't get away with a hand made solution, unless you have a whole team of PhDs and several years to spend. The best advice I can give you is to buy a Mathematica (or other) license and interface it with your program.

If you are a Lisp programmer, using Maxima is another potential (free this one) solution.

If you want background on the state of art in summation algorithms, this paper is a good start.

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

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

This kind of problems occupy a lot of people to figure out how to do it on paper.

Let us take k = 2. Then X_1 + X_2 = n gives X_2 = n - X_1.

So the expectation to be computed is E = X_1^2 + (n - X_1)^2 = 2 X_1^2 -2n X_1 + n^2.

This reads

E = sum(p_k * (2 * k^2 - 2 * n * k + n^2), k = 0..infinity)

where p_k = Prob(X_1 = k). This kind of sums, depending on p_k, is generally very difficult to compute. I'd say that the problem is even more difficult than computing integrals in closed form (for which no software fully implement the available -- but undecidable -- Risch algorithm).

To convince yourself, take eg. p_k = 1 / (log(k) * k^4).

Finding a formula (or a formula generator) for it is at the very least a very difficult research problem.