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

• Apr 10th 2010, 02:51 AM
differentiate
Prove by induction that (3^n + 5^n)/2 >> 4^n
Prove by induction that $\frac{3^n + 5^n}{2} >> 4^n$

Thank you
• Apr 10th 2010, 03:46 AM
Quote:

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

Thank you

Hi differentiate,

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

then try to prove that this causes

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

P(k)

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

P(k+1)

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

Proof

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

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

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

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

then as $5^k>4^k$

$\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.
• Apr 10th 2010, 10:22 AM
novice
Quote:

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

Thank you

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

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

$Proof:$

Basis step:

\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 $P(k) \Rightarrow P(k+1)$ is true.

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

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

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

\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 $4^k$ to the right hand side and obtain
\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 $2$, we substitue 2 for k for the items in the parenthesis and obtain

\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.