Thread: Induction divisibility P1

1. Induction divisibility P1

Could someone help me with these questions? I just need to prove n=k+1 using the assumption that n=K

Prove:
1) n^3 - n is divisible by 6 for n=2,3,4...
2) n^4 - 1 is divisible by 3 for n=1,2,3...
3) n(n^2 +5) is divisible by 6 for n=1,2,3....

Thank you ! =)

2. Sorry, but I couldn't understand your questions in the other thread...
so for 1)
the proposition is: $n^3 - n = 6k$ for $n \geq 2, k \in \mathbb{Z}$
so you try for (n = 2):
$(2)^3 - (2) = 6k$
$8 - 2 = 6k$
which is true for k = 1.

Then you accept the hypothesis: $n^3 - n = 6k$ for $n \geq 2, k \in \mathbb{Z}$ for all n. And try and show that:

$(n + 1)^3 - (n + 1) \stackrel{?}{=} 6k$
$(n^3 + 3n^2 + 3n + 1) - (n + 1) = 6k$
$n^3 + 3n^2 + 2n = 6k$
$(n^3 - n) + (3n^2 + 3n) = 6k$ sub assumption, ie. $n^3 - n = 6k$

this means that you're only interested in showing that:
$(3n^2 + 3n) = 6k$
$3n(n + 1) = 6k$

and then for $n \geq 2$ you see that if n is even that 3 times an even number is divisble by 6 (3n). If n is odd you see that the (n + 1) term is even and so once again 3 times an even number (greater than 2 (lol)) is also divisible by 6. (You should probably write this up in a more formal way.) Finished.

3. Originally Posted by christina
Could someone help me with these questions? I just need to prove n=k+1 using the assumption that n=K

Prove:
1) n^3 - n is divisible by 6 for n=2,3,4...
2) n^4 - 1 is divisible by 3 for n=1,2,3... please check this, it's not divisible by 3
3) n(n^2 +5) is divisible by 6 for n=1,2,3....

Thank you ! =)
1)

$\frac{n^3-n}{6}=natural\ number$ ?

$\frac{(n+1)^3-9n+1)}{6}=\frac{n^3+3n^2+3n+1-n-1}{6}$

$=\frac{n^3-n+3n^2+3n}{6}=\frac{n^3-n}{6}+\frac{3n(n+1)}{6}$

The right fraction is $\frac{n(n+1)}{2}$

which is the sum of the first n natural numbers, definately a natural number, hence if

$n^3-n$ is divisible by 6, so is $(n+1)^3-(n+1)$

Then test for n=1.

3)

$\frac{n\left(n^2+5\right)}{6}=natural\ number$ ?

$\frac{(n+1)\left((n+1)^2+5\right)}{6}=\frac{(n+1)( n^2+2n+1+5)}{6}=\frac{n\left(n^2+2n+6\right)+n^2+2 n+6}{6}$

$=\frac{n\left(n^2+5\right)+n(2n+1)+n^2+2n+6}{6}=\f rac{n\left(n^2+5\right)+2n^2+n+n^2+2n+6}{6}$

$=\frac{n\left(n^2+5\right)}{6}+\frac{3n^2+3n}{6}+\ frac{6}{6}$

$=\frac{\left(n^2+5\right)}{6}+\frac{n(n+1)}{2}+1$

Since the middle fraction is the sum of the first n natural numbers, it's also natural, hence

$\frac{(n+1)[(n+1)^2]+5}{6}\ is\ natural\ if\ \frac{n\left(n^2+5\right)}{6}\ is$

test for n=1.