Proving that $4k < 2^k$ by induction 
Prove that $4k < 2^k$ by induction.

It holds for $k = 5$. Assume $ k = n + 1 $. Then
$4(n+1) < 2^{(n+1)}$
$4n + 4 < 2^n * 2$
$2n + 2 \leq 2^n$
Now I just need to show that
$2n + 2 \leq 4n$
$n + 1 \leq 2n$
$1 \leq n$
And because I chose $n = 5$ which is greater than $1$, this should prove that the formula holds for $n \geq 5$.
Is this correct?
 A: Consider the following (see if you can determine how one step relates to another): 
\begin{align}
4(k+1)&=4k+4\\[1em]
&< 2^k+4\tag{why?}\\[1em]
&< 2^k+2^k\tag{why?}\\[1em]
&= 2\cdot2^k\\[1em]
&=2^{k+1}.
\end{align}
A: You got the basis step correct by checking that $4n<2^n$ for $n=5$.
Next, you must prove that $4N<2^N \implies 4(N+1) < 2^{N+1}$ for $N\geq5$
When trying to solve this problem, simplify the right-hand-side of this implication to a form that is easily comparable to the left-hand-side.
Notice that $4(N+1) < 2^{N+1}$ holds if and only if 
$4N+4 < 2^N *2$
Then you might notice that the inductive hypothesis gives us that 
$4N+4 < 2^N + 4$ (since we are assuming $4N < 2^N$).
These two formulae look similar, so we are almost done.
Now we need only show that $2^N + 4 < 2^N * 2 $
Notice $2^N * 2 = 2^N + 2^N $.
Can you now show that $2^N + 4 < 2^N + 2^N$ for $N \geq 5$?
Do that, and you're done! Hooray for you!
A: Hint $ $ Equivalently we seek to prove that $\,f(n) = 2^n/(4n) > 1\,$ for all $\,n\ge 5.$
Note $\,f(5)>1\,$ and $\,f(n\!+\!1)/f(n) = 2n/(n\!+\!1) \ge 1\,$ for $\,n\ge 5\,$ so $\,\color{#c00}{f(n\!+\!1) \ge f(n)}\,$ 
Hence the induction reduces to a trivial one: $ $ an $\rm\color{#c00}{increasing}$ sequence stays $\,\ge\, $ its initial value. From this view, the induction step becomes obvious, boiling down to transitivity of $\,\ge,\,$ i.e.
$$\begin{align} f(n)\ge f(5)\,&\Rightarrow\, \color{#c00}{f(n\!+\!1)\ge f(n)} \ge f(5)\\[0.3em]
{\rm i.e.}\quad P(n)\,&\Rightarrow\,P(n\!+\!1)\end{align}$$ 
Remark $ $ This is not an ad-hoc trick. Rather, it is a special case of a general method of transforming such problems into a simpler form where the inductive step is more obvious. It is a special case of multiplicative telescopy. Follow the link for many further examples.  
Note that once you prove by induction that result about increasing sequences, you can invoke the result as a Lemma for other induction problems of this type (which are quite common, as you can see from the links).
A: You made lots of little mistakes but your biggest mistake is that you inductions step, doesn't actually do any inducing.
A proper induction step always goes like this:
=======
We assume that something is true for a specific $k = n$
$\implies$
Then something is true for $k = n+1$.
======
Thus, we start with showing it is true for $k= $ base case; thus we can conclude it is true of $k = $ base case $ + 1$; thus we can conclude it is true for $k = $ base case $ + 2$; thus we con conclude it is true for $k = $ base case $ + 3$; the we can....
... and so on.  We can conclude it is true for all possible numbers $k$.
But your induction step didn't try to conclude something for $k = n + 1$ from something for $k = n$.  
Instead you tried to assume something was true for $k = n+1$ and then show if it's true for $k = n + 1 $ then $n \ge 1$ and therefor it must be true for all numbers.
This is wrong.  1) your logic is backwards.  You can't start at a conclusion and get a basic result and assume your conclusion is true.  That just isn't logical. But more importantly 2) your induction doesn't build forward step by step.  You didn't do anything to do with the statement being true for $k = n$.
THat's your big mistake.  Your small mistakes are:
a) In stating that you are trying to prove $4k < 2^k$ you didn't state the essential condition that $k \ge 5$.  This just isn't true if $k = 1,2,3,4$.
b)Your logic can't start with a conclusion, get the result $n \ge 1$ and assume you conclusion is true.  
Consider this:  Assume $25 > 36$.  Then as $47 > 25$ I get $47 > 25>  36$ so $47 > 36$.  So $11 > 0$.  So $1 > 0$.  That is a true statement so $25 > 36$.
I hope you see why that is bull#*@%.
c)  You claimed $2n+2 \le 2^n$ when you meant $2n+2 < 2^n$.
d) You claimed "all we need to show is $2n + 2 \le 4n$".  That isn't true.  If $2n+ 2 \le 4n$ and $2n+2 \le 2^n$ we can not conclude anything about how $4n$ relates to $2^n$.  Maybe $4n < 2^n$ maybe $4n > 2^n$ or maybe $4n = 2^n$.
To reach that conclusion you have to show that $4n \le 2n + 2$ and therefore as $2n+2 < 2^n$ we can conclude by transitivity that $4n < 2^n$.  
But we can't prove $4n \le 2n+2$ ... because it isn't. Or proof was flawed from the beginning because the logic of mistake b) doesn't work.
So let's fix this:
=====
Prove $4k < 2^k$ for all $k \ge 5$.
Well it is true for $k = 5$ as $4*5 = 20 < 32 = 2^5$.
Induction step:
We assume it is true for some $k = n$.  (This is okay because we know it is true for $k = n = 5$.)
So $4n < 2^n$
We need to find steps 
$\implies.....$
$\implies.....$
$\implies.....$ $4(n+1) < 2^{n+1}$.
Can we do that?
Well,
$4n < 2^n$
$4n + 4 < 2^n + 4$
$4n + 4 < 2^n + 4 \le 2^n + 4n$ (because $n \ge 1$ so $4n \ge 4$)
$4n + 4 < 2^n + 4n < 2^n + 2^n$.
$4(n+1) < 2*2^n = 2^{n+1}$
and we have proven the induction step.
Thus we can conclude as it is true for $k = 5$, it is true for $k = 6$.  And as it is true for $k = 6$ it is true for $k = 7$, and so on.  By induction we have shown it is true for all $k \ge 5$.
A: Your choice of $n$ should only be for the basis of the induction, not for the inductive step.
What you need to do is to show that if $4n<2^n$ then $4(n+1)<2^{n+1}$. One way of doing that is to say that $4(n+1)=4n+4<2^n+4$ and then argue that $x+4<2x$ for the relevant values.
