7
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ You pretty-much proceed by trial and error. Note that the middle coefficients aren't as helpful as the ends. If there are going to be "nice" factors, they'll need to look like $$(\text{factor of } 2) n \pm (\text{factor of } 6)$$ (You can rule-out possibilities like $2n\pm 2$ and $2n\pm 6$, as these have factors of $2$ that the full polynomial lacks.) To test what works, you can try clever grouping, or you can observe that $a n + b$ is a factor if $-b/a$ is a root (a value of $n$ that makes the polynomial become $0$). Since $2(-1)^3+9(-1)^2+13(-1)+6=0$, we know that $n-(-1)$ is a factor. $\endgroup$ – Blue Sep 29 '18 at 22:29
  • 1
    $\begingroup$ It's worth noting that technology can handle this stuff for you. For instance, you can use WolframAlpha to perform the factorization. $\endgroup$ – Blue Sep 29 '18 at 22:33
  • $\begingroup$ Had no idea Wolfram Alpha could do that -- going to be helpful for checking my own working. Thanks a ton! $\endgroup$ – mathimpaired Sep 29 '18 at 23:31
  • 1
    $\begingroup$ WolframAlpha is essentially an online version of Mathematica, which is serious mathematical software. It can do pretty much anything. It easily does stuff like the summation that triggered your question. (Disclaimer: I'm not associated with Wolfram. I'm just a fan and a customer.) $\endgroup$ – Blue Sep 29 '18 at 23:49
  • 1
    $\begingroup$ Probably the best way to do it is to use the rational root theorem like @Blue says. There are some more clever and cool answers in the comments, but really for the everyday drudgery like this it's easiest to just use the theorem; now if THAT doesn't work, then I would start looking other ways. But textbooks don't expect you to know tricks like Chief VOLDERMORT's for example, any polynomial of degree $\ge3$ that comes up should be factoriable either using the rational root theorem or by simple grouping. $\endgroup$ – Ovi Sep 30 '18 at 1:56
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ One point of clarification: "Expanding the right-hand side and comparing like terms in n quickly gives that a=2,b=7,c=6" ... so e.g. $an^2(n+1)+bn(n+1)+c(n+1)$ then somehow we can work back to values of a, b and c? I'll have to try that. The tip RE: finding zeros easily for -1 is also something I think I would have missed. The rational root theorem is something I know I'm going to find valuable too. Thanks for all of this, super helpful as a starting point for further understanding where I went wrong here. $\endgroup$ – mathimpaired Sep 29 '18 at 23:27
  • 1
    $\begingroup$ You're welcome, I'm glad you found it useful. If you ask a follow-up question, feel free to post the link as a reply to my answer, and I'll take a look at it. $\endgroup$ – Travis Sep 30 '18 at 0:49
  • 1
    $\begingroup$ And yes, that's exactly what I mean by comparing like terms. Expanding and collecting terms by powers then gives $$a n^3 + (a + b) n^2 + (b + c) n + c = 2 n^3 + 9 n^2 + 13 n + 6 .$$ Now, two polynomials agree if and only each of their coefficients agrees, so we have $$a = 2, \quad a + b = 9, \quad b + c = 13, \quad c = 6 .$$ Substituting the first equation into the second, for example, recovers $b = 7$ like we wanted. There's trick/observation, by the way, for checking whether $1$ is a root of a polynomial similar to that for $-1$. $\endgroup$ – Travis Sep 30 '18 at 0:50
  • $\begingroup$ Hm I think I'll probably end up using something like synthetic division using roots for now until I get a little more comfortable with the mechanics. Still appreciate all the insight here. Accepted your answer, thanks again! $\endgroup$ – mathimpaired Sep 30 '18 at 7:41
  • 1
    $\begingroup$ I assume you meant to write $p/q$ rather than $p, q$ in your first sentence. $\endgroup$ – N. F. Taussig Sep 30 '18 at 8:41
4
$\begingroup$

Recall (in your question) the line ... $$=\frac{(n^2+n)(2n+1)+6(n+1)^2}{6}$$

What followed, however was a missed opportunity, for $n^2+n$ factors as $n(n+1)$, so your expression becomes $$\begin{align} \frac{(n^2+n)(2n+1)+6(n+1)^2}{6} &= \frac{n(n+1)(2n+1)+6(n+1)^2}{6}\\ &= \frac{(n+1)\bigg(n(2n+1)+6(n+1)\bigg)}{6}\\ &= \frac{(n+1)(2n^2+n+6n+6)}{6}\\ &= \frac{(n+1)(2n^2+7n+6)}{6}\\ \end{align} $$ and all that remains to do is to factor the quadratic $2n^2+7n+6$, and you're done. :-)

$\endgroup$
  • 1
    $\begingroup$ D'oh, you're absolutely right! I just accepted Travis' answer because it's a more general solution & there were a number of "missing links" in there that I wouldn't have figured out on my own without a lot more reading. Also, I can't trust myself to "see" the kind of thing that you just pointed out here. But I was also very much hoping somebody would point out something like this! Thanks a ton. $\endgroup$ – mathimpaired Sep 30 '18 at 7:36
2
$\begingroup$

Find a single root of the polynomial through trial and error and then apply long division. Dividing $(2n^3+9n^2+13n+6)$ by $(n+1)$ yields $(n+2)(2n+3)=2n^2+7n+6$. A root of $-1$ yields a factor of $(n+1)$.

$\endgroup$
2
$\begingroup$

Step-by-step simplification $$2n^3 + 9n^2+13n+6$$ $$= 2n(n^2 + 4n + 4) + (n^2+5n+6)$$$$=2n(n+2)^2+(n+2)(n+3)$$$$=(n+2)(n+3+2n(n+2))$$$$=(n+2)(n+3+2n^2+4n)$$$$=(n+2)(2n^2+5n+3)$$$$=(n+2)(2n(n+1) + 3(n+1))$$$$ = (n+2)(n+1)(2n+3)$$

$\endgroup$
  • $\begingroup$ last line mistake. $\endgroup$ – Takahiro Waki Sep 29 '18 at 22:36
  • $\begingroup$ Thans @TakahiroWaki $\endgroup$ – Chief VOLDEMORT Sep 29 '18 at 22:38
  • $\begingroup$ I think I can mostly follow this, but how did you "know" to pull out $n^2 + 5n + 6$ specifically in your first step? I tried similar approaches, but they typically led me to dead ends. Wondering if I'm missing some key/"obvious" insight here. $\endgroup$ – mathimpaired Sep 29 '18 at 23:25
  • 1
    $\begingroup$ My personal approach to factorise polynomials of 3degree(power) or more is to take out such power of x that we have a square term left. for example from power of three we take common a single. As to having $$n^2 + 5n + 6$$ it was left after taking $$8n^2+8n$$ for left side term. I was trying to convert the left side term into something factorisable preferably a square. $\endgroup$ – Chief VOLDEMORT Sep 29 '18 at 23:56
  • $\begingroup$ You will start to "know" the steps after a certain amount of practise $\endgroup$ – Chief VOLDEMORT Sep 29 '18 at 23:57
1
$\begingroup$

put $n=-1,-2$, and get $0$. Then this equation has factor $(n+1)(n+2)$.

$\endgroup$
1
$\begingroup$

You should have factored $(n+1)$ at your first numerator and factor the resulting quadratic easily.

Even at this point where you have a cubic you have $x=-1$ as a candidate so divide the cubic by $(x+1) $ and factor the resulting quadratic.

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