2: Second Order Recurrence Relations

Second Order What?
Second Order Recurrence Relations is a fancy way of saying, if recursive equation meets a specific criteria, it can be reduced to a no recursive equation.

Requirements:

• The nth term depends on the two previous terms
• Constant coefficients with exponents no greater than 1
• Must be homogeneous ( g(n) == 0 )
• General form: S(n) = C₁S( n - 1 ) + C₂S( n - 2 )

Process:

1. Find the roots of t² - C₁t - C₂ = 0
1. r₁ & r₂
2. Solve for p & q
1. S(1) = p + q
2. S(2) = p( r₁ ) + q( r₂ )
3. Plug answers in the solution formula
1. S(n) = p( r₁ )^{n - 1} + q( r₂ )^{n - 1}

Example:

   S(n) = 2S( n - 1 ) + 3S( n - 2 )
   S(1) = 3
   S(2) = 1

1.  t² - 2t - 3 = 0
• r₁ = 3
•  r₂  = -1
2. Solve for p & q
• 3 = q + p
• p( 3 ) + q( -1 ) = 1
• p = 1
• q = 2
3. Substitute
1. S(n) = 1( 3 )^n-1 + 2( -1 )^n-1

Code

• line 10: Love how you can simultaneously assign variables from an array
• Line 36: This isn't a true quadratic formula. It takes advantage of the fact that a == 1in all cases  
• I added a master parse file 
• I love the ||= assignment, this is amazing. It will only assign the variable if it doesn't exist