Skip to main content
deleted 25 characters in body
Source Link
Yaakov Baruch
  • 5.1k
  • 2
  • 31
  • 43

Here is a completely elementary proof, inspired by Pasten's comments.

Let $P(n)=an^2+bn+c$.

Take $n=a^5x^4+2a^3(ab+2a+1)x^3+a(2a^3c+a^2b^2+6a^2b+3ab+6a^2+5a+1)x^2+(ab+2a+1)(2a^2c+2ab+b+2a+1)x+a^3c^2+2a^2bc+abc+2a^2c+ac+c+ab^2+b^2+2ab+2b+a+1$

Then

$P(n)=P_1(x)P_2(x)P_3(x)$

where

$$\begin{align*} P_1(x)=&a^2x^2+abx+2ax+ac+b+1\\ \\ P_2(x)=&a^4x^2+a^3bx+2a^3x+2a^2x+a^3c+a^2b+ab+a^2+2a+1\\ \\ P_3(x)=&a^5x^4\\ &+2a^4bx^3+4a^4x^3+2a^3x^3\\ &+2a^4cx^2+a^3b^2x^2+6a^3bx^2+3a^2bx^2+6a^3x^2+4a^2x^2+ax^2\\ &+2a^3bcx+4a^3cx+2a^2cx+2a^2b^2x+ab^2x+6a^2bx+4abx+bx+4a^2x+2ax\\ &+a^3c^2+2a^2bc+abc+2a^2c+c+ab^2+b^2+2ab+b+a\\ =&n-(a^2x^2+abx+2ax+x+ac+b+1) \end{align*}$$

Clearly for $x$ large enough $P_1(x), P_2(x), P_3(x)$ are distinct and less than $n$ in absolute value. Since the product of 3 distinct numbers $\le n$ divides $n!$, the result follows.$\qquad\qquad\blacksquare$

The idea behind this proof is that always $P(x)\;|\;P(P(x)+x)$ and applying this idea twice allows to factor $P(\text{some polynomial})$ into 3 factors all small enough.

Here is the relevant Maxima code:

(%i7%i1)   a*x*x+b*x+c;
(%o7%o1)   ...
(%i89%i2)   a*x^2+(b+1)*x+c;
(%o89%o2)   ...
(%i98%i3)   subst(a^2*x^2+a*b*x+2*a*x+x+a*c+b+1, x, (%o89%o2));
(%o98%o3)   ...
(%i99%i4)   expand((%o98%o3));
(%o99%o4)   ...
(%i101%i5)   subst(%o99%o4, x, (%o7%o1));
(%o101%o5)   ...
(%i102%i6)   expand((%o101%o5));
(%o102%o6)   ...
(%i103%i7)   factor((%o102%o6));
(%o103%o7)   (a^2*x^2+a*b*x+2*a*x+a*c+b+1)*(a^4*x^2+a^3*b*x+2*a^3*x+2*a^2*x+a^3*c+a^2*b+a*b+a^2+2*a+1)*(a^5*x^4+2*a^4*b*x^3+4*a^4*x^3+2*a^3*x^3+2*a^4*c*x^2+a^3*b^2*x^2+6*a^3*b*x^2+3*a^2*b*x^2+6*a^3*x^2+4*a^2*x^2+a*x^2+2*a^3*b*c*x+4*a^3*c*x+2*a^2*c*x+2*a^2*b^2*x+a*b^2*x+6*a^2*b*x+4*a*b*x+b*x+4*a^2*x
+2*a*x+a^3*c^2+2*a^2*b*c+a*b*c+2*a^2*c+c+a*b^2+b^2+2*a*b+b+a)

Here is a completely elementary proof, inspired by Pasten's comments.

Let $P(n)=an^2+bn+c$.

Take $n=a^5x^4+2a^3(ab+2a+1)x^3+a(2a^3c+a^2b^2+6a^2b+3ab+6a^2+5a+1)x^2+(ab+2a+1)(2a^2c+2ab+b+2a+1)x+a^3c^2+2a^2bc+abc+2a^2c+ac+c+ab^2+b^2+2ab+2b+a+1$

Then

$P(n)=P_1(x)P_2(x)P_3(x)$

where

