8

I'm doing the following induction proof and wanted to know if this was valid. I think it is, but I'm seeing more complicated solutions than what I did. What I did seems much easier.

Prove that $3^n+4^n<5^n$ for all $n>2$.

When $n=3$ we get $91<125$. No problem, now assume the result is true from $k<n$, $(5^k>3^k+4^k)$ and consider $5^{k+1}=5 \times 5^k>5(3^k+4^k)=5\times 3^k + 5\times 4^k>3\times 3^k+4\times 4^k=3^{k+1}+4^{k+1}$ since $5\times 3^k>3\times 3^k$ and $5\times 4^k> 4\times 4^k$.

ddswsd
  • 1,337

2 Answers2

3

Another proof, NO INDUCTION! -- just for fun.

Let $\ n\ge 3.\ $ then:

$$ 3^n + 4^n <\, 3^2\cdot 5^{n-2} + 4^2\cdot 5^{n-2} \,=\, (3^2+4^2)\cdot 5^{n-2}\, =\ 5^n $$

REMARK   If you look at the above proof under a magnifying glass then you may see induction after all -- just a trace.

Wlod AA
  • 2,124
2

Here's a method I like for showing $f(n) > g(n)$ for $n \ge n_0$.

  1. Show that $f(n_0) > g(n_0)$.

  2. Show that, if $n \ge n_0$ and $f(n) > g(n)$ then $f(n+1)-f(n) \ge g(n+1)-g(n) $.

Then $f(n) > g(n)$ for $n \ge n-0$.

In this case, $f(n) = 5^n, g(n) = 3^n+4^n$.

Choose $n_0 = 3$. $f(n_0) = 5^3=125, g(n_0) = 3^3+4^3 = 91 \lt f(n_0)$. So (1) holds.

If $n \ge 3$ and $f(n) > g(n)$ then

$f(n+1)-f(n) =5^{n+1}-5^n =4\cdot 5^n \gt 4(3^n+4^n),\\ g(n+1)-g(n) =2\cdot 3^n+3\cdot 4^n \lt 3(3^n+4^n) \lt f(n+1)-f(n) $.

marty cohen
  • 107,799