Programming mathemathics: how to expand a function

Lets say that I have a math function that is defined recursively. Like so:

T(1)(x) = 1
T(n)(x) = 2x*T(n-1)(x)-1

So:

T(1)(x) = 1
T(2)(x) = 2x*1-1 = 2x-1
T(3)(x) = 2x*(2x-1)-1 = 4x^2 - 2x - 1
/* and so on... */

Basically, I know how to write a program that will count T(15)(x) if the x is given. Thats not a problem. What I wonder, however is - how to write a program that will give me a polynomial for like T(10)(x) (one looking something like: 16x^4 + 3x^3 .开发者_如何学编程..).

In the nutshell: How can I recursively count the math expression, but using x as a variable (not set).

Any help would be greatly appreciated,

Paul

---

Based upon the comments, I believe that there are four options, in order of complexity.

First, you could just implement an explicit formula for the given polynomial that you are looking for, if it exist. In the case of the Chebyshev polynomials, an explicit formula (3^rd sum from the top) fitting your needs does exist.

If, however, you are looking for something more general, i.e. more than one type of polynomial, you could create an explicit list of the polynomials up to some absurd order and do a string replace using the user supplied variable name. In most systems, this won't take up a lot of memory.

Thirdly, if you wish to remain general and still recursively produce the polynomials, you could tap into a computer algebra system, like Mathematica. For instance, you can access Mathematica through MathLink, or use an instance of webMathematica, or even scrape the output from WolframAlpha. Although, I think you'd run into copyright issues with the last one.

Lastly, the most complex and most general would be to create an abstract syntax tree. If you can use c++, I'd look at boost.proto which essentially does this for you. But, if you create it yourself, you'd have three types of binary ops, add, multiply, and power and two types of leaf nodes, coefficient and variable. Now, to massage the tree into a form where you can use it you have to move through the tree and apply transformation rules: replace a subtree and interchange parent and child. Replace would alter the tree by applying standard math rules, such as 2 + 2 becomes 4 and x * x becomes x². But, the real work would be in interchanging the parent and child nodes, as this would be used to apply the distributive law (mult -> add becoming add -> mult) and providing opportunities to use replace.

The first two options are by far the easiest, and I'd go with the first if it is available. That said, I'd find implementing either the MathLink interface or the syntax tree much more interesting to do.

Edit: to clarify what I mean by interchanging a parent with its child, consider the case of n = 2.

which effects 4 nodes: "Plus", both "Times", and the coefficient 1. But, it is easy to see that this will reduce the overall number of nodes by eliminating the second "Times."

---

I think your Mathematica tag may be wrong, but anyway. Mathematica has an embedded function RSolve to cope with this:

   RSolve[{a[n] == 2  x a[n - 1] - 1, a[1] == 1}, a[n], n]  

The result is:

   a[n] = (x + 2^n (-1 + x) x^n)/(x (-1 + 2 x))    

As expected

   a[3] = -1 - 2 x + 4 x^2

HTH