- #1
Solve Recurrence Relation w/ 3 Terms & Initial Conditions
- Context: MHB
- Thread starter yakin
- Start date
Click For Summary
Discussion Overview
The discussion revolves around solving a third-degree recurrence relation with given initial conditions. Participants explore the process of deriving the characteristic equation, finding its roots, and constructing a general solution based on these roots.
Discussion Character
- Technical explanation
- Mathematical reasoning
- Homework-related
Main Points Raised
- One participant asks for a step-by-step explanation of how to solve the recurrence relation.
- Another participant suggests identifying the characteristic equation and its roots as a starting point.
- A participant provides the characteristic equation as \(r^3-2r^2-r+2=0\) and prompts others to find its roots.
- One participant claims to have found the roots \(r=2\), \(r=1\), and \(r=-1\) but expresses uncertainty about how to derive the characteristic polynomial.
- Another participant explains the substitution method to derive the characteristic polynomial from the recurrence relation.
- There is a discussion about constructing the general solution using the identified roots and the initial conditions.
- One participant expresses confusion about finding the correct values for parameters in the general solution.
- Another participant suggests a method to simplify the system of equations to solve for the parameters.
- A later reply indicates that a participant realized they were on the right track but had made a minor error in comparison with the professor's answers.
- One participant outlines the closed form of the solution based on the roots and initial conditions, providing a linear combination of the powers of the roots.
Areas of Agreement / Disagreement
Participants generally agree on the process of finding the characteristic equation and its roots, but there is uncertainty regarding the correct values of parameters in the general solution. The discussion includes multiple perspectives on solving the system of equations derived from the initial conditions.
Contextual Notes
Some participants express uncertainty about specific steps in deriving the characteristic polynomial and solving for parameters, indicating potential gaps in understanding or missing assumptions.
- #2
MarkFL
Gold Member
MHB
- 13,284
- 12
Hello and welcome to MHB! :D
Can you identify the characteristic equation and its roots?
Can you identify the characteristic equation and its roots?
- #3
yakin
- 42
- 0
This is all what is given. I have not solved a 3 degree recurrence relation before.
- #4
MarkFL
Gold Member
MHB
- 13,284
- 12
From the linear homogeneous recurrence, you may obtain the characteristic equation:
$$r^3-2r^2-r+2=0$$
Now, you want to factor this to get its 3 roots. What do you find?
$$r^3-2r^2-r+2=0$$
Now, you want to factor this to get its 3 roots. What do you find?
- #5
yakin
- 42
- 0
I found
r=2
r=1
r=-1
But how did you find the characteristic polynomial equation. I tried, but i got stuck we replace a sub n -1 with r sub n-1. I didn't know what to do next? To get the complete characteristic polynomial.
r=2
r=1
r=-1
But how did you find the characteristic polynomial equation. I tried, but i got stuck we replace a sub n -1 with r sub n-1. I didn't know what to do next? To get the complete characteristic polynomial.
- #6
MarkFL
Gold Member
MHB
- 13,284
- 12
Essentially we want to find a solution of the form:
$$a_n=r^n$$
Substituting this solution into the recurrence, we obtain:
$$r^n=2r^{n-1}+r^{n-2}-2r^{n-3}$$
Now, dividing through by $r^{n-3}\ne0$ we obtain:
$$r^3=2r^3+r-2$$
And arranged in standard form, we have:
$$r^3-2r^3-r+2=0$$
Now that you have the characteristic roots, can you state the form of the general solution?
$$a_n=r^n$$
Substituting this solution into the recurrence, we obtain:
$$r^n=2r^{n-1}+r^{n-2}-2r^{n-3}$$
Now, dividing through by $r^{n-3}\ne0$ we obtain:
$$r^3=2r^3+r-2$$
And arranged in standard form, we have:
$$r^3-2r^3-r+2=0$$
Now that you have the characteristic roots, can you state the form of the general solution?
- #7
yakin
- 42
- 0
Got it. Did the roots i find are correct?
- #8
MarkFL
Gold Member
MHB
- 13,284
- 12
yakin said:
Yes, you have the correct roots. So, you want to use these roots to construct the 3-parameter general solution, and then use the given initial values to determine the parameters. You will get a 3X3 linear system of equations to solve.
I've got to run now, (so anyone else is free to jump into answer further questions if they want) but I will be back to check on your progress in roughly 2 hours. :D
- #9
yakin
- 42
- 0
Whatever you explained so far i redid to get better hang of it. I am going to try to find the closed form, because that is what i need to find. I will post here, whatever i would get, please tell me if i got it correct or wrong, if wrong please explain then. Thanks a lot!
- #10
- #11
MarkFL
Gold Member
MHB
- 13,284
- 12
Try adding the first two equations together and the last two equations together to eliminate the third parameter and then you have a 2X2 system. The subtract one of these two equations from the other to eliminate one of the parameters and then you will be able to solve for the other, and then using that you will be able to determine the values of the other two...
- #12
yakin
- 42
- 0
Ok i try that!
P.S: Oops i was doing it right the whole time, but just missed one thing when compared my answers with professors' answers. Thanks for reply though!
P.S: Oops i was doing it right the whole time, but just missed one thing when compared my answers with professors' answers. Thanks for reply though!
Last edited:
- #13
soroban
- 191
- 0
Hello, yakin!
Good work!
The closed form will contain powers of these roots:
. . 2^n,\;1^n,\; (\text{-}1)^n
The closed form is a linear combination of these powers.
. . f(n) \;=\;a(2^n) + b(1^n) + c(\text{-}1)^n
and we must determine a,b,c.We know the first three terms of the sequence.
. . \begin{array}{cccccccc}f(0) = 0\!: & a + b + c &=& 0 & [1] \\ f(1) = 1\!: & 2a + b - c &=& 1 & [2] \\ f(2) = 2\!: & 4a + b + c &=& 2 & [3] \end{array}
Solve the system: .a = \tfrac{2}{3},\;b = \text{-}\tfrac{1}{2},\;c = \text{-}\tfrac{1}{6}Therefore: .f(n) \;=\;\tfrac{2}{3}(2^n) - \tfrac{1}{2}(1^n) - \tfrac{1}{6}(\text{-}1)^n
. . . . . . . . f(n) \;=\;\tfrac{1}{6}\left[4\!\cdot\!2^n - 3 - (\text{-}1)^n\right]
. . . . . . . . f(n) \;=\;\tfrac{1}{6}\left[2^{n+2} - 3 + (\text{-}1)^{n+1}\right]
You found the characteristic equation and its roots: .2,\,1,\,\text{-}1
Good work!
The closed form will contain powers of these roots:
. . 2^n,\;1^n,\; (\text{-}1)^n
The closed form is a linear combination of these powers.
. . f(n) \;=\;a(2^n) + b(1^n) + c(\text{-}1)^n
and we must determine a,b,c.We know the first three terms of the sequence.
. . \begin{array}{cccccccc}f(0) = 0\!: & a + b + c &=& 0 & [1] \\ f(1) = 1\!: & 2a + b - c &=& 1 & [2] \\ f(2) = 2\!: & 4a + b + c &=& 2 & [3] \end{array}
Solve the system: .a = \tfrac{2}{3},\;b = \text{-}\tfrac{1}{2},\;c = \text{-}\tfrac{1}{6}Therefore: .f(n) \;=\;\tfrac{2}{3}(2^n) - \tfrac{1}{2}(1^n) - \tfrac{1}{6}(\text{-}1)^n
. . . . . . . . f(n) \;=\;\tfrac{1}{6}\left[4\!\cdot\!2^n - 3 - (\text{-}1)^n\right]
. . . . . . . . f(n) \;=\;\tfrac{1}{6}\left[2^{n+2} - 3 + (\text{-}1)^{n+1}\right]
Similar threads
- · Replies 18 ·
- · Replies 13 ·
- · Replies 1 ·
- · Replies 4 ·
- · Replies 22 ·
- · Replies 2 ·
- · Replies 5 ·
- · Replies 2 ·
- · Replies 5 ·
- · Replies 5 ·