# Factor polynomial of degree n+3

I'm considering a polynom poly[n,v] in v

poly[n_ , v_] := 5 (-1)^n + 2 v - 10 (-1)^n v - v^2 +5 (-1)^n v^2 + (-1 + 2 v)^(2 + n) (-5 + 4 v) +2 n (-1 + v) ((-1)^n (-1 + v) + (-1 + 2 v)^(2 + n))


for positive integers n.

checking

Apply[PolynomialGCD,   Table[poly[n, v] // Simplify, {n, 0, 10}]  ]
(* 16 (-1 + v)^2 v *)


shows, that the list of polynomials seem to possess a common factor v(1-v)^2

but unfortunately

Simplify[ Factor[poly[n, v]], {Element[n, Integers], n > 0}]


doesn't succeed.

Is there a tricky way to factor out v(1-v)^2 for arbitrary integer n? Thanks!

• Not quite what you are looking for: Series[poly[n, v] / v (v - 1)^2) , {v, 0, 2}] nicely gives a polynomial in v without negative exponents, so for any n the polynomial has this factor, and we have the first three coefficients after division. Aug 24, 2018 at 11:23
• Ok your observation is true for series-expansion around v=v0(arbitrary!) . Thanks! Aug 24, 2018 at 12:11
• Expanding on the comment by @FredSimons, if poly[n, v] is divisible by (v (v - 1)^2), then poly[n, v] / v (v - 1)^2) must be a polynomial of order n in v. This is true only if Simplify[SeriesCoefficient[poly[n, v]/(v (v - 1)^2), {v, 0, n + 1}], n ∈ Integers && n > 0] is zero, and it is Aug 25, 2018 at 20:13
• @ bbgodfrey That's true, but the question remains: How to evaluate the polynom(!) poly[n, v] / (v (v - 1)^2))? Thanks. Aug 25, 2018 at 20:17

There may not be an "easy" way to factor (v (1 - v)^2) from poly[n, v], leaving an n-th order polynomial. Here is a not-so-easy approach. Begin by simplifying the form of poly, representing (-1 + 2 v)^(2 + n) by t.

eq1 = Collect[poly[n, v] /. (-1 + 2 v)^(2 + n) -> t, v, Simplify]
(* (5 + 2 n) ((-1)^n - t) + (2 - 10 (-1)^n - 4 (-1)^n n + 4 t + 2 n t) v
+ (-1 + 5 (-1)^n + 2 (-1)^n n) v^2 *)


Now, t can be expanded by the Binomial Theorem

Hold[Sum[Binomial[n + 2, k] (-1)^(n + 2 - k) (2 v)^k, {k, 0, n + 2}]];


which can be rewritten as

2 v Hold[Sum[Binomial[n + 2, k] (-1)^(n + 2 - k) (2 v)^(k - 1), {k, 1, n + 2}]]
+ Sum[Binomial[n + 2, k] (-1)^(n + 2 - k) (2 v)^k, {k, 0, 0}];


which, when inserted into eq1, yields

eq2 = Collect[eq1 /. ((-1)^n - t) -> ((-1)^(n + 2) - %), {v, t}, Simplify]
(* (-1 + 5*(-1)^n + 2*(-1)^n*n)*v^2 + v*(2 - 10*(-1)^n - 4*(-1)^n*n + 2*(2 + n)*t -
2*(5 + 2*n)*Hold[Sum[Binomial[n + 2, k]*(-1)^(n + 2 - k)*(2*v)^(k - 1),
{k, 1, n + 2}]]) *)


thereby factoring out v. Next, divide out that factor of v and replace v elsewhere by x+1.

eq3 = Collect[Cancel[eq2/v] /. v -> x + 1, {x, t}, Simplify]
(* 1 - 5*(-1)^n - 2*(-1)^n*n + 2*(2 + n)*t + (-1 + 5*(-1)^n + 2*(-1)^n*n)*x
- 2*(5 + 2*n)*Hold[Sum[Binomial[n + 2, k]*(-1)^(n + 2 - k)*(2*(1 + x))^(k - 1),
{k, 1, n + 2}]] *)


