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).

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search