Results 1 to 4 of 4
Like Tree3Thanks
  • 3 Post By SlipEternal

Thread: Solving this recurrence relation

  1. #1
    Newbie
    Joined
    Sep 2017
    From
    Around.
    Posts
    15

    Exclamation Solving this recurrence relation

    Solve the recurrence relation an = an-1 + 2an-2 with initial conditions a0 = a1 = 1 by making the substitution bn = an.

    I made the substitution from the beginning. Never seen an example like this. My working...

    bn = 1bn-1 + 2bn-2

    Characteristic equation form: x2 = ax + b implies x2 = 1x + 2

    x2 -x -2 = 0

    (x - 2)(x + 1) = 0

    x = 2, -1.

    General solution is bn = A(2)n + B(-1)n

    When n = 0; b0 = a0 = 1 = 1.

    1 = A(2)0 + B(-1)0
    1 = A(1) + B

    When n = 1; b1 = a1= 1 = 1.

    1 = A(2)1 + B(-1)1
    1 = 2A - B

    Solving simultaneous equations...

    A = 2 / 3.

    B = 1 / 3.

    Solution is (2/3)2n + (1/3)(-1)n.

    Method is correct?
    Last edited by Induction; Oct 19th 2017 at 05:25 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Dec 2013
    From
    Colombia
    Posts
    1,821
    Thanks
    592

    Re: Solving this recurrence relation

    Method looks fine to me, barring a final answer for a_n.
    Last edited by Archie; Oct 19th 2017 at 06:17 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,967
    Thanks
    1140

    Re: Solving this recurrence relation

    Let's check:

    $\sqrt{\dfrac{2}{3}2^n+\dfrac{1}{3}(-1)^n} = \sqrt{\dfrac{2}{3}2^{n-1}+\dfrac{1}{3}(-1)^{n-1}}+2\sqrt{\dfrac{2}{3}2^{n-2}+\dfrac{1}{3}(-1)^{n-2}}$?

    Try with $n=2$:

    $\sqrt{3} = \sqrt{1}+2\sqrt{1}$ is false.

    Instead, you need to use the fact that $b_n = \sqrt{a_n}$ implies

    $a_n = b_n^2 = \left(\dfrac{2}{3}2^n+\dfrac{1}{3}(-1)^n\right)^2 = \dfrac{4}{9}4^n+\dfrac{4}{9}(-2)^n+\dfrac{1}{9}$

    Now, we test:
    $a_0 = \dfrac{4}{9}+\dfrac{4}{9}+\dfrac{1}{9} = 1$ check
    $a_1 = \dfrac{16}{9}-\dfrac{8}{9}+\dfrac{1}{9} = 1$ check
    $\sqrt{a_n} = \sqrt{a_{n-1}}+2\sqrt{a_{n-2}}$ satisfied by construction. Check.

    Yup, that's the solution.
    Thanks from Plato, topsquark and Induction
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Sep 2017
    From
    Around.
    Posts
    15

    Re: Solving this recurrence relation

    Right, if I squared my solution; it would've been fine for an​.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Solving a recurrence relation.
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: Jan 11th 2011, 03:05 PM
  2. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 16th 2010, 02:56 AM
  3. Solving Recurrence Relation
    Posted in the Calculus Forum
    Replies: 0
    Last Post: Feb 16th 2009, 05:43 PM
  4. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: Feb 14th 2009, 07:24 PM
  5. Solving a recurrence relation
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Jan 12th 2009, 11:19 PM

/mathhelpforum @mathhelpforum