# Thread: Using my assumption when proving by induction

1. ## Using my assumption when proving by induction

I had to prove by induction that n³ - n is divisible by 3.

What I did was expanded (n + 1)³ - (n + 1) and simplified it and I got n(n + 1)(n + 2). From my assumption that it is true for all n, I can see that this is also divisible by n and so it has been proved for the (n + 1) term.

Is that correct?

2. It's a little hard to understand...
What I did was expanded (n + 1)³ - (n + 1) and simplified it and I got n(n + 1)(n + 2). From my assumption that it is true for all n, I can see that this is also divisible by n
What is true for all n? Do you mean that n(n + 1)(n + 2) is divisible by 3 (not n) because one of the factors is a multiple of 3? You are correct, but you have a direct proof rather than a proof by induction because you never use the induction hypothesis. (Coming up with a direct proof is usually more difficult than with a proof by induction.) Indeed, given some n, you have to prove that n³ - n is divisible by 3. Let k = n - 1. Then n³ - n = (k + 1)³ - (k + 1), and then you proceed as before.

In a proof by induction, you assume that n³ - n is divisible by 3. Then (n + 1)³ - (n + 1) = n³ - n + 3(n^2 + n), which is divisible by 3 using the assumption.

3. q

4. Here is how you would write the inductive proof:

Proving $\displaystyle n^3 - n$ is divisible by 3 for natural numbers $\displaystyle n \geq 0$

=================

Base case:
$\displaystyle 0^3 - 0 = 0$ is divisible by 3.

=================

Induction step:
Assume $\displaystyle n^3 - n$ is divisible by 3 for some $\displaystyle n$.
We need to prove that $\displaystyle (n+1)^3 - (n+1)$ is divisible by 3 given the assumption.

$\displaystyle (n+1)^3 - (n+1) = n^3 + 3n^2 + 3n + 1 - n - 1 = (n^3 - n) + 3(n^2 + n)$
$\displaystyle n^3 - n$ is divisible by 3 by our assumption.
$\displaystyle 3(n^2 + n)$ is divisible by 3.
This means the sum is also divisible by 3.

So we have proved our induction step (n+1)^3 - (n+1) is divisible by 3 (assuming $\displaystyle n^3 - n$ is divisible by 3).

=================

With the proofs of the base case and inductive step, we have proved by induction:
$\displaystyle n^3 - n$ is divisible by 3 for natural numbers $\displaystyle n \geq 0$

5. Originally Posted by snowtea
Here is how you would write the inductive proof:

Proving $\displaystyle n^3 - n$ is divisible by 3 for natural numbers $\displaystyle n \geq 0$

=================

Base case:
$\displaystyle 0^3 - 0 = 0$ is divisible by 3.

=================

Induction step:
Assume $\displaystyle n^3 - n$ is true
is divisible by 3
for some $\displaystyle n$.
We need to prove that $\displaystyle (n+1)^3 - (n+1)$ is true
is divisible by 3
given the assumption.

$\displaystyle (n+1)^3 - (n+1) = n^3 + 3n^2 + 3n + 1 - n - 1 = (n^3 - n) + 3(n^2 + n)$
$\displaystyle n^3 - n$ is divisible by 3 by our assumption.
$\displaystyle 3(n^2 + n)$ is divisible by 3.
This means the sum is also divisible by 3.

So we have proved our induction step (n+1)^3 - (n+1) is divisible by 3 (assuming $\displaystyle n^3 - n$ is divisible by 3).

=================

With the proofs of the base case and inductive step, we have proved by induction:
$\displaystyle n^3 - n$ is divisible by 3 for natural numbers $\displaystyle n \geq 0$