Prove by induction that $n^3-n+3$ is divisible by 3 for all natural numbers $n$

Question

Show that $n^3-n+3$ is divisible by $3$ for all natural numbers $n$

What would the step by step induction proof be?

Answer 1

Base case: $n=0$, then we get that $3$ is divisible by $3$ since plugging in $0$ yields $0^3-0+3$.

So for some $k \in \mathbb{Z}^+$ we can assume that $k^3-k+3$ is divisible by $3$. What about $k+1$?

Plug in $k+1$ and use the previously mentioned hypothesis to show that it is divisible by $3$.

Answer 2

Proof by induction involves demonstrating the truth of a base case, then showing that if it can be assumed true for any step it will true for the successor.

$$P(0) , \forall n{\in}\Bbb N\;(P(n)\to P(n+1)) \;\vdash\; \forall n{\in}\Bbb N\; (P(n))$$

Here the predicate $P(n)$ is that $3\mid(n^3-n+3)$ .

1. Show that $P(0)$ is true.

2. Show that if any $P(n)$ is true, then so is $P(n+1)$

ie: Can you show that $3\mid((n+1)^3-(n+1)+3)$ is true whenever $3\mid(n^3-n+3)$ is so?

Answer 3

Here's a method different from induction: Notice that

$$n^3-n-3 = n(n^2-1)-3 = (n-1)n(n+1) - 3.$$

The first term is a product of three consecutive integers, one of which must be a multiple of $3$, and the last term is certainly divisible by $3$ too.

The exercise says you need to use induction, but this should give you another insight as to why it is true.

Answer 4

Note that $0^3-0+3$ is divisible by $3$.

Now assume for some $n$, that $n^3 - n +3$ is divisible by $3$. (You know that it's true for $n=0$, so there is at least some validity for this assumption moving forward.)

We have that $$\begin{align} (n+1)^3 - (n+1) + 3 &=n^3 + 3n^2 + 3n + 1 - n - 1 + 3\\ &=\left(n^3-n+3\right)+3n^2+3n \end{align}$$ In this last expression, the latter two terms are clearly divisible by $3$. By our assumption, the expression in the parentheses is also divisible by $3$. Therefore, $(n+1)^3 - (n+1) + 3$ is divisible by $3$.

Now back to the beginning: $$\begin{align} 3\mid0^3-0+3& \implies3\mid1^3-1+3\\ &\implies3\mid2^3-2+3\\ &\implies3\mid3^3-3+3\\ &\implies\ldots\\ &\implies3\mid n^3-n+3\text{ for any $n$} \end{align}$$

Answer 5

For proof by induction; these are the $\color{red}{\mathrm{three}}$ steps to carry out:

Step 1: Basis Case: For $n=1 \implies n^3-n+3= 1^3-1+3=3$ which is divisible by $3$. So statement holds for $n=1$.

Step 2: Inductive Assumption: Assume statement is true for $n=k$ such that $n^3-n+3=\color{blue}{(k^3-k+3)}=\color{blue}{3p} \tag{1}$ Where $p,k \in \mathbb{N^+}$.

Step 3: Prove Statement holds for $n=k+1$ such that $$n^3-n+3=(k+1)^3-(k+1)+3$$ $$=k^3+3k^2+3k+1-k-1+3=3k^2+3k+\color{blue}{(k^3-k+3)}= 3(k^2+k)+\color{blue}{3p}$$ using our inductive assumption $(1)$ the resulting expression clearly is divisible by $3$.

Hence $n^3-n+3$ is divisible by $3$ $\forall \space n \in \mathbb{N^+}$

QED

Answer 6

The induction step will work only if $((n+1)^3-(n+1)-3) -(n^3-n-3) $ is divisible by $3$. But that difference is $3n^2+3n+1-1 =3n(n+1) $, which is obviously by $3$.

Note that, since one of $n$ and $n+1$ is even, this difference is actually divisible by $6$, so that if $n^3-n-3$ is divisible by $6$ for some $n$, it is divisible by $6$ for all subsequent $n$.

However, this is $3$ for $n = 0$. Therefore $n^3-n+3 \bmod 6 = 3$ for all integral $n$.

Of course, a direct way to prove this is to note that $n^3-n =(n-1)n(n+1) $, and this is divisible by $6$ because it is the product of $3$ consecutive integers.