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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.