<s>[INST] How to know that $2n^3+9n^2+13n+6$ factors into $(n+1)(n+2)(2n+3)$? Apologies in advance, my math is very rusty.
I'm slowly working my way through Schaum's Outline of Discrete Math for some self-study, occasionally filling in large knowledge gaps in my grasp on algebra. In one of the supplementary questions I'm asked to prove (by induction) that:
$$
\sum^n_{i=1}i^2 = \frac{n(n+1)(2n+1)}{6}
$$
In the inductive step I add $(n+1)^2$ to either side and then try to work my way through, multiplying out the factors:
$$
\frac{n(n+1)(2n+1)}{6} + (n+1)^2 \\
= \frac{n(n+1)(2n+1)+6(n+1)^2}{6} \\
= \frac{(n^2+n)(2n+1)+6(n+1)^2}{6} \\
= \frac{2n^3+n^2+2n^2+n+6(n^2+2n+1)}{6} \\
= \frac{2n^3+n^2+2n^2+n+6n^2+12n+6}{6} \\
= \frac{2n^3+9n^2+13n+6}{6}
$$
I think everything up to this point is pretty trivial, but it's around this point that I get a bit lost. I know I need to factor the terms in the 3-degree polynomial in the numerator somehow, but I'm having a hard time with the actual mechanics given the lack of obvious common factors & the fact that 13 is prime.
I'm pretty sure the final result should look something like:
$$
\frac{(n+1)((n+1)+1)(2(n+1)+1)}{6} \\
= \frac{(n+1)(n+2)(2n+3)}{6}
$$
Multiplying the expected result out I can see the two statements are equal and I'm confident that
$$
\frac{2n^3+9n^2+13n+6}{6} = \frac{(n+1)(n+2)(2n+3)}{6}
$$
but I'm just not quite sure how to factor the polynomial myself to arrive at the final result.
Any hints on how to proceed from here, or what I need to be reading up on to get my head around this?
 [/INST] The Rational Root Theorem tells you that any rational root of the polynomial $2 n^3 + 9 n^2 + 13 n + 6$ has the form $\frac{p}{q}$ for integers $q \mid 2$, $p \mid 6$, leaving 12 possible rational roots. Since all of the coefficients are positive, all of the (real) roots are negative, leaving only 6 possible rational roots, $-6, -3, -2, -\frac{3}{2}, -1, -\frac{1}{2}$.
Substituting, for example, $-1$ (because it's fast to evaluate a polynomial at $-1$---just take the alternating sum of the coefficients) gives $-2 + 9 - 13  + 6 = 0$, so $n = -1$ is a root of the polynomial, and equivalently the polynomial has factor $n + 1$. Dividing the polynomial by $n + 1$ and factoring gives $2 n^2 + 7 n + 6 = (n + 2)(2 n + 3)$, and putting this all together gives the desired factorization:
$$\boxed{2 n^3 + 9 n^2 + 13 n + 6 = (n + 1) (n + 2) (2 n + 3)}.$$
Remark As you probably know, not all polynomials with integer coefficients factor into products of linear terms with integer coefficients as they did in this case. For example, the general formula for $\sum i^4$ analogous to the one in this question contains a factor of $3 n^2 + 3 n - 1$, which is not factorable over the integers.
</s>