Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Second Order Recurrence with Non-Constant Coefficients

Date: 05/27/2005 at 15:47:18
From: Bassam
Subject: second order recurrence with non constant coefficient

Hello.  I ran into this second order recurrence relation with no 
constant coefficients and I was wondering what would be the best way 
to get a closed form solution in terms of the initial values u(0) 
and u(1). 

  u(n+2) = 2*(2*n+3)^2 * u(n+1) - 4*(n+1)^2*(2*n+1)*(2*n+3)*u(n)

What I find most difficult is the presence of non-constant 
coefficients in the recurrence relation.  Had it been involving only 
constant coefficients things would have been much easier to solve.

I tried noticing a certain repeating pattern but that is very hard 
to detect.  I was thinking of finding an equivalent second order 
differential equation whose series expansion would yield the required 
recurrence relation but that also didn't lead to anywhere interesting.

I am interested in getting a closed form solution for this recurrence.
Any help would be highly appreciated.

Thanks!



Date: 05/27/2005 at 22:01:07
From: Doctor Vogler
Subject: Re: second order recurrence with non constant coefficient

Hi Bassam,

Thanks for writing to Dr. Math.  Unfortunately, recurrence relations
are very much like sums in that MOST of them cannot be solved in 
closed form.  That is, most of them can't be solved with a nice, neat,
simple formula.  But some of them can.  For both sums and recurrences,
there are those that have nice forms (like geometric sums and linear
recurrences) which can be solved by very straight-forward techniques.
And then there are a few special ones (like the sum of 1/n^2, or your
recurrence) that can be solved with enough effort.

Fortunately for you, yours is solvable.  But I didn't know this at
first.  In any case, you might as well try.  How do you try to solve a
recurrence relation?  Well, as with sums, there are various 
techniques, and not all of them work all of the time.  But let's see
what we can do.

So the first thing I noticed was that both terms in your recurrence
are divisible by 2n+3.  So let's suppose that u(0) and u(1) are 
integers.  Then all u(n)'s will also be integers.  And u(n+2) will
always be divisible by 2n+3.  That means (replacing n by n-2) that 
u(n) will always be divisible by 2n-1.

Great!  We're getting somewhere!  Now 2n+1 divides the second term,
but 2n+1 divides u(n+1), which means it also divides the first term! 
So 2n+1 also divides u(n+2), and therefore 2n-3 divides u(n).  You can
continue in this way and show that 2n-5 divides u(n), and 2n-7, and so on.

So then we recall a definition

  n!! = n*(n-2)*(n-4)*(n-6)*...*u

where u is either 1 or 2, according to whether n is odd or even.  Then
we divide the whole equation by (2n+3)!! and set

  a(n) = u(n)/(2n-1)!!.

Then the recurrence becomes

  a(n+2) = (2n+3)*a(n+1) - (n+1)^2*a(n).

Even better!  Now we have reduced the degree of the coefficients by 1
and 2, respectively.  Can we do more?  Well, we can try to show that
these a(n)'s are divisible by some similar factorial, but it's just
not always true.  Nevertheless, they do grow about as fast as a
factorial.  We might try dividing by a polynomial in n, or something
like that, but it won't reduce the degree of those coefficients; we
need factorials for that.

So what happens if we take a leap of faith?  We really want to reduce
the degree of those coefficients, so let's divide by a full factorial:
Let's divide the original equation by (2n+3)! and set

  b(n) = u(n)/(2n-1)!.

Then the recurrence becomes

             2n+3            n+1
  b(n+2) = 2(----)*b(n+1) - (---)*b(n).
             2n+2             n

So the cost of our leap of faith is fractions.  But you might notice
that those fractions are *nearly* one, and so our recurrence is *almost*

  b(n+2) = 2b(n+1) - b(n),

which is an easy recurrence to solve.  In fact, its solutions are

  b(n) = C*n + D.

Unfortunately, that *almost* means that this is not quite correct. 
But what happens if we subtract off the nice part and put that on the
left side of the equation?

                            b(n+1)   b(n)
  b(n+2) - 2b(n+1) + b(n) = ------ - ----.
                              n+1      n

Well, that's not too bad.  It has some nice symmetry going on, 
especially with the denominators on the right matching the indices. 
For example, we might suspect that we could get one solution by 
supposing that both sides of the equation are zero.  On the right,
that would mean b(n)/n is constant, and that also solves the left side
too!  But we can do better!  In fact, the left side is a difference of
differences

  [b(n+2) - b(n+1)] - [b(n+1) - b(n)],

and the right side is also a difference.  So let's pair up the 
differences!

                    b(n+1)                   b(n)
  b(n+2) - b(n+1) - ------ = b(n+1) - b(n) - ----.
                      n+1                      n

That means that the sequence

                         b(n)
  c(n) = b(n+1) - b(n) - ----
                           n

is constant!  So let's write

                  b(n)
  b(n+1) - b(n) - ---- = K
                    n

and then solve

                n+1
  b(n+1) = K + (---)*b(n).
                 n

If we take K = 0, then that is the solution I mentioned previously. 
Otherwise, we start substituting

               n
  b(n) = K + (---)*b(n-1).
              n-1

               n        n-1
       = K + (---)*[K + ---*b(n-2)]
              n-1       n-2

              n       n            n     n
       = K + ---*K + ---*K + ... + -*K + -*b(1).
             n-1     n-2           2     1

Ultimately, this is our answer.  We notice that we might have gotten a
simpler answer by considering b(n)/n, or half of that which is

  v(n) = u(n)/(2n)!,

and that would have changed our recurrence (after some simplifying and
rewriting) to

                    n+1
  v(n+2) - v(n+1) = ---*(v(n+1) - v(n))
                    n+2

and therefore

  v(n) - v(n-1) = M*1/n

for some constant M, and

          n   M
  v(n) = sum --- + v(0).
         i=1  i

In either case, we find that the general solution to your recurrence
relation is

            n  (2n)!
  u(n) = C sum -----  +  D * (2n)!
           i=1   i

for constants C and D.  (Of course, you could start the sum at some
other value by changing the constant D; so the 1 is sort of 
arbitrary.)  You can also write expressions for C and D in terms of
the initial conditions u(0) and u(1).

If you have any questions about this or need more help, please write
back and show me what you have been able to do, and I will try to 
offer further suggestions.

- Doctor Vogler, The Math Forum
  http://mathforum.org/dr.math/ 
Associated Topics:
College Number Theory
High School Number Theory
High School Sequences, Series

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/