# Thread: Math of Induction - Divisbility

1. ## Math of Induction - Divisbility

I'm trying to prove $\displaystyle 3|(x^3 - x)$ through induction. (and for 5 in $\displaystyle x^5 - x$ but that's for later)
Done the base case which simplifies to 2
Assume for $\displaystyle x = k$ evaluates to $\displaystyle k(k + 1) = \mathbb{I}$
Inductive prove for $\displaystyle x = k + 1$ evaluates to $\displaystyle (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:
$\displaystyle \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 $\displaystyle 3|\left( {k^3 - k} \right)$ is true. Then look at:
$\displaystyle \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 $\displaystyle 3|(x^3 - x)$ through induction. (and for 5 in $\displaystyle x^5 - x$ but that's for later)
Done the base case which simplifies to 2
Assume for $\displaystyle x = k$ evaluates to $\displaystyle k(k + 1) = \mathbb{I}$
I dont understand the stuff you have written....

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

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

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

By Induction Hypothesis, $\displaystyle 3|k^3 - k$, 3 clearly divides $\displaystyle 3(k^2 + k)$, thus 3 divides the sum $\displaystyle 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 $\displaystyle 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.

$\displaystyle 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 $\displaystyle 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 $\displaystyle 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 $\displaystyle x^p - x$ is divisible by $\displaystyle p$ for any prime $\displaystyle 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 $\displaystyle (k+1)^p$ are divisible by $\displaystyle p$, when $\displaystyle p$ is prime. This is simply because the numerator of $\displaystyle \frac{p!}{r!(p-r)!}$ has a prime factor $\displaystyle p$ for $\displaystyle 1\le r\le p-1$, but the denominator doesn't.