# Prove $n^3 + 7n + 3$ is divisible by 3 for all integers n ≥ 0

The statement I'm trying to prove is:

$n^3 + 7n + 3$ is divisible by 3 for all integers n ≥ 0

I eventually need to prove $(k + 1)^3 + 7(k + 1) + 3$ is divisible by 3.

I don't really understand how to deal with $k + 1$, so I'm a little lost.

I've know that the base case of P(0) is true, but I'm not sure about proving the inductive case.

• It's not true for $k=0$. It is true for $n=0$, but you didn't get to the variable $n$ until after saying $P(0)$ is true... Feb 5, 2016 at 17:45
• It's only divisible by $3$ when $k+1$ is divisible by $3$, specifically. Feb 5, 2016 at 17:46
• Maybe you meant $n^3 -7n+3$? Feb 5, 2016 at 18:03
• yur statement is not true. peter.petrov has given a nice counter example. Feb 5, 2016 at 18:18

The statement is not true. Take $n=1$ as a counter example.

Since it's not true, you won't manage to prove it (by induction or otherwise).

• nice observation, +1 Feb 5, 2016 at 18:17

Take $k+1=j$ and take modulo $3$. So the question is if $j^3+j$ is a multiple of $3$, but $j^3+j=j(j^2+1)$, which is never a multiple of $3$ if $j$ isn't.

Set $n=k+1$ then your expression is equivalent modulo 3 to $$n^3+7n+3 \equiv n+7n+3 \equiv 8n \equiv -n \pmod{3}.$$ In particular, this is a multiple of $3$ iff $3$ divides $k+1$.

The given statement $$n^3 + 7n + 3$$ is divisible by 3 for $$n ≥ 0$$ is not true, as detailed below P(n): n^3. + 7n + 3 is divisible by 3 P(1): 1^3 + 7(1) + 3 = 11 which is not divisible by 3 P(2): 2^3 + 7(2) + 3 = 25 which is also not divisible by 3 Hence given statement is not true.

I presume that statement may be n^3 - 7n + 3 is divisible by 3 for n ≥ 0 In that case Proof is detailed below.

P(n): n^3 - 7n + 3 is divisible by 3 P(1): (1)^3 -7(1) + 3 = 1 -7 + 3 = -3 which is divisible by 3

Assume P(k) is true for some positive integer k, i.e P(k): (k)^3 - 7k + 3 is divisible by 3 We can write (k)^3 - 7k + 3 = 3d, where d ∈ N ………….. (1) We shall prove that P(k+1) is also true, whenever P(k) is true. Now we have P(k+1): (k+1)^3 - 7(k+1) + 3
= k^3 + 1^3 +3.k.1(k+1) - 7(k+1) + 3 (Using (a+b)^3 = a^3 + b^3 + 3ab(a+b)

    = k^3 + 1 +3k(k+1) - 7(k+1) + 3
= k^3 + 1 + 3k^2 + 3k -7k - 7 +3
= k^3 - 7k + 3 + 3k^2 +3k - 6  (by rearranging)
= 3d + 3(k^2 + k - 2 ).........{From (1)}
= 3d + 3(k^2 + 2k - k - 2 )
= 3d + 3 {k(k +2)-(k+2)}
= 3d + 3 (k-1)(k+2)
= 3 {d +(k-1)(k+2)}
= 3 q,  where q = {d +(k-1)(k+2)} which is some positive integer


From the last line, we see (k+1)^3 - 7(k+1) + 3 ) is divisible by 3. Thus P(k+1) is true, whenever P(k) is true. Hence, by the PMI, the given statement is true for all natural numbers n ≥ 0