0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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... $\endgroup$ Feb 5, 2016 at 17:45
  • $\begingroup$ It's only divisible by $3$ when $k+1$ is divisible by $3$, specifically. $\endgroup$ Feb 5, 2016 at 17:46
  • 2
    $\begingroup$ Maybe you meant $n^3 -7n+3$? $\endgroup$
    – Lubin
    Feb 5, 2016 at 18:03
  • $\begingroup$ yur statement is not true. peter.petrov has given a nice counter example. $\endgroup$ Feb 5, 2016 at 18:18

4 Answers 4

4
$\begingroup$

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).

$\endgroup$
1
  • $\begingroup$ nice observation, +1 $\endgroup$ Feb 5, 2016 at 18:17
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
-1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .