Factoring equations, non quadratic.

Question

I'm taking the MIT opencouseware 6.042, Mathematics for CS. Working with induction proofs. It's been years since I've done this, and I'm not sure how he factored this.

Assume p(n) true:

$3|(n^3 -n)$

How did he get?

$(n + 1)^3 - (n + 1)$

Also, what should I be looking for for a refresher for this? Factoring is a broad search term.

Answer 1

If you are doing a proof by induction, what you want to do is, after checking the base case, assume that your statement holds for $n$, and use this to show that it holds for $n+1$.

So here, in the inductive step, the write assumes $p(n)$, that is that $3|(n^3-n)$, and wants to use it to show that $p(n+1)$ holds, i.e. that $3|(n+1)^3-(n+1)$.

Answer 2

Hint:

By the binomial formula, $$(n+1)^3-(n+1)=(n^3-n)+3n^2+3n.$$