# Thread: Math of Induction - Divisbility

1. ## Math of Induction - Divisbility

I'm trying to prove $3|(x^3 - x)$ through induction. (and for 5 in $x^5 - x$ but that's for later)
Done the base case which simplifies to 2
Assume for $x = k$ evaluates to $k(k + 1) = \mathbb{I}$
Inductive prove for $x = k + 1$ evaluates to $(k + 1)(k + 2)$
But I'm guessing you have to add and minus some value before to incorporate the assumption so I'm guessing we do something here:
$\frac{3k^2 + 9k + 6}{3}$
Don't know what exactly, pointers?

Sorry about the mundane question. I'm not wired to think the 2 steps ahead for proofs.

2. Assume that $3|\left( {k^3 - k} \right)$ is true. Then look at:
$\left( {k + 1} \right)^3 - \left( {k + 1} \right) = k^3 + 3k^2 + 2k = \left( {k^3 - k} \right) + 3\left( {k^2 + k} \right)$.
Is that clearly a multiple of 3?

3. Originally Posted by sogetthis
I'm trying to prove $3|(x^3 - x)$ through induction. (and for 5 in $x^5 - x$ but that's for later)
Done the base case which simplifies to 2
Assume for $x = k$ evaluates to $k(k + 1) = \mathbb{I}$
I dont understand the stuff you have written....

But if you substituted x = 2 and checked if $3|2^3 - 2$ for the base case, then you are right.(or have taken the easier route $3|1^3 - 1$)

Induction Hypothesis: Assume the result is true for x = k: This means $3|k^3 - k$
We want to prove the Induction Step: $3|(k+1)^3 - (k+1)$

But $(k+1)^3 - (k+1) = (k^3 + 1 + 3k + 3k^2) - (k+1) = (k^3 - k) + 3(k+k^2)$

By Induction Hypothesis, $3|k^3 - k$, 3 clearly divides $3(k^2 + k)$, thus 3 divides the sum $k^3 - k + 3(k^2 + k) = (k+1)^3 - (k+1)$

4. Okay so you add and subtract a k to get the assumed value and a multiple of 3.
Thanks, got it for 5 | x^5 - x too.

5. By the way, you said you were to use induction so that is the way you were answered. But $x^3- x= x(x^2- 1)= (x-1)(x)(x+1)$, the product of three consecutive integers (assuming x is an integer). One of them has to be a multiple of 3.

$x^5- x= x(x^4-1)= x(x^2-1)(x^2+ 1)= x(x-1)(x+1)(x^2+1)$ is a little harder. If x is a multiple of 5, then we are done. if x= 5n+1, then x-1= 5n, a multiple of 5, and we are done. If x= 5n+ 2, then neither x-1= 5n+1 nor x+1= 5n+ 3 is a multiple of 5 but $x^2+ 1= 25n^2+ 20n+ 4+ 1= 5(5n^2+ 4n+ 1)$ is a multiple of 5. If x= 5n+ 3, then neither x-1= 5n+2 nor x+1= 5n+4 is a multiple of 5 but $x^2+ 1= 25n^2+ 30n+ 9+ 1= 5(5n^2+ 6n+ 2)$ is a multiple of 5. Finally, if x= 5n+4, then x+1= 5n+ 5= 5(n+1) is a multiple of 5.

6. ## Divisibility

Hello everyone -

It is perhaps interesting to observe that $x^p - x$ is divisible by $p$ for any prime $p$.

The proof (by induction) follows exactly the same lines as before, noting that, with the exception of the first and last terms, all the coefficients in the expansion of $(k+1)^p$ are divisible by $p$, when $p$ is prime. This is simply because the numerator of $\frac{p!}{r!(p-r)!}$ has a prime factor $p$ for $1\le r\le p-1$, but the denominator doesn't.