Thursday

May 28, 2015

May 28, 2015

Posted by **Francesca** on Tuesday, April 5, 2011 at 4:11pm.

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 -
**MathMate**, Tuesday, April 5, 2011 at 6:34pmWhat 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 -
**Francesca**, Tuesday, April 5, 2011 at 8:51pmIf 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 -
**Francesca**, Tuesday, April 5, 2011 at 9:12pmOops posted twice. . .Sorry

- Discrete Math -
**MathMate**, Tuesday, April 5, 2011 at 9:34pmSolve the recurrence relation:

a_{n+1}= 7a_{n} 10a_{n-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 -
**Francesca**, Tuesday, April 5, 2011 at 10:21pmThank 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 -
**MathMate**, Tuesday, April 5, 2011 at 11:10pmUnfortunately 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 -
**Francesca**, Tuesday, April 5, 2011 at 11:27pmOh 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 -
**MathMate**, Tuesday, April 5, 2011 at 11:47pmC2=-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 ?? -
**MathMate**, Wednesday, April 6, 2011 at 7:32amGuess you're in a rush!

- Discrete Math -
**Francesca**, Wednesday, April 6, 2011 at 6:06pmIdk 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 -
**MathMate**, Wednesday, April 6, 2011 at 9:05pmThis 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 -
**Francesca**, Wednesday, April 6, 2011 at 9:30pmSo the characteristic roots are 1?

- Discrete Math -
**Francesca**, Wednesday, April 6, 2011 at 9:36pmHow 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 -
**Francesca**, Wednesday, April 6, 2011 at 10:33pmSo, 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 -
**MathMate**, Wednesday, April 6, 2011 at 10:44pm"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 -
**MathMate**, Wednesday, April 6, 2011 at 10:48pmFor 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 -
**Francesca**, Wednesday, April 6, 2011 at 11:03pmWell a_1 = 37 not 31

- Discrete Math -
**MathMate**, Wednesday, April 6, 2011 at 11:20pmSorry, 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 -
**Francesca**, Wednesday, April 6, 2011 at 11:41pmHey thanks a lot for help!

- Discrete Math :) -
**MathMate**, Thursday, April 7, 2011 at 7:38amYou're welcome!