By induction:
It's true for
, since 
clearly contains a factor of 3.
Suppose it's true for
, that 
is divisible by 3. Then
where
is an integer. This reduces to
and both terms are clearly multiples of 3. We know that
is an integer since we had set 
previously, which implies is a multiple of 
. So the statement is true.
It's true for
Suppose it's true for
where
and both terms are clearly multiples of 3. We know that