Can a program be used to simplify algebraic expressions?

Question

We know that 1+2+...+n is n(n+1)/2 .

But can we get the same result programmatically if we do not know it in advance?

About why I have such a question.

Think of a more difficult situation:

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

What is Standby X1^2+...Xk^2 ?

The result is not obvious with just one glance, and we want to pass it on to the program for reducing algebra, as soon as we develop a mathematical representation of the expectation X1^2+...Xk^2

Answer 1

Perhaps you are thinking of a computer algebra system (CAS)? WolframAlpha is a free online interface that uses Mathematica (a very powerful CAS system). Here you can see how it calculates / simplifies your expression: WolframAlpha .

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

Answer 2

Well, first a few suggestions about the mathematical part of the question, and then about software development.

There is an e-book "A = B" by Marco Petkova · Sec, Herbert S. Wilf and Doron Zeilberger who deals with solving (or showing that solving summation problems is even more complicated than just polynomials. A review of Ian Vanles’s book is worth a quick read. E-book freely downloadable, but related copies can be purchased from Amazon.

A 2004 Trans. AMS articles Closed summation of C-terminal sequences Greene and Wilf is also available on the Internet.

In general, you will need basic CAS software to implement these algorithms, and it seems that the goal is to develop such software yourself. I would recommend exploring some of the open source CAS programs (computer algebra software), like Maxima or Axiom , to understand what the involvement is. Of course, it is likely that a narrow-priority application can use only part of what these fairly mature and high-performance packages implement, but I don’t feel like I can show you a more directional path, given the current wording of the question.

If the "Pending" expression is included in the scope of your project, there are a number of complications stacked on top of simple algebraic manipulations. Of course, it is necessary to be able to determine probability density functions to support the expected values, and, apparently, some integration software (although potentially limiting the choice of parameterized distributions can lead to a simplified problem of finding the moments of these distributions). I think this is a particularly nice transition application, since the seemingly simple expressions (sums, max / min) of random variables can lead to a nightmare of cases that are well suited for the patience of the computer.

Answer 3

EDIT , due to a recent clarification of this post.

You will not be able to deal with a manual solution if you do not have a whole group of candidates of sciences and several years. The best advice I can give you is to buy a Mathematica (or other) license and associate it with your program.

If you're a Lisp programmer, using Maxima is another potential (free) solution.

If you need a background in modern art in summation algorithms, this document is a good start.

---

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

What is Standby X1 ^ 2 + ... Xk ^ 2?

Such problems take a lot of people to figure out how to do this on paper.

Take k = 2. Then X_1 + X_2 = n gives X_2 = n - X_1.

So, the expected calculation is E = X_1^2 + (n - X_1)^2 = 2 X_1^2 -2n X_1 + n^2 .

It reads

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

where p_k = Prob(X_1 = k) . Such amounts, depending on p_k , are usually very difficult to calculate. I would say that the problem is even more complicated than computational integrals in a closed form (for which no software fully implements the Risch algorithm, but cannot be analyzed).

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

Finding a formula (or a formula generator) for her is at least a very complex research problem.