# mathematical induction

• Dec 9th 2009, 12:45 PM
mathematical induction
Prove that n^3-n is divisible by 3
• Dec 9th 2009, 01:06 PM
craig
Quote:

Prove that n^3-n is divisible by 3

\$\displaystyle n^3 - n = 3a\$ for some \$\displaystyle a\$.

First we see if it holds for \$\displaystyle n=0\$

\$\displaystyle 0^3 - 0 = 0\$, therefore true for \$\displaystyle n=0\$

Now we use what's called the induction step, we assume that it's true for \$\displaystyle n=k\$ where k is some natural nubmer.

This gives us \$\displaystyle k^3 - k = 3a\$

We then prove this for \$\displaystyle n=k+1\$, giving us

\$\displaystyle (k+1)^3 - k - 1\$.

Expanding the brackets gives \$\displaystyle k^3 + 3k^2 + 3k + 1 - k - 1\$

\$\displaystyle k^3 + 3k^2 + 2k\$ which can be written as \$\displaystyle k^3 + 3k^2 + 3k - k\$

\$\displaystyle (k^3-k) + 3(k^2 + k) = 3a + 3(k^2 + k)\$.

Therefore it is true for \$\displaystyle k+1\$ if true for \$\displaystyle k\$.

You know it is true for 0, therefore true for 1. True for one, therefore true for 2....

Hope this helps