0
$\begingroup$

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.

$\endgroup$

2 Answers 2

1
$\begingroup$

Hint:

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

$\endgroup$
1
  • $\begingroup$ Ok that is my next step then. $\endgroup$
    – TheEditor
    Dec 1, 2015 at 20:57
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Ohhhh. Ok I feel really stupid. It wasn't factored, just rewritten for n+1. I totally missed what was happening here. Thank you. $\endgroup$
    – TheEditor
    Dec 1, 2015 at 20:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .