Im having a lot of trouble proving by induction that $3^n + 5^n \geq 2^{n+2}.$
The base step is easy, but I don't seem to find the way to proof the inductive step.
Asked
Active
Viewed 99 times
1
-
Just notice that $2<3$ and $2<5$... – zozoens Feb 03 '14 at 21:28
-
@zozoens I've noticed over the years that when people start focusing on the method of proof they often overlook those little details that make things work out. – John Habert Feb 03 '14 at 21:29
3 Answers
4
Inductive step
$$3^{n+1} + 5^{n+1}=3\times3^{n} + 5\times5^{n}\geq2(3^{n} + 5^{n}) \geq2\times 2^{n+2}=2^{n+3}$$
3
Hint $\ $ Dividing by $2^n$ it is $(3/2)^n + (5/2)^n \ge 4.\,$ But for any $\,a,b\ge 1,$ $\,f_n = a^n+b^n\,$ is increasing, therefore $\,f_1\ge 4\,\Rightarrow\, f_n\ge f_1\ge 4.\,$
Remark $\ $ By a little rearranging, we reduced the induction to more intuitive inductions about increasing functions (which still require inductive proof, but the proofs are straightforward, using prior intuition about increasing functions). In the same way, such intuitive preprocessing often allows one to transform inductive proofs into simpler or well-known forms, e.g. see many prior posts on induction via telescopy.
Bill Dubuque
- 272,048
0
n=1: 3+5=8=2^3 Assume true for some natural k: 3^k+5^k >= 2^(k+2)^[induction hypothesis)
n=k=1: 3.3^k+5.5^k= 3(3^k+5^k)+5^k(5-3) >=3.(2^(k+2)) +2.5^k (by Induction hypothesis) so then 3.3^k+5.5^k > 2((2^(k+2)) (as all positive numbers i.e, if a>0 3a>2a and if b>0 a+b>a) so we are done.... Trick was to add and subtract 3.5^k or 5.3^k would work too
Jens
- 281