Discrete Math
posted by Francesca on .
Solve the recurrence relation a_n = 6a_n  1 + 7a_n2, 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.

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 = C17C2 ...(2)
Subtract (2) from (1) to eliminate C1:
8C2=49
So C2=49/8
From (1), calculate C1:
C1=3249/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 
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 
Oops posted twice. . .Sorry

Solve the recurrence relation:
a_{n+1} = 7a_{n} – 10a_{n1},
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 = 203100= 103 (=f(3))
f(4) = (7/2)2^4 + (3/5)*5^4 = 56+375=431
a4 = 7a310a2 = 721290 = 431 (=f(4))
....
Make sure you understand the steps to obtain the solution. 
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 = . . . (?) 
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! 
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 = . . . (?) 
C2=2 is perfectly alright, so with C1=7, we have:
f(n)=72(6)^n, which gives
f(0)=72=5 (=a0)
f(1)=72(6)=19 (=a1)
f(2)=72(6)^2=65 (=5*19+6*5=65=a2)
...
Check a few more and you'll be confident you have the right solution. 
Guess you're in a rush!

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? 
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! 
So the characteristic roots are 1?

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 
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?

"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=8a116a0=8*1716*5=13680=216
So everything works (so far).
Check at least two more terms and you'll be a pro at it! 
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 
Well a_1 = 37 not 31

Sorry, your answer is correct.
You can check this by calculating a2 & a3 both ways:
a2=403*2=34
a3=403*3=31
a2=2*a1a0=2*3740=34
a3=2*a2a1=2*3437=31
So the coefficients are correct [as long as the initial values are correct ;>) ] 
Hey thanks a lot for help!

You're welcome!