Results 1 to 3 of 3

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

  1. #1
    Member
    Joined
    Dec 2008
    From
    Australia
    Posts
    161

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    4
    Quote Originally Posted by differentiate View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by differentiate View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 10
    Last Post: Jun 29th 2010, 12:10 PM
  2. Prove by induction #2
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Oct 10th 2009, 12:39 PM
  3. Prove by induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 10th 2009, 08:11 AM
  4. Prove by induction? I think...
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Sep 21st 2009, 08:43 AM
  5. prove by induction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Feb 12th 2007, 10:32 PM

Search Tags


/mathhelpforum @mathhelpforum