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

	# PROJECT: Second Order Recurrence Relations
	$LOAD_PATH << '../lib'
	require 'parseFile.rb'
	class Sorr
	def initialize(inputs)
	s1 = inputs["S(1)"]; s2 = inputs["S(2)"]
	c1 = inputs['C1']; c2 = inputs['C2']
	r1,r2 = quadratic(c1,c2)
	puts "r1 = #{r1}"
	puts "r2 = #{r2}"
	unless r1 == r2
	q = ((s2 - (s1 * r1) ) / ( ( -r1 ) + r2 ))
	p = s1 - q
	puts "p = #{p}"
	puts "q = #{q}"
	puts "S(n) = (#{p})(#{r1})^(n-1) + (#{q})(#{r2})^(n-1)"
	for i in 1..10 do
	puts "S(#{i}) = #{(p*r1**(i-1) + q*r2**(i-1))}"
	end
	else
	p = s1
	q = ( s2 - p*r1 ) / r1
	puts "p = #{p}"
	puts "q = #{q}"
	puts "S(n) = #{r1}^(n-1) + #{q}(n-1)*#{r1}^(n-1)"
	for i in 1..10 do
	puts "S(#{i}) = #{r1**(i-1) + q*(i-1)*r1**(i-1)}"
	end
	end #unless
	end #initialize
	def quadratic(b,c)
	[ ( b + Math.sqrt(b**2 + 4 * c) ) / 2,
	( b - Math.sqrt(b**2 + 4 * c) ) / 2 ]
	end #quadratic
	end #class Sorr
	begin
	parsed = Master::ParseFile.new(Hash)
	if parsed.getFile.instance_of?(Hash) then Sorr.new(parsed.getFile) end
	end

view raw SORR.rb hosted with ❤ by GitHub