Results 1 to 5 of 5
Like Tree2Thanks
  • 1 Post By Idea
  • 1 Post By Idea

Thread: Demonstration by Induction

  1. #1
    Newbie
    Joined
    Nov 2018
    From
    Spain
    Posts
    4

    Post Demonstration by Induction

    Hi, I've been trying to demonstrate this:
    I know that $d_1=1, d_2=10, d_3=50, d_4=248$ and for $n \geq 5 ,d_n = 5d_{n-1} - 4d_{n-4} $. Demonstrate for all
    $n \in \mathbb{N} $ that: $$P(n): d_n < n \cdot 3^{n+1}. $$

    I need to demostre this using the induction principle. My doubt is in the second part of the demonstration.

    First, I check if P(1) until p(4) is true
    $d_1=1 \geq 3$ so P(1) verifies
    $d_2=10 \geq 2\cdot3^{3}=18$ so P(2) verifies.
    $d_3 = 50 < 3 \cdot 3^{3+1} = 243$ so P(3) verifies.
    $d_4 = 248 < 4 \cdot 3^{4+1} = 972$ so P(4) verifies.

    Now, the second part is where I have the problem. I do not know what to do. I understand the theory but I don't know how to apply it. This is what I thought

    Then, I assume true P(n) for $n \in \mathbb{N}$ and $n \geq 5$ is true, so
    $$d_n < n \cdot 3^{n+1}. \text{ is true}$$

    We know too that for $n \geq 5, d_n = 5d_{n-1} - 4d_{n-4}$, so
    $d_{n+1} = 5d_{n} - 4d_{n-3}$. Later, we clear $$5d_{n}=d_{n+1}+4d_{n-3}.$$

    Then, by Inductive Hypothesis I deduce that:
    $$5d_n < 5n \cdot 3^{n+1}.$$

    So:
    $$ d_{n+1}+4d_{n-3}< 5n \cdot 3^{n+1}$$

    Then
    $$d_{n+1}<d_{n+1}+4d_{n-3}< 5n \cdot 3^{n+1}.$$

    I want to demonstrate that $d_{n+1}<(n+1)3^{n+2}.$

    So i tried to compare $5n \cdot 3^{n+1}$ and $(n+1)3^{n+2}$ trying to prove that
    $$5n \cdot 3^{n+1}<(n+1)3^{n+2}.$$

    If someone find a way or give me some advice, pls write it.
    My English is not good at all, but I tried my best.

    Thanks in advance,
    Raimaths
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jun 2013
    From
    Lebanon
    Posts
    877
    Thanks
    414

    Re: Demonstration by Induction

    $\displaystyle d_9 = 752596$

    is not less than

    $\displaystyle 9 * 3^{10}=531441$
    Thanks from Raimaths
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2018
    From
    Spain
    Posts
    4

    Re: Demonstration by Induction

    It's true. Sorry, I have made an error copying it. I'll change it.
    Last edited by Raimaths; Nov 9th 2018 at 05:48 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Nov 2018
    From
    Spain
    Posts
    4

    Demonstration by Induction Correct

    Im my last post I made and error copying the wording. So, I changed and tried to solve it again, but here I am again. My doubt is again in the second part of the demonstration. The wording is the same, but changing < for >.

    I know that $d_1 = 1$, $d_2 = 10$, $d_3 = 50$, $d_4 = 248$ and for $ n \geq 5 $, $d_n = 5d_{n-1} - 4d_{n-4} $. Demonstrate for all $ n \in N $ and $ n \geq 9$ that:
    $$P(n):d_n > n \cdot 3^{n+1}.$$

    As you could see at the last message, changing "<" for ">", We notice that for $d_1$ to $d_8$ the proposition for these $n$ values is false ($P(1...8)$ is false). However, like Idea said, applying it to his new wording, $P(9)$ is true. Ive verified it for $n=10,n=11$ and $n=12$ too. So its seem that for $n \geq 9 $ ($ n \in N $) $P(n)$ is true.

    Applying demonstration by induction:

    (1) We see that $d_9= 752596 > 9 \cdot 3^{10}=531441$, so $P(9)$ is true.
    (2) Then, I assume true $P(n)$ for $ n \in N$ and $n \geq 9$ is true, so
    $$d_n>n\cdot3^{n+1}.$$

    I want to demonstrate $d_{n+1}>(n+1)\cdot3^{n+2}.$

    I know that $d_{n+1}=5d_n - 4d_{n-3}$ so byInductive Hypothesis $d_{n+1}=5d_n - 4d_{n-3}>5n3^{n+1} -4d_{n-3}$. One thing I tried, is comparing $5n \cdot 3^{n+1} - 4d_{n-3}$ and $(n+1)\cdot3^{n+2}$.

    If someone find a way or give me some advice write it, pls.
    Last edited by Raimaths; Nov 9th 2018 at 09:43 AM. Reason: Wrong wording
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Jun 2013
    From
    Lebanon
    Posts
    877
    Thanks
    414

    Re: Demonstration by Induction

    Let
    $\displaystyle c_n=d_n-d_{n-1}$

    1) Show that $\displaystyle c_n=4\left(c_{n-1}+c_{n-2}+c_{n-3}\right)$

    2) Use (1) and induction to prove $\displaystyle c_n>3^n(2n+1)$

    3) use induction again to show

    $\displaystyle d_n=d_{n-1}+c_n>(n-1)3^n+(2n+1)3^n=n 3^{n+1}$
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Big O, little o demonstration
    Posted in the Differential Geometry Forum
    Replies: 6
    Last Post: Mar 16th 2011, 09:46 PM
  2. Demonstration, please help.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 24th 2010, 09:05 AM
  3. Demonstration
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: Jun 26th 2009, 01:32 AM
  4. Demonstration
    Posted in the Calculus Forum
    Replies: 0
    Last Post: Jun 8th 2009, 02:42 PM
  5. demonstration - help
    Posted in the Algebra Forum
    Replies: 3
    Last Post: Aug 14th 2007, 03:05 PM

Search Tags


/mathhelpforum @mathhelpforum