Again, expand t by the Binomial Theorem, this time in terms of x.

Hold[Sum[Binomial[n + 2, k] (2 x)^k, {k, 0, n + 2}]];


which can be rewritten as

(2 x)^2 Hold[Sum[Binomial[n + 2, k] (2 x)^(k - 2), {k, 2, n + 2}]] +
Sum[Binomial[n + 2, k] (2 x)^k, {k, 0, 1}]
(* 1 + 2*(2 + n)*x +
4*x^2*Hold[Sum[Binomial[n + 2, k]*(2*x)^(k - 2), {k, 2, n + 2}]] *)


which, when inserted into eq3, yields

eq7 = Collect[eq3 /. t -> %, x, Simplify]
(* (5 + 2*n)*(3 + (-1)^n + 2*n)*x + 8*(2 + n)*x^2*
Hold[Sum[Binomial[n + 2, k]*(2*x)^(k - 2), {k, 2, n + 2}]] -
(5 + 2*n)*(-1 + (-1)^n + 2*Hold[Sum[Binomial[n + 2, k]*(-1)^(n + 2 - k)*
(2*(1 + x))^(k - 1), {k, 1, n + 2}]]) *)


The second Sum is in powers of 1 + x, and we need it in powers of x. Once again, the Binomial Theorem facilitates this transformation, replacing (1 + x))^(k - 1) by

Hold[Sum[Binomial[k - 1, kk] x^kk, {kk, 0, k - 1}]];


which allows the second Sum in eq7 to be rewritten as

eq4 = 2 Hold[Sum[Binomial[n + 2, k] (-1)^(n + 2 - k) 2^(k - 1)
Binomial[k - 1, kk] x^kk, {k, 1, n + 2}, {kk, 0, k - 1}]];


Interchanging the order of the two indices, k and kk, then gives

eq5 = 2 Hold[Sum[Binomial[n + 2, k] Binomial[k - 1, kk] (-1)^(n + 2 - k)
2^(k - 1) x^kk, {kk, 0, n + 1}, {k, kk + 1, n + 2}]];


Because this interchange tends to be error-prone, it is prudent to verify that the two expressions are the same (here for n == 5).

Simplify[ReleaseHold[eq4 == eq5] /. n -> 5]
(* True *)


Next, explicitly perform the inner sum.

Sum[Binomial[n + 2, k] Binomial[k - 1, kk] (-1)^(n + 2 - k)
2^(k - 1) x^kk, {k, kk + 1, n + 2}]
(* (-1)^(1 - kk + n) 2^kk x^kk Binomial[2 + n, 1 + kk]
Hypergeometric2F1[1 + kk, -1 + kk - n, 2 + kk, 2] *)


and insert the result into the outer Sum.

eq6 = 2 Hold[Sum[(-1)^(1 - kk + n) (2 x)^kk Binomial[2 + n, 1 + kk]
Hypergeometric2F1[1 + kk, -1 + kk - n, 2 + kk, 2], {kk, 0, n + 1}]];
ReleaseHold[eq5 == eq6]
(* True *)


eq6 can be rewritten as

2 (2 x)^2 Hold[Sum[(-1)^(1 - kk + n) (2 x)^(kk - 2) Binomial[2 + n, 1 + kk]
Hypergeometric2F1[1 + kk, -1 + kk - n, 2 + kk, 2], {kk, 3, n + 1}]] +
2 Sum[(-1)^(1 - kk + n) (2 x)^kk Binomial[2 + n, 1 + kk]
Hypergeometric2F1[1 + kk, -1 + kk - n, 2 + kk, 2], {kk, 0, 2}];


and inserted into eq7.

