There is a generic formula Z^N = A(Z)^N+1 + B(Z)^N+1 . This formula is used to convert a given recursive function back to its original explicit form :
Recursive Formulas :
1) R(0) = 1, R(n) = (1/3) R(n-1), n = 1, 2, ...
2) P(0) = 1, P(1) = 1/3, P(n) = (4/3) P(n-1) - (1/3) P(n-2), n = 2, 3, ...
3) Q(0) = 1, Q(1) = 1/3, Q(n) = (10/3) Q(n-1) - Q(n-2), n = 2, 3, ...
Then, it suggests that "difference formulas" of the form :
2) P(n) = A(1/3^n) + B
3) Q(n) = A(1/3^n) + B * 3^n
represent the general solution.
Then the "difference functions" are to be substituted into the "recursive functions" to obtain root of A, B which completes the proof that the recursive function is indeed a representation of the original sequence {Xn} = {1/3^n} = 1, 1/3, 1/9, ...
My Question is where the difference formulas come from? I would appreciate a reference to the subject in any major text-book in calculus or numerical methods like Swokowski, Fink, or Chapra.
It's just a bit of freshman algebra. Let's take example 3 for instance:
Q(n+2) = (10/3)Q(n+1) + (-1)Q(n)
Q(n+1) = ( 1)Q(n+1) + ( 0)Q(n)
That second equation seems silly, but it allows us to write the following matrix equation:
[ Q(n+2) ] = [ 10/3 -1 ][ Q(n+1) ]
[ Q(n+1) ] = [ 1 0 ][ Q(n) ]
This is the 2-dimensional analogue of a recurrence like v(n+1) = a*v(n) which has an easy solution v(n) = a^n * v(0). We can apply the same logic to our matrix equation to obtain:
[ Q(n+1) ] = [ 10/3 -1 ]^n [ 1/3 ]
[ Q(n) ] = [ 1 0 ] [ 1 ]
Let's call that 2 x 2 matrix in the middle that we're raising to the nth power, A.Now how do we quickly compute powers of square matrices? When they're diagonalizable, it's easy. The eigenvalues of that 2x2 matrix are the roots of its characteristic polynomial:
det(A - xI) = (10/3 - x)(0 - x) - (1)(-1) = (x - 1/3)(x - 3)
This tells us that there's some invertible 2 x 2 matrix P (consisting of the eigenvectors of A) such that:
[ Q(n+1) ] = P [ 1/3 0 ]^n P^-1 [ 1/3 ]
[ Q(n) ] = [ 0 3 ] [ 1 ]
and so:
[ Q(n+1) ] = P [ 1/3^n 0 ] P^-1 [ 1/3 ]
[ Q(n) ] = [ 0 3^n ] [ 1 ]
From this we easily deduce that for some constants a and b:
Q(n) = a(1/3^n) + b(3^n)
We could explicitly figure out what they are by finding the eigenvectors of A, constructing the matrices P and P^-1, multiplying those three 2 x 2 matrices with the 2 x 1 vector on the right, and actually extracting the expression for Q(n) from that. But it's easier to just look at the equation, realize that it'll result in something of the form Q(n) = a(1/3^n) + b(3^n) and actually just solve for a and b via back-substitution.