I have the following question: Prove with mathematical induction that $3^n+4^n\le 5^n$ for all $n\ge 2$. $$\text{Assume true: }3^n+4^n \le 5^n \text{. Prove that $3^{n+1}+4^{n+1} \le 5^{n+1}$} \\ = 3\cdot3^n+4\cdot4^n \\ =3\cdot3^n+4^n(3+1)\\ =3\cdot3^n+3\cdot4^n+4^n \\ =3(3^n+4^n)+4^n \\ \le 3(5^n)+4^n \\ (5-2)(5^n)+4^n \\ 5^{n+1} - 2\cdot5^n+4^n\\ 5^{n+1} - 2\cdot(3^n+4^n) +4^n$$ I am stuck on. I see now that I double the $5^n$, and this leads me nowhere. Where can I go from here to solve this? I have tried playing with the algebra, but I am not getting anywhere with this last step.
Asked
Active
Viewed 135 times
3
-
1You are almost there. Since $4\le 5$, $4^n\le 5^n$, and in the middle there you have $3\cdot 5^n+4^n<3\cdot 5^n+5^n=4\cdot 5^n<5^{n+1}$ – pancini Oct 09 '20 at 22:54
2 Answers
5
How about this, with the same first step: $$\begin{align*} 3^{n+1} + 4^{n+1} &\le 3 \cdot 3^n + 4 \cdot 4^n \\ &\le 5 \cdot 3^n + 5 \cdot 4^n \\ &\le 5(3^n + 4^n) \\ &\le 5 \cdot 5^n \\ &= 5^{n+1} \end{align*} $$
Lee Mosher
- 120,280
-
-
I should of stated that I assumed $3^n+4^n \le 5^n$ is true for all $n\ge 2$. I don't know if I could use this with my assumption. – Oct 09 '20 at 23:10
-
That's not how induction works. You cannot assume that $3^n + 4^n \le 5^n$ is true for all $n \ge 2$ because that's what you are trying to prove. Instead, you first do the basis step, proving that $3^n + 4^n \le 5^n$ is true for $n=2$. Then you do the induction step, by proving that the following implication is true for all $n$: $$\text{If $3^n + 4^n \le 5^n$ then $3^{n+1} + 4^{n+1} \le 5^{n+1}$}$$ Which is what my answer does. – Lee Mosher Oct 10 '20 at 00:41
-
1
From where you left off, we have $$ 5^{n+1}-2(3^n+4^n)+4^n=5^{n+1}-2\cdot3^n - 4^n\leq 5^{n+1} $$ and your proof is finished.
Arthur
- 199,419