NetNews Usenet Archive 1992 #16/NN_1992_16.iso/spool/sci/math/9595

Internet Message Format | 1992-07-28 | 5.5 KB

Path: sparky!uunet!sequent!ogicse!usenet.coe.montana.edu!uakari.primate.wisc.edu!sdd.hp.com!mips!darwin.sura.net!jvnc.net!netnews.upenn.edu!netnews.cc.lehigh.edu!ns1.cc.lehigh.edu!fc03
From: [e-mail] (Frederick W. Chapman)
Newsgroups: sci.math
Subject: Re: HELP! Cross-linked series / recursive formulas
Message-ID: <[e-mail]>
Date: 28 Jul 92 15:17:19 GMT
Article-I.D.: ns1.1992Jul28.151719.103466
Organization: Lehigh University
Lines: 140

In article <[e-mail]>, [e-mail]
(Jian Feng) writes:

>Can someone in the net point me to the solution of the following
>problem:
>
>I have two series which are cross-linked:
>
>f(n) = a * f(n-1) + b * g(n-1)
>g(n) = c * f(n-1) + d * g(n-1)
>
>where a != b != c != d
>
>I am after an explicit formula for
>
>Sum [f(k)+g(k)] {k=1,n}.

The problem becomes easy if we recast it in matrix form and apply
techniques from linear algebra.  Form a vector-valued function U(n) from
the unknown functions f(n) and g(n), and form a constant matrix M as
follows:

                        ( f(n) )              ( a   b )
               U(n) :=  (      )        M :=  (       )
                        ( g(n) )              ( c   d )

Now rewrite your system of recurrence relations as a matrix equation:

                          U(n) = M * U(n-1)

Clearly, U(1) = M * U(0), U(2) = M^2 * U(0), U(3) = M^3 * U(0), etc. and in
general,
                                  n
                          U(n) = M  * U(0).

The problem now becomes one of finding a closed form expression for the
powers of the matrix M.  This is easily done if we first find the Jordan
canonical form for M.  There is a non-singular matrix K (of generalized
eigenvectors) such that M = K * J * K^(-1), where J is the Jordan canonical
form of M.  Since M is 2 x 2, J is either a diagonal matrix

                                ( lambda     0 )
                                (       1      )
                          D  =  (              )
                                ( 0   lambda   )
                                (           2  )

or a matrix of the form

                           lambda I  +  N

where I is the 2 x 2 (multiplicative) identity matrix and N is the
following nilpotent matrix of order 2:

                                ( 0   1 )
                          N :=  (       )
                                ( 0   0 )

(The lambda's are the eigenvalues of M.)  Powers of M are easy to compute
in this form, since

                   k              -1 k         k    -1
                  M  =  (K * J * K  )  =  K * J  * K

Thus, we need only compute powers of J.  If J is the diagonal matrix D,
this is trivial:

                                         k
                                ( lambda     0 )
                           k    (       1      )
                          D  =  (            k )
                                ( 0   lambda   )
                                (           2  )


If J is of the second form, it is not much harder:

                             k          k               k-1
             (lambda I  +  N)  =  lambda  I  +  k lambda    N

which results from taking the first two terms of the binomial expansion.
(The powers of N from N^2 on vanish since N is nilpotent of order 2.)

I suggest determining a closed-form expression for

                          n            n    k
                         SUM U(k)  =  SUM  M  * U(0)
                         k=0          k=0

                                       n        k   -1
                                   =  SUM  K * J * K  * U(0)
                                      k=0

                                           n   k    -1
                                   =  K * SUM J  * K  * U(0)
                                          k=0

and then adding the two components of the resulting vector expression to
get the sought-after sum (but starting at k=0 instead of k=1; make
adjustments as desired).  Thus, we need only find a closed-form expression
for

                                      n   k
                                     SUM J
                                     k=0

which involves the sum of two finite geometric series (in the lambda_i's)
in the case that J is the diagonal matrix D; in the case that J is of the
form

                                lambda I + N,

we get a sum of a finite geometric series (in lambda), and the derivative
of the sum of a finite geometric series (in lambda).  Apply the formulas

                                     n+1
                           n   k    r    -   1
                          SUM r  =  ----------
                          k=0         r  -  1


                             n+1              n+1          n
           n     k-1     d  r    -   1     n r    - (n+1) r  + 1
          SUM k r    =  --  ----------  =  ---------------------
          k=0           dr   r  -  1                     2
                                                  (r - 1)

(For an eigenvalue of 1, the formulas are not applicable, but the sums are
simple enough to compute by other means.)


                   Viola!  er, I mean...  Voila!  :-)

--

o ------------------------------------------------------------------------- o
|  Frederick W. Chapman, User Services, Computing Center, Lehigh University |
|    Campus Phone:  8-3218     Preferred E-mail Address:  [e-mail]   |
|  "I do comedy and magic; what you don't find funny -- that's the magic."  |
o ------------------------------------------------------------------------- o