========================================================================
Subject:  Recurrence Relation Solution
========================================================================

Here is the problem that I presented at the end of Monday's lecture
(11/23/09):
========================================================================

Find the "explicit" solution of this recurrence relation:

	a_n = 2a_(n-1) + 3a_(n-2)

[i.e., a_n = c1*a_(n-1) + c2*a_(n-1), where c1 = 2 & c2 = 3]

with these initial conditions:

	a0 = 4
	a1 = 5

[i.e., where C0 = 4 and C1 = 5, using the textbook's notation]
------------------------------------------------------------------------
This generates the following sequence:

	4, 5, 22, 59, ...
------------------------------------------------------------------------
To find its explicit solution--i.e., a formula for the nth term of the
sequence that is computed from input n instead of from previous outputs
a_(n-1) and a_(n-2)--do the following:

1.
Find the recurrence relation's characteristic equation,
which is of the form:

	r^2 - c1*r - c2 = 0

i.e.,   r^2 - 2r - 3 = 0
------------------------------------------------------------------------
2.
Solve this equation to find the characteristic roots r1 and r2:

	Digression:  You can either use the quadratic formula
	or factor the equation.  Factoring gives (r-3)(r+1)=0,
	so r1 = 3 and r2 = -1.  The quadratic formula gives
	the same answer, of course:

	r1 = [-(-2) + sqrt( (-2)^2 - 4*1*(-3)]/2*1
	   = [2 + sqrt(4 + 12)]/2
	   = [2 + sqrt(16)]/2
	   = (2 + 4)/2
	   = 3

	r2 = [-(-2) - sqrt( (-2)^2 - 4*1*(-3)]/2*1
           = [2 - sqrt(4 + 12)]/2
           = [2 - sqrt(16)]/2
           = (2 - 4)/2
	   = -1
	End of digression

So:  r1 = 3 and r2 = -1
------------------------------------------------------------------------
3.
Find alpha1 and alpha2 such that a_n = alpha1*r1^n + alpha2*r2^n:

Do this by using the initial conditions to produce 2 simultaneous
equations in 2 unknowns:

a0 = 4 = alpha1*3^0 + alpha2*(-1)^0
a1 = 5 = alpha1*3^1 + alpha2*(-1)^1

These simplify to:

4 =   alpha1 + alpha2
5 = 3*alpha1 - alpha2

From the first one, we get alpha2 = 4 - alpha1
From the second, we get    alpha2 = 3*alpha1 - 5

Setting the two right-hand sides equal to each other, we get:

4 - alpha1 = 3*alpha1 - 5

Therefore, 9 = 4*alpha1
Therefore, alpha1 = 9/4
Therefore, alpha2 = 4 - 9/4 = 7/4
------------------------------------------------------------------------
Output the explicit formula for a_n, namely

	a_n = alpha1*r1^n + alpha2*r2^n
i.e.,   a_n = (9/4) *3^n  + (7/4) *(-1)^n
========================================================================

We can check this by computing a0, a1, a2, etc.:

a0 = (9/4)*3^0 + (7/4)*(-1)^0 = 9/4  + 7/4 = 4,	which is correct
				   (i.e., it matches the given sequence)

a1 = (9/4)*3^1 + (7/4)*(-1)^1 = 27/4 - 7/4 = 5, which is correct

a2 = (9/4)*3^2 + (7/4)*(-1)^2 = 81/4 + 7/4 = 22, which is correct, etc.

(Try computing a3 to see if it comes out to 59.)
(Then compute a4 both recursively and explicitly to see if they match.)