Prove that for every integer $n\geq 0$, $1+3n\leq 4^n$.
Proof:
Let the property $P(n)$ be the inequality $$1+3n\leq 4^n.$$ Establishing $P(0)$, we see that $1+3(0)=1$ and $4^0=1$, hence $P(0)$ is true.
Suppose $k$ is any integer with $k\geq 0$ such that $$1+3k\leq 4^k.$$ We must show $$1+3(k+1)\leq 4^{k+1}.$$ By algebra, we see $$1+3(k+1)=1+3k+3=(3k+1)+3\leq4^{k+1}=4^k\cdot4^1.$$
Since $1+3k \leq 4^k$ (by the inductive hypothesis) and $3\leq 4^k\cdot4^1$ (for $k\geq0$), therefore $$(3k+1)+3\leq4^{k+1}.$$
I think it's good enough, but I might have overlooked something. Is this correct? Thank you.
You should've put a questionmark above one of the $\le$ signs, like so:
$$1+3(k+1)=1+3k+3=(3k+1)+3\stackrel{?}\leq 4^{k+1}=4^k\cdot 4^1\tag{1}$$
You can't conclude that just because $A\le C_1\le C$ and $B\le C$ we have $A+B\le C$. This seems to be what you used in your proof, but I am not sure.
This is how you could've continued your proof:
Since by inductive hypothesis $3k+1\le 4^k$, we have $$(3k+1)+3\le 4^k+3\tag{2}$$
But $(4^k+3\le 4^{k+1}=4\cdot 4^k=4^k+3\cdot 4^k)\iff (3\le 3\cdot 4^k), \forall k\ge 0$.
So that
$$4^k+3\le 4^{k+1}\tag{3}$$
Now combine $(1),(2),(3)$ and you have that $P(k)\implies P(k+1), \forall k\ge 0$, and you've already shown that $P(0)$ is true, so our proof by induction is done. $\ \ \ \square$