eq7 /. 2 Hold[_] -> %
eq8 = Collect[%/x^2, x, Simplify[#, n ∈ Integers] &] /. x -> v - 1
(* 8*(2 + n)*Hold[Sum[Binomial[n + 2, k]*(2*(-1 + v))^(k - 2), {k, 2, n + 2}]] -
(5 + 2*n)*(1 + (-1)^(1 + n) + 4*n + 2*n^2 +
8*Hold[Sum[(-1)^(1 - kk + n)*(2*(-1 + v))^(kk - 2)*Binomial[2 + n, 1 + kk]*
Hypergeometric2F1[1 + kk, -1 + kk - n, 2 + kk, 2], {kk, 3, n + 1}]]) *)


Note that x^2 == (v - 1)^2 has been factored from eq8, and eq8 is the desired remainder. As verification,

Simplify[ReleaseHold[eq8 /. n -> 15] == poly[15, v]/(v (1 - v)^2)]
(* True *)


Incidentally, Mathematica diligently performs the general Sums in eq8, if Hold is removed, but the resulting expression is not a step in the right direction.

• You've done a tough job, thank you. Likely I need an undefined amount of time to understand(!) it. Aug 26, 2018 at 11:07

I think the clever analysis of @FredSimons needs to be made into an answer. @bbgodfrey's virtuoso algebra is impressive. However, since neither seems to yield a useful expression for general n, here's a simpler, (you might say stupider) solution:

rat3[n_Integer, v_Symbol] := Cancel[poly[n, v]/(v (1 - v)^2)]
Table[rat3[n, v], {n, 0, 5}] // TableForm

16
16 (-2+3 v)
16 (4-9 v+8 v^2)
16 (-6+21 v-32 v^2+20 v^3)
16 (9-39 v+88 v^2-100 v^3+48 v^4)
32 (-6+33 v-96 v^2+160 v^3-144 v^4+56 v^5)


In fact, the solution is simple. Form a differential equation for the reminder and solve it:

f = x (1 - x)^2 g[x];
lhs=D[f, {x, 3}]
rhs=D[poly[k, x], {x, 3}]
DSolve[lhs==rhs, g, x]


General solution for the reminder is given by

$\frac{c_1}{(x-1)^2 x}+\frac{c_2}{(x-1)^2}+\frac{c_3 x}{2 (x-1)^2}+\frac{(2 k x-2 k+4 x-5) (2 x-1)^{k+2}}{(x-1)^2 x}$

It is a simple matter to determine the constants. For instance, using SolveAlways for $k=1$ yields

SolveAlways[(2 (7 + C[1] + x (-48 + 8 x (15 + 2 x (-8 + 3 x)) + C[2]))
+ x^2 C[3])/(2 (-1 + x)^2 x) == 16 (3 x - 2), x]


$c_1\to -7,c_2\to 16,c_3\to -16$.

Concerns were raised that in order to determine the coefficients we need to know the solution beforehand. However, the are nod actually needed. The polynomials can be computed setting $c_1=c_2=c_3=0$

v[k_, x_] := (-1 + 2 x)^(2 + k) (-5 - 2 k + 4 x + 2 k x)
PolynomialQuotient[v[10, x], (1 - x)^2 x , x]

• It appears that you need to know the remainder in advance in order to obtain the coefficients, and the coefficients are different for each value of k. Aug 27, 2018 at 4:34
• @bbgodfrey The point is that you do not actually need to know the coefficients :) See my edit ! Aug 27, 2018 at 22:01
• PolynomialQuotient discards any remainder. To have no remainder, use PolynomialQuotient[poly[10, v], (1 - v)^2 v, v], which would be equivalent to John Doty's Cancel[poly[10, v]/(v (1 - v)^2)] . Aug 27, 2018 at 22:32
• @bbgodfrey Yes, I know what PolynomialQuotient is doing. Yes, it looks like going in circles, however, there are some differences: the form of the denominator is much simpler now showing also what terms are relevant. Aug 28, 2018 at 4:21