Post a New Question

Discrete Math

posted by on .

Solve the recurrence relation a_n = -6a_n - 1 + 7a_n-2, n ≥ 2, given a₀ = 32, a₁ = -17.

This is what I have figured out so far:

polynomial: x² + 6x - 7
distinct roots: 1 and -7

I do not understand how to find C₁ and C₂. How do I complete this problem? Thank you for any helpful replies.

  • Discrete Math - ,

    What method are you expected to use to solve the recurrence relation? Have you covered characteristic polynomials or generating functions?

    You seem to give me the hint that you have done characteristic polynomials, so I will solve this by characteristic polynomials. The key is, whichever method you use, check the solution by calculating a few terms.

    So you have done the first step of finding k1=1, and k2=-7.

    The solution will be in the form of:
    f(n) = C1*k1^n + C2&k2^n


    So, for n=0,
    f(0)=32 = C1*1^0 + C2*(-7)^0 = C1+C2 ...(1)
    for n=1
    f(1)=-17= C1*1^1 + C2*(-7)^1 = C1-7C2 ...(2)

    Subtract (2) from (1) to eliminate C1:
    8C2=49
    So C2=49/8
    From (1), calculate C1:
    C1=32-49/8=207/8

    So the coefficients can be described as:
    f(n) = (207/8)+(49/8)(-7)^n

    Let's calculate a few terms of f(n)
    n f(n)
    0 32
    1 -17
    2 326
    3 -2075
    4 14732
    ...

    and a few terms using the recurrence relation:
    a0=32 (given)
    a1=-17 (given)
    a2=-6*(-17)+7*32=326
    a3=...=-2075
    a4=...=14732

    So we conclude that an=f(n):
    an=f(n)=207/8 + (49/8)(-7)^n
    where C1=207/8, C2=49/8

  • Discrete Math - ,

    If you don't mind can you help with this problem?

    Solve the recurrence relation an+1 = 7an – 10an - 1, n ≥ 2, given a₁ = 10, a₂ = 29.

    The characteristic polynomial is x^2 - 7 + 10 with characteristic roots 2 and 5. Once again I get confused when I get to this part. We obtain a_n = C_1(2)^n + C_2(5)^n.

    a_1 = 3C_1 + 3C_2 = 10
    a_2 = I don't know what to put here = 29

  • Discrete Math - ,

    Oops posted twice. . .Sorry

  • Discrete Math - ,

    Solve the recurrence relation:
    an+1 = 7an – 10an-1,
    where n ≥ 2, and
    given a₁ = 10, a₂ = 29.

    You have done the first step to give:
    λ1=2, λ2=5.

    So the function is defined by the powers of λ1 and λ2, with the associated constants C1 and C2 to be determined.

    f(n) = C1*2^n + C2*5^n

    We are given
    a1=f(1) = C1*2^1 + C2*5^1 = 2C1 + 5C2 ...(1)
    a2=f(2) = C1&2^2 + C2*5^2 = 4C1 + 25C2 ...(2)
    Eliminate C1 using (2)-2(1):
    0 + 15C2 = 9 => C2 = 3/5
    Substitute C2 into (1) to get
    2C1 + (3/5)*5 = 10
    => C1 = 7/2

    Therefore
    f(n) = (7/2)2^n + (3/5)*5^n

    Check:
    f(1) = (7/2)2^1 + (3/5)*5^1 = 10
    f(2) = (7/2)2^2 + (3/5)*5^2 = 29
    f(3) = (7/2)2^3 + (3/5)*5^3 = 103
    a3 = 7a2 - 10a1 = 203-100= 103 (=f(3))
    f(4) = (7/2)2^4 + (3/5)*5^4 = 56+375=431
    a4 = 7a3-10a2 = 721-290 = 431 (=f(4))
    ....

    Make sure you understand the steps to obtain the solution.

  • Discrete Math - ,

    Thank you so much for your help! I think I am getting the hang of it better. Can you please check:

    Solve the recurrence relation a_n = -5a_n - 1 + 6a_n - 2, n ≥ 2, given a₀ = 5, a₁ = 19.

    characteristic polynomial is x^2 + 5x - 6 it has the distinct root 2 and 3.

    a_n = C_1(2)^n + C_2(3)^n
    a0 = C_1 + C_2 = 5 (1)
    a1 = 2C_1 + 3C_2 = 19 (2)

    So to find C2 I eliminated it by (2) - 2(1)

    (2C1 + 3C2) = 19
    - (2C1 + 2C2) = 10
    ___________________
    C2 = 9

    Plug this into (1) and this is where I get confused because I get a C1 = -4, is it suppose to be negative? Am I doing a step wrong?

    a_n = . . . (?)

  • Discrete Math - ,

    Unfortunately there must have been an algebraic error:
    "characteristic polynomial is x^2 + 5x - 6 it has the distinct roots 1 and -6"

    So you'd have to redo the calculations for C1 and C2.
    Once you've done that, evaluate a0,a1 as a check, and then compare a2,a3,a4 using the calculated values of C1 and C2 with those obtained by the recurrence relation. If they compare favorably, then you're done!

  • Discrete Math - ,

    Oh I feel dumb. . .

    Ok so now

    a_n = C_1(1)^n + C_2(-6)^n
    a0 = C_1 + C_2 = 5 (1)
    a1 = C_1 - 6C_2 = 19 (2)

    So to find C1 I eliminated it by 6(1) + (2) <--is this allowed?

    (6C1 + 6C2) = 30
    + (C1 - 6C2) = 19
    ___________________
    7C1 = 49
    C1 = 7

    Plug this into (1) and this is where I get confused because I get a C1 = -2, is it suppose to be negative? Am I doing a step wrong?

    a_n = . . . (?)

  • Discrete Math - ,

    C2=-2 is perfectly alright, so with C1=7, we have:
    f(n)=7-2(-6)^n, which gives

    f(0)=7-2=5 (=a0)
    f(1)=7-2(-6)=19 (=a1)
    f(2)=7-2(-6)^2=-65 (=-5*19+6*5=-65=a2)
    ...
    Check a few more and you'll be confident you have the right solution.

  • Discrete Math ?? - ,

    Guess you're in a rush!

  • Discrete Math - ,

    Idk what happened at 7:24 I think my computer had a glitch or something and it reposted.

    This one is throwing me for a loop:

    Solve the recurrence relation a_n = 2a_n - 1 – a_n -2, n ≥ 2, given a₀ = 40, a₁ = 37.

    Characteristic polynomial: x^2 - 2 + 1

    How do I find the roots?

  • Discrete Math - ,

    This is a special case:
    x^2 - 2 + 1
    λ=λ1=λ2=1.

    The general solution is
    an=C1*1^n+C2*n*1^n
    which reduces to
    an=C1+nC2

    Try to see if you can solve it!

  • Discrete Math - ,

    So the characteristic roots are 1?

  • Discrete Math - ,

    How about this:

    Solve the recurrence relation a_n+1 = -8a_n – 16a_n - 1, n ≥ 1, given a₀ = 5, a₁ = 17.

    Characteristic polynomial is: x^2 + 8x + 16 with distinct roots -4.

    Since the roots are equal a0 = 5 = C1(-4)^0 + C2(0)(-4)^0 making C1 = 5, right? But when I apply a1 = 17 = C1(4) + C2(1)(-4), it does not work for me. . .I always seem to get confused

  • Discrete Math - ,

    So, going back to the previous 9:05. The solution is a_n = 40(1)^n - 3(1)^n, is this correct or way off?

  • Discrete Math - ,

    "So the characteristic roots are 1?"
    Correct!

    For
    _n+1 = -8a_n – 16a_n - 1, n ≥ 1, given a₀ = 5, a₁ = 17.
    you have correctly solved for
    λ=-4, and the solution is
    an=C1(-4)^n+C2*n*(-4)^n
    which simplifies to:
    an=(C1+nC2)(-4)^n

    a0=5=(c1+0*C2)(-4)^0=C1, so C1=5 (correct)
    For
    a1=17=(C1+1*C2)(-4)^1=(5+C2)(-4)
    which gives C2=-37/4

    Now check a2:
    a2=(5 - 37n/4)(-4)^2=-216
    Also,
    a2=-8a1-16a0=-8*17-16*5=-136-80=-216

    So everything works (so far).
    Check at least two more terms and you'll be a pro at it!

  • Discrete Math - ,

    For 9:05 pm
    an=(C1+nC2)1^n=C1+nC2
    a0=40 => C1=40
    a1=31 => 31=(40+1*C2) => C2=-9

    Maybe you should show your work how you got C2=-3

  • Discrete Math - ,

    Well a_1 = 37 not 31

  • Discrete Math - ,

    Sorry, your answer is correct.
    You can check this by calculating a2 & a3 both ways:
    a2=40-3*2=34
    a3=40-3*3=31

    a2=2*a1-a0=2*37-40=34
    a3=2*a2-a1=2*34-37=31

    So the coefficients are correct [as long as the initial values are correct ;>) ]

  • Discrete Math - ,

    Hey thanks a lot for help!

  • Discrete Math :) - ,

    You're welcome!

Answer This Question

First Name:
School Subject:
Answer:

Related Questions

More Related Questions

Post a New Question