Prove by induction that $2^n + 4^n \leq 5^n$ I'm trying to prove by induction that $2^n + 4^n \leq 5^n$. Through some value plugging I've established that the induction must start from $n = 2$ because $2^2 + 4^2 \leq 5^2 \equiv 20 \leq 25$; for $n = 1$ it doesn't hold since $2 + 4 \geq 5$. 

Now I assume that $2^k + 4^k \leq 5^k$ is true and I want to prove that implies $k+1$. Using the inductive hypothesis I multiply both sides by $4$ to get this: 
$$4 \cdot 2^{k} + 4\cdot 4^{k} \leq 4 \cdot 5^{k}$$
$$2^{k+2} + 4^{k+1} \leq 4 \cdot 5^{k}$$
I will use again the induction hypothesis, this time I'll multiply both side by $5$ to get:
$$5 \cdot (2^{k} + 4^{k}) \leq 5^{k+1}$$
I can say that $2^{k+2} + 4^{k+1} \leq 5 \cdot (2^{k} + 4^{k})$ and $4 \cdot 5^{k} \leq 5^{k+1}$ so I concatenate them:
$$2^{k+2} + 4^{k+1} \leq 5 \cdot (2^{k} + 4^{k}) \leq 4 \cdot 5^{k} \leq 5^{k+1}$$

However this doesn't feel right. I'm assuming that $5 \cdot (2^{k} + 4^{k}) \leq 4 \cdot 5^{k}$ which there's no way I can be sure about. At this point I'm stuck since the whole reasoning seems wrong.
 A: You almost proved it in the beginning, then went somewhat off-course. You showed at first that $2^{k+2} + 4^{k+1} ≤ 4*5^k$ inductively. But now $4 < 5$, so $4*5^k < 5^{k+1}$ and hence $2^{k+2} + 4^{k+1} ≤ 5^{k+1}$. In fact, this shows that the inequality is strict for all $n ≥ 2$.
A: You already have established from the induction hypothesis that 
$$2^{k+2} + 4^{k+1} \leq 4 \cdot 5^{k}$$
So:
$$ 2^{k+1} + 4^{k+1} < 2^{k+2} + 4^{k+1} \leq 4\cdot5^k < 5 \cdot 5^k =5^{k+1}$$
Which already shows the required inequality for $k+1$.
It's simpler than you think...
A: It can be done much easier: assume $2^k+4^k\le 5^k$, and see
\begin{align}
5^{k+1}&=5\cdot5^k\\
&\ge 5\cdot 2^k+5\cdot4^k\\
&\ge2\cdot 2^k+4\cdot4^k\\
&=2^{k+1}+4^{k+1}\\
\end{align}
Completing the induction.
A: Just remove the step $5\cdot (2^k+4^k)$ from your last inequality and you're fine.  You get $$2^{k+2} + 4^{k+1} \leq 4 \cdot 5^{k} \leq 5^{k+1},$$ where the first inequality is exactly what you proved before. (You aren't quite done, though, since you want $2^{k+1}+4^{k+1}$ instead of $2^{k+2}+4^{k+1}$ on the left-hand side.  I'll leave it to you to finish.)
A: Assume that $2^k + 4^k \leq 5^k$ is true.
Then
\begin{align} 2^{k+1} + 4^{k+1} & \leq 2 ( 2^{k} + 4^{k}) + 2\cdot 4^k \\
& \le 2 \cdot 5^k + 2 \cdot 4^k  \\ 
& \le 2 \cdot 5^k + 2 \cdot 5^k  \\ 
& \le 4 \cdot5^k \\
& \le  5^{k+1}
\end{align}
A: By Karamata for all $n \geq2$ we obtain:
$$2^n+4^n<5^n+1^n=5^n+1.$$
Thus, $2^n+4^n\leq5^n$.
Done!