$$\begin{align*} P_1(x)=&a^2x^2+abx+2ax+ac+b+1\\ \\ P_2(x)=&a^4x^2+a^3bx+2a^3x+2a^2x+a^3c+a^2b+ab+a^2+2a+1\\ \\ P_3(x)=&a^5x^4\\ &+2a^4bx^3+4a^4x^3+2a^3x^3\\ &+2a^4cx^2+a^3b^2x^2+6a^3bx^2+3a^2bx^2+6a^3x^2+4a^2x^2+ax^2\\ &+2a^3bcx+4a^3cx+2a^2cx+2a^2b^2x+ab^2x+6a^2bx+4abx+bx+4a^2x+2ax\\ &+a^3c^2+2a^2bc+abc+2a^2c+c+ab^2+b^2+2ab+b+a\\ =&n-(a^2x^2+abx+2ax+x+ac+b+1) \end{align*}$$

Clearly for $x$ large enough $P_1(x), P_2(x), P_3(x)$ are distinct and less than $n$ in absolute value. Since the product of 3 distinct numbers $\le n$ divides $n!$, the result follows.$\qquad\qquad\blacksquare$

The idea behind this proof is that always $P(x)\;|\;P(P(x)+x)$ and applying this idea twice allows to factor $P(\text{some polynomial})$ into 3 factors all small enough.

Here is the relevant Maxima code:

(%i7)   a*x*x+b*x+c;
(%o7)   ...
(%i89)  a*x^2+(b+1)*x+c;
(%o89)  ...
(%i98)  subst(a^2*x^2+a*b*x+2*a*x+x+a*c+b+1, x, (%o89));
(%o98)  ...
(%i99)  expand((%o98));
(%o99)  ...
(%i101) subst(%o99, x, (%o7));
(%o101) ...
(%i102) expand((%o101));
(%o102) ...
(%i103) factor((%o102));
(%o103) (a^2*x^2+a*b*x+2*a*x+a*c+b+1)*(a^4*x^2+a^3*b*x+2*a^3*x+2*a^2*x+a^3*c+a^2*b+a*b+a^2+2*a+1)*(a^5*x^4+2*a^4*b*x^3+4*a^4*x^3+2*a^3*x^3+2*a^4*c*x^2+a^3*b^2*x^2+6*a^3*b*x^2+3*a^2*b*x^2+6*a^3*x^2+4*a^2*x^2+a*x^2+2*a^3*b*c*x+4*a^3*c*x+2*a^2*c*x+2*a^2*b^2*x+a*b^2*x+6*a^2*b*x+4*a*b*x+b*x+4*a^2*x
+2*a*x+a^3*c^2+2*a^2*b*c+a*b*c+2*a^2*c+c+a*b^2+b^2+2*a*b+b+a)

Here is a completely elementary proof, inspired by Pasten's comments.

Let $P(n)=an^2+bn+c$.

Take $n=a^5x^4+2a^3(ab+2a+1)x^3+a(2a^3c+a^2b^2+6a^2b+3ab+6a^2+5a+1)x^2+(ab+2a+1)(2a^2c+2ab+b+2a+1)x+a^3c^2+2a^2bc+abc+2a^2c+ac+c+ab^2+b^2+2ab+2b+a+1$

Then

$P(n)=P_1(x)P_2(x)P_3(x)$

where

$$\begin{align*} P_1(x)=&a^2x^2+abx+2ax+ac+b+1\\ \\ P_2(x)=&a^4x^2+a^3bx+2a^3x+2a^2x+a^3c+a^2b+ab+a^2+2a+1\\ \\ P_3(x)=&a^5x^4\\ &+2a^4bx^3+4a^4x^3+2a^3x^3\\ &+2a^4cx^2+a^3b^2x^2+6a^3bx^2+3a^2bx^2+6a^3x^2+4a^2x^2+ax^2\\ &+2a^3bcx+4a^3cx+2a^2cx+2a^2b^2x+ab^2x+6a^2bx+4abx+bx+4a^2x+2ax\\ &+a^3c^2+2a^2bc+abc+2a^2c+c+ab^2+b^2+2ab+b+a\\ =&n-(a^2x^2+abx+2ax+x+ac+b+1) \end{align*}$$

Clearly for $x$ large enough $P_1(x), P_2(x), P_3(x)$ are distinct and less than $n$ in absolute value. Since the product of 3 distinct numbers $\le n$ divides $n!$, the result follows.$\qquad\qquad\blacksquare$

The idea behind this proof is that always $P(x)\;|\;P(P(x)+x)$ and applying this idea twice allows to factor $P(\text{some polynomial})$ into 3 factors all small enough.

Here is the relevant Maxima code:

