# How to deduce a generator formula for a polynomial sequence?

Consider a polynomial sequence $\{p_n\}$ generated by some (simple) rule: $$\begin{array}{l} p_1(x)=x \\ p_2(x)=2 x-x^2 \\ p_3(x)= x^3-3 x^2+3 x \\ p_4(x)=-x^4+4 x^3-6 x^2+4 x \\ p_5(x)= x^5-5 x^4+10 x^3-10 x^2+5 x \\ p_6(x)= -x^6+6 x^5-15 x^4+20 x^3-15 x^2+6 x \\ p_7(x)= x^7-7 x^6+21 x^5-35 x^4+35 x^3-21 x^2+7 x \\ p_8(x)= -x^8+8 x^7-28 x^6+56 x^5-70 x^4+56 x^3-28 x^2+8 x \\ p_9(x)= x^9-9 x^8+36 x^7-84 x^6+126 x^5-126 x^4+84 x^3-36 x^2+9 x \\ p_{10}(x)= -x^{10}+10 x^9-45 x^8+120 x^7-210 x^6+252 x^5-210 x^4+120 x^3-45 x^2+10 x \\ \end{array}$$

Suppose we have only the above list of ten polynomials in expanded form. Is it possible to make Mathematica derive a formula that generates $p_n$ (I mean to get $p_n=1-(1-x)^n$ in this particular case)?

Note that something like  FullSimplify[Expand[1 - (1 - x)^5]]  does not give the desired result, so at least it would be nice to see how to get 1 - (1 - x)^5 from here...

FindSequenceFunction[{a, 2 a - a^2, 3 a - 3 a^2 + a^3, 4 a - 6 a^2 + 4 a^3 - a^4}, n]
(*
-> 1 - (1 - a)^n
*)

• It doesn't always work, of course; try FindSequenceFunction[JacobiP[Range, 1, 1, x], n]. – J. M. will be back soon Oct 2 '12 at 0:07
• @J.M. Of course. – Dr. belisarius Oct 2 '12 at 1:14
• I like using *that* sequence as an example, too. :D – J. M. will be back soon Oct 2 '12 at 1:17
• @J.M. Google used the "guess the next term" of that sequence at least once in a job interview. I always thought that was sadistic on their part. – Dr. belisarius Nov 5 '12 at 1:16

Assuming a simple rule (a recurrence relation) generating the sequence of polynomials, we can solve the problem with RSolve :

RSolve[ {a[x, n + 1] == a[x, n] (1 - x) + x, a[x, 1] == x}, a[x, n], n]

{{a[x, n] -> 1 - (1 - x)^n}}


Why have we assumed : a[x, n + 1] == a[x, n] (1 - x) + x ?

Because we can see a simple pattern (quotient, reminder) :

PolynomialQuotientRemainder[ #1, #2, x] & @@@
Partition[ Reverse @ { 3 x - 3 x^2 + x^3, 4 x - 6 x^2 + 4 x^3 - x^4,
5 x - 10 x^2 + 10 x^3 - 5 x^4 + x^5,
6 x - 15 x^2 + 20 x^3 - 15 x^4 + 6 x^5 - x^6},  2, 1]

{{1 - x, x}, {1 - x, x}, {1 - x, x}}