12
$\begingroup$

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...

$\endgroup$
10
$\begingroup$
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
*)
$\endgroup$
  • $\begingroup$ It doesn't always work, of course; try FindSequenceFunction[JacobiP[Range[10], 1, 1, x], n]. $\endgroup$ – J. M. will be back soon Oct 2 '12 at 0:07
  • $\begingroup$ @J.M. Of course. $\endgroup$ – Dr. belisarius Oct 2 '12 at 1:14
  • $\begingroup$ I like using *that* sequence as an example, too. :D $\endgroup$ – J. M. will be back soon Oct 2 '12 at 1:17
  • 1
    $\begingroup$ @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. $\endgroup$ – Dr. belisarius Nov 5 '12 at 1:16
8
$\begingroup$

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}}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.