# Thread: Prove by induction that (3^n + 5^n)/2 >> 4^n

1. ## Prove by induction that (3^n + 5^n)/2 >> 4^n

Prove by induction that $\displaystyle \frac{3^n + 5^n}{2} >> 4^n$

Thank you

2. Originally Posted by differentiate
Prove by induction that $\displaystyle \frac{3^n + 5^n}{2} >> 4^n$

Thank you
Hi differentiate,

If $\displaystyle \frac{3^n+5^n}{2}\ \ge\ 4^n$

then try to prove that this causes

$\displaystyle \frac{3^{n+1}+5^{n+1}}{2}\ \ge\ 4^{n+1}$

P(k)

$\displaystyle \frac{3^k+5^k}{2}\ \ge\ 4^k$ ?

P(k+1)

$\displaystyle \frac{3^{k+1}+5^{k+1}}{2}\ \ge\ 4^{k+1}$ ?

Proof

$\displaystyle \frac{3^{k+1}+5^{k+1}}{2}\ \ge\ 4^{k+1}$ ?

$\displaystyle \frac{(3)3^k+(5)5^k}{2}\ \ge\ (4)4^k$ ?

$\displaystyle (3)\frac{3^k+5^k}{2}+(2)\frac{5^k}{2}\ \ge\ (3)4^k+4^k$ ?

If $\displaystyle \frac{3^k+5^k}{2}\ \ge\ 4^k$

then as $\displaystyle 5^k>4^k$

$\displaystyle \frac{3^{k+1}+5^{k+1}}{2}\ \ge\ 4^{k+1}$

Test for n=0 or n=1.
As it is true, the inequality is true for all natural n.

3. Originally Posted by differentiate
Prove by induction that $\displaystyle \frac{3^n + 5^n}{2} >> 4^n$

Thank you
Your question is not complete, for which it is required that $\displaystyle n$ be defined, since in the case of $\displaystyle n=1$, the statement $\displaystyle \frac{3^n + 5^n}{2} >> 4^n$
is false, i.e. $\displaystyle 4 \not > 4$. So for it to be true $\displaystyle n$ ought to be greater than 2.

Since we must prove by induction, we will restate the question correctly. So let $\displaystyle P(n):\frac{3^n + 5^n}{2} > 4^n$ for $\displaystyle n\geq 2$, $\displaystyle n \in \mathbb{N}$.

$\displaystyle Proof:$

Basis step:

\displaystyle \begin{aligned} P(2): \frac{3^2 + 5^2}{2} &> 4^2\\ 17 &> 16 \end{aligned}

Next is the Inductive step:

We will prove that $\displaystyle P(k) \Rightarrow P(k+1)$ is true.

So
$\displaystyle P(k):\frac{3^k + 5^k}{2} > 4^k$. We multiply both sides by 2 and obtain

$\displaystyle 3^k + 5^k > 2 \cdot 4^k$ Next, multiply both sides by 3 and obtain

$\displaystyle 3 \cdot 3^k + 3\cdot 5^k > 3 \cdot 2 \cdot 4^k$. We now add to both side $\displaystyle 2 \cdot 5^k$ and obtain

\displaystyle \begin{aligned} 3 \cdot 3^k + 3\cdot 5^k +2\cdot 5^k&> 3 \cdot 2 \cdot 4^k+2\cdot 5^k\\ 3 \cdot 3^k + 5\cdot 5^k &> 2(3 \cdot 4^k+ 5^k)\\ \frac{3^{k+1} + 5^{k+1}}{2} &> 3 \cdot 4^k+ 5^k\\ \frac{3^{k+1} + 5^{k+1}}{2} &> 3 \cdot 4^k+ 5^k \end{aligned}.

Next, we add and subtract $\displaystyle 4^k$ to the right hand side and obtain
\displaystyle \begin{aligned} \frac{3^{k+1} + 5^{k+1}}{2} &> 3 \cdot 4^k+ 4^k -4^k+ 5^k\\ \frac{3^{k+1} + 5^{k+1}}{2} &> 4 \cdot 4^k -4^k+ 5^k\\ \frac{3^{k+1} + 5^{k+1}}{2} &> 4^{k+1} + (5^k-4^k)\\ \end{aligned}

Since the smallest integer permissible for the basis step is $\displaystyle 2$, we substitue 2 for k for the items in the parenthesis and obtain

\displaystyle \begin{aligned} \frac{3^{k+1} + 5^{k+1}}{2} &> 4^{k+1} + (5^2-4^2)\\ \frac{3^{k+1} + 5^{k+1}}{2} &> 4^{k+1} + (25-16)\\ \frac{3^{k+1} + 5^{k+1}}{2} &> 4^{k+1} + 9 >4^{k+1}\\ P(k+1):\frac{3^{k+1} + 5^{k+1}}{2} &>>4^{k+1}\\ \end{aligned}

Now the proof is complete.