Results 1 to 3 of 3

Math Help - 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  \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
    1
    Quote Originally Posted by differentiate View Post
    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.
    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  \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}<br />
P(2): \frac{3^2 + 5^2}{2} &> 4^2\\<br />
17 &> 16<br />
\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}<br />
3 \cdot 3^k + 3\cdot 5^k +2\cdot 5^k&> 3 \cdot 2 \cdot 4^k+2\cdot 5^k\\<br />
3 \cdot 3^k + 5\cdot 5^k &> 2(3 \cdot 4^k+  5^k)\\<br />
\frac{3^{k+1} + 5^{k+1}}{2} &> 3 \cdot 4^k+  5^k\\<br />
\frac{3^{k+1} + 5^{k+1}}{2} &> 3 \cdot 4^k+  5^k<br />
\end{aligned}.

    Next, we add and subtract 4^k to the right hand side and obtain
    \begin{aligned}<br />
\frac{3^{k+1} + 5^{k+1}}{2} &> 3 \cdot 4^k+ 4^k -4^k+  5^k\\<br />
\frac{3^{k+1} + 5^{k+1}}{2} &> 4 \cdot 4^k -4^k+  5^k\\<br />
\frac{3^{k+1} + 5^{k+1}}{2} &> 4^{k+1} +  (5^k-4^k)\\<br />
\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}<br />
\frac{3^{k+1} + 5^{k+1}}{2} &> 4^{k+1} +  (5^2-4^2)\\<br />
\frac{3^{k+1} + 5^{k+1}}{2} &> 4^{k+1} +  (25-16)\\<br />
\frac{3^{k+1} + 5^{k+1}}{2} &> 4^{k+1} + 9 >4^{k+1}\\<br />
P(k+1):\frac{3^{k+1} + 5^{k+1}}{2} &>>4^{k+1}\\<br />
\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: June 29th 2010, 01:10 PM
  2. Prove by induction #2
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 10th 2009, 01:39 PM
  3. Prove by induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 10th 2009, 09:11 AM
  4. Prove by induction? I think...
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 21st 2009, 09:43 AM
  5. prove by induction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 12th 2007, 11:32 PM

Search Tags


/mathhelpforum @mathhelpforum