I assume that by "complete mathematical induction" you refer to what is often known as "strong induction." Yes, this approach notes that if you are reasoning inductively and can show that $P(1)$ is true and $P(k) \implies P(k+1)$, then you can examine the general case $P(n+1)$ with not only $P(n)$ in your toolbox, but each of $P(1), P(2), \ldots, P(n)$.
For the particular proposition that you gave, strong induction is not helpful. The standard proof by mathematical induction is exactly as you have written it. (Of course, it is not the only way to prove this proposition: you could consider that $4^n = (3+1)^n$ and when the latter is expanded you have a sum of terms that are each divisible by $3$ except the final term, a $1$, which disappears since you are considering $4^n - 1$. But this gets away from your query...)
For an example that is more elucidating, consider proving that every natural number greater than $2$ can be factored entirely into primes. Try proving this by induction and you will see that it is not so helpful: the base case goes through fine, but if you have a natural number $n$, really what you want to say is that either $n$ is prime (and you're done) or $n$ is composite and can be written as $n = a \cdot b$ for two natural numbers $a, b < n$. And it is here that one essentially stagnates with the standard inductive approach.
The advantage of strong induction in this case is that you can say, since each of $a$ and $b$ is less than $n$, they satisfy the inductive hypothesis of being factorable into primes, so each can be factored and these factorizations can then be multiplied together to give a prime decomposition of $n$.
Best Answer
HINT $\ $ Put $\rm\ f(n)\: =\: n^3 - 4\ n\:.\:$ To show that $\rm\ 3\ |\ n\ f(n)\:$ it suffices too show $\rm\ 3\ |\ f(n)\:.\:$ To prove this by induction note that $\rm\ 3\ |\ f(n+1)-f(n)\ =\ 3\ (n^2+n-1)\:.\: $ Therefore we deduce that
$\qquad$ since $\rm\ \ 3\ |\ f(n+1)-f(n),\ \ $ if $\rm\ \ 3\ |\ f(n)\: \ $ then $\rm\ \ 3\ |\ f(n+1)-f(n)+f(n) \ =\ f(n+1)$
which yields the inductive step, viz. $\rm\ 3\ |\ f(n)\ \Rightarrow\ 3\ |\ f(n+1)\:.\:$ The base step is: $\rm\:3\ |\ f(0)\: =\: 0\:.\:$
The same technique works very generally - see my many prior posts on telescopy.