the number of subsets for a set with order $n$ is $2^n$. Consequently, $2^n-1 \neq 2^{n-1}$ in general, so it is false.
To prove this fact, you can actually use induction!
More specifically, think about the number of ways you can have a k-element subset which is going to be$\dbinom{n}{k}$ [how many ways can you pick a group of k people out of an $n$-person group.] Then all possible subsets will look like the total number of ways to be pick $k$-element subsets. In particular:
$$\dbinom{n}{0}+\dbinom{n}{1}+...+\dbinom{n}{n}=2^n$$
For practice, try to prove this with induction.
For (2), the base case is clear. We assume that $3 \mid n^3+3n^2+2n$. This means that there exists some integer $k$ so that $3k=n^3+3n^2+2n$
Then:
$$\begin{align}(n+1)^3+3(n+1)^2+2(n+1)&=(n^3+3n^2+3n+1)+3(n^2+2n+1)+2n+2 \\
&=(n^3+3n^2+2n)+3n+3+3(n^2+2n+1)\\ \end{align}$$
by substitution from the hypothesis, we obtain:
$$\begin{align}&=3k+3(n^2+3n+2) \\
&=3(n^2+3n+2+k)\end{align}$$
Hence, the result follows readily.
I leave part 3 to you. You got the induction step correctly, at least in the set up. Try some algebraic manipulation to start with; keep in mind what your assumption is, you just want it to show up somewhere in your inductive step. Induction is an easy enough idea, but the problem is that it doesn't show much in the way of intuition. As in, it generally doesn't tell you why something works. We just get used to the fact that it solves problems for us. Kind of like l'hopital's rule in Calculus.
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
No, your proof is not correct. You are correct up to this point:
$$(k+1)\cdot 4^k > 4^{k+1}$$
However, you then claim that by dividing both sides by $4^k$, you get
$$k+1>\frac{4}{4^k}$$ which is not true. In fact, dividing both sides by $4^k$, you get
$$k+1 > \frac{4^{k+1}}{4^k}\neq \frac{4}{4^k}$$