Prove by induction that $\frac{n^3}{3}+\frac{2n}{3}$ is an integer.

Question

The question that I am working on is:

Prove that $\dfrac{n^3}{3}+\dfrac{2n}{3} \in \mathbb Z \ \forall \ n \in \mathbb N$

The method that I think would be will work for this question is that I say that $3|(n^3+2n)$ and prove that.Would this be a good way to do this question?

So far I have done the following:

1) Base Case n = 1
$3|n^3+2n = 3|3 \checkmark$

2) Assume, $n^3+2n$ is divisible by $3$ for $n =k, k \in \mathbb N$

$k^3+2k = 3m , m \in \mathbb N$

Let $n = k + 1$ ; Then:

$(k+1)^3 + 2(k+1)$ = $k^3+2k+3k^2+3k+3$

Since $k^3+2k = 3m$

$3m + 3k^2+3k+3$

Now, I'm stuck I don't know what else to do further.

Answer 1

$$( k + 1 )^3 = k^3 + 3 k^2 + 3k + 1$$

For $n = k + 1$ $$(k + 1)^3 + 2(k + 1) = k^3 + 3k^2 + 3k + 2k + 3$$

If $k^3 + 2k$ is divisible by $3,$ it is ovious that $$k^3 + 3k^2 + 3k + 2k +3=(k^2+2k)+3(k^2+k+1)$$ is dividable by $3.$

Answer 2

Look at this:

assuming

$\dfrac{k^3 + 2k}{3} \in \Bbb Z, \tag{1}$

we have

$\dfrac{(k + 1)^3 + 2(k + 1)}{3} = \dfrac{k^3 + 3k^2 + 3k + 1 + 2k + 2}{3} = \dfrac{(k^3 + 2k) + 3(k^2 + k +1)}{3}$ $= \dfrac{k^3 + 2k}{3} + k^2 + k + 1 \in \Bbb Z, \tag{2}$

by (1).

QED!!!

Answer 3

The last step should have been

$3m+3k^2+3k+3=3(m+k^2+k+1)$ whereupon dividing by $3$ produces an integer.

Answer 4

$$ { n }^{ 3 }+2n=0\quad mod\left( 3 \right) $$

$${ \left( n+1 \right) }^{ 3 }+2\left( n+1 \right) =$$ $$={ n }^{ 3 }+3{ n }^{ 2 }+3n+1+2n+2= \left( { n }^{ 3 }+2n \right) +3\left( n^{ 2 }+n+1 \right) =0\quad mod\left( 3 \right) $$

Answer 5

not induction, but maybe useful to note:

firstly, since 3 is a prime, we have $n^3 \equiv_3 n$ (Fermat's little theorem)

secondly $2n \equiv_3 -n$ (since $3n = 2n + n \equiv_3 0$)

adding these two results: $$ n^3 + 2n \equiv_3 n-n =0 $$

Answer 6

This will be an addition to the above answers: Note that $n^3 + 2n = (n^3-n)+3n = n(n^2-1)+3n = (n-1)n(n+1) + 3n$, each term of the sum is divisible by $3$, hence $3 \mid n^3+2n \Rightarrow \dfrac{n^3+2n}{3} \in \mathbb{N}$

Answer 7

Proof Using Burnside Lemma:

Consider a round table with $3$ seats. The chair at each seat can be selected from $n$ types of chairs. In how many ways can we arrange the chairs, if two arrangements are considered the same when one can be rotated into the other?

The group of symmetry of the chair arrangement is the cyclic group $C_3$ of order $3$. This group acts on the chair arrangement via chair rotations. For any of the two nonidentity elements $g\in C_3$, the arrangements fixed by $g$ are those where all chairs are colored the same, which there are $n$ ways to do so. For the identity element of $C_3$, all of the possible $n^3$ arrangements are fixed. Hence, the number of arrangements when rotations are ignored is given by $\frac{1}{3}\left(n^3+n+n\right)=\frac{n^3+2n}{3}$, which must then be an integer.

In general, if the round table has $m$ seats, then the number of all chair arrangements when there are $n$ types of chairs and when rotations are ignored is given by $$\frac{\sum_{d\mid m}\,\phi(d)\cdot n^{m/d}}{m}\,.$$ Here, $\phi$ is Euler's totient function.

Answer 8

The short way: $T_0=0$ and $T_{n+1}-T_n=n^2+n+1$ are integers.