1
$\begingroup$

I have these notes, but I'm confused on what is happening at the inductive step.

Theorem:

$\forall n \in \mathbb{N} 3 | (n^3-n) $

Inductive Step:

For $n \geq 0, show P(n) \Rightarrow P(n+1) is True$

Assume P(n) true i.e. $3 | (n^3-n) $

Examine:

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

I understand what we're trying to prove but

  1. where does $(n+1)^3 - (n+1) $ come from?
  2. What is happening here $n^3 - n + 3n^2 + 3n$, how did we get there from the previous point? I assume $n^3 + 3n^2 + 2n $ is not obvious if it was divisible by 3, thus we assumed $3 | (n^3-n) $ is true... But how does step 2 become 3?

Thanks in advance

$\endgroup$
3
$\begingroup$

$P(n+1)$ is the statement that $(n+1)^3 - (n+1)$ is divisible by 3. Just fill in $n+1$ in $P(n)$. So you have to simplify this expression first.

The equality between 2 and 3 is just algebra (you write $2n$ from the second term as $3n - n$, which is true for all $n$).

Why would you do this? Because you want to use your assumption that $P(n)$ is true, which says that $n^3 - n$ is divisible by 3. The second term has no term $n^3 - n$ but it has an $n^3$ and then substracts $n$ to get the number $n^3 - n$, about which we know something (!), and add $n$ to another term to compensate and keep the equality.

Now note that the last line is a sum of multiples of 3, the first one, $n^3 - n$, by the inductive assumption.

$\endgroup$
1
  • $\begingroup$ thanks for your answer, it's really obvious now, I've +1 since it helped me get a better understanding :) $\endgroup$
    – boywonder
    Oct 30 '15 at 10:25
2
$\begingroup$
  1. $(n+1)^3-(n+1)$ comes from the expression $n^3-n$ when you replace $n$ with $n+1$. This is the induction step - to show that $(n+1)^3-(n+1)$ is divisable by $3$ if we assume that $n^3-n$ is.
  2. Here the following happens: $n^3-n$ is divisable by $3$ (by the inductive assumption), $3n^2$ is divisable, $3n$ is divisable, therefore, their sum $n^3-n+3n^2+3n$ is divisable too. (Note that $+2n=-n+3n$ here from 2 to 3.)
$\endgroup$
0

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.