(%i1)   a*x*x+b*x+c;
(%o1)   ...
(%i2)   a*x^2+(b+1)*x+c;
(%o2)   ...
(%i3)   subst(a^2*x^2+a*b*x+2*a*x+x+a*c+b+1, x, (%o2));
(%o3)   ...
(%i4)   expand((%o3));
(%o4)   ...
(%i5)   subst(%o4, x, (%o1));
(%o5)   ...
(%i6)   expand((%o5));
(%o6)   ...
(%i7)   factor((%o6));
(%o7)   (a^2*x^2+a*b*x+2*a*x+a*c+b+1)*(a^4*x^2+a^3*b*x+2*a^3*x+2*a^2*x+a^3*c+a^2*b+a*b+a^2+2*a+1)*(a^5*x^4+2*a^4*b*x^3+4*a^4*x^3+2*a^3*x^3+2*a^4*c*x^2+a^3*b^2*x^2+6*a^3*b*x^2+3*a^2*b*x^2+6*a^3*x^2+4*a^2*x^2+a*x^2+2*a^3*b*c*x+4*a^3*c*x+2*a^2*c*x+2*a^2*b^2*x+a*b^2*x+6*a^2*b*x+4*a*b*x+b*x+4*a^2*x
+2*a*x+a^3*c^2+2*a^2*b*c+a*b*c+2*a^2*c+c+a*b^2+b^2+2*a*b+b+a)
Source Link
Yaakov Baruch
  • 5.1k
  • 2
  • 31
  • 43

Here is a completely elementary proof, inspired by Pasten's comments.

Let $P(n)=an^2+bn+c$.

Take $n=a^5x^4+2a^3(ab+2a+1)x^3+a(2a^3c+a^2b^2+6a^2b+3ab+6a^2+5a+1)x^2+(ab+2a+1)(2a^2c+2ab+b+2a+1)x+a^3c^2+2a^2bc+abc+2a^2c+ac+c+ab^2+b^2+2ab+2b+a+1$

Then

$P(n)=P_1(x)P_2(x)P_3(x)$

where

$$\begin{align*} P_1(x)=&a^2x^2+abx+2ax+ac+b+1\\ \\ P_2(x)=&a^4x^2+a^3bx+2a^3x+2a^2x+a^3c+a^2b+ab+a^2+2a+1\\ \\ P_3(x)=&a^5x^4\\ &+2a^4bx^3+4a^4x^3+2a^3x^3\\ &+2a^4cx^2+a^3b^2x^2+6a^3bx^2+3a^2bx^2+6a^3x^2+4a^2x^2+ax^2\\ &+2a^3bcx+4a^3cx+2a^2cx+2a^2b^2x+ab^2x+6a^2bx+4abx+bx+4a^2x+2ax\\ &+a^3c^2+2a^2bc+abc+2a^2c+c+ab^2+b^2+2ab+b+a\\ =&n-(a^2x^2+abx+2ax+x+ac+b+1) \end{align*}$$

Clearly for $x$ large enough $P_1(x), P_2(x), P_3(x)$ are distinct and less than $n$ in absolute value. Since the product of 3 distinct numbers $\le n$ divides $n!$, the result follows.$\qquad\qquad\blacksquare$

The idea behind this proof is that always $P(x)\;|\;P(P(x)+x)$ and applying this idea twice allows to factor $P(\text{some polynomial})$ into 3 factors all small enough.

Here is the relevant Maxima code:

(%i7)   a*x*x+b*x+c;
(%o7)   ...
(%i89)  a*x^2+(b+1)*x+c;
(%o89)  ...
(%i98)  subst(a^2*x^2+a*b*x+2*a*x+x+a*c+b+1, x, (%o89));
(%o98)  ...
(%i99)  expand((%o98));
(%o99)  ...
(%i101) subst(%o99, x, (%o7));
(%o101) ...
(%i102) expand((%o101));
(%o102) ...
(%i103) factor((%o102));
(%o103) (a^2*x^2+a*b*x+2*a*x+a*c+b+1)*(a^4*x^2+a^3*b*x+2*a^3*x+2*a^2*x+a^3*c+a^2*b+a*b+a^2+2*a+1)*(a^5*x^4+2*a^4*b*x^3+4*a^4*x^3+2*a^3*x^3+2*a^4*c*x^2+a^3*b^2*x^2+6*a^3*b*x^2+3*a^2*b*x^2+6*a^3*x^2+4*a^2*x^2+a*x^2+2*a^3*b*c*x+4*a^3*c*x+2*a^2*c*x+2*a^2*b^2*x+a*b^2*x+6*a^2*b*x+4*a*b*x+b*x+4*a^2*x
+2*a*x+a^3*c^2+2*a^2*b*c+a*b*c+2*a^2*c+c+a*b^2+b^2+2*a*b+b+a)