# \[Math\] Closed form from a recursion relation? **URL:** \ **Category:** Factual Questions\ **Created:** [November 27, 2012, 1:18am UTC](https://boards.straightdope.com/t/math-closed-form-from-a-recursion-relation/642225 "2012-11-27T01:18:52Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [November 27, 2012, 1:18am UTC](https://boards.straightdope.com/t/math-closed-form-from-a-recursion-relation/642225/1 "2012-11-27T01:18:52Z")
I have a mathematical function of two variables that I’m studying. At present, I have this function as a recursion relation: I know the values for certain low values of the independent variables, and I can relate the value of the function for high inputs to its value for lower inputs. This is enough to always evaluate the function, but I could do much more if I could express it directly. Is there any general method for constructing such a representation from the recursion relations? If it matters, the relations I have are: a, b nonnegative integers; P(a,b) rational If a \< b, P(a,b) = 0 If b = 0, P(a,b) = 1 If b = 1, P(a,b) = a/(a+1) P(a-2,1) + 1/(a+1) Otherwise, P(a,b) = a/(a+b) P(a-2,b) + b/(a+b) P(a-1,b-1) (a virtual cookie to anyone who recognizes what problem this is from) ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [November 27, 2012, 2:32am UTC](https://boards.straightdope.com/t/math-closed-form-from-a-recursion-relation/642225/2 "2012-11-27T02:32:05Z")
What’s the value of P(1, 1)? I think you need to expand your base cases slightly. ---
**Author:** ![Jragon](https://avatars.discourse-cdn.com/v4/letter/j/e19b73/32.png) [@Jragon](https://boards.straightdope.com/u/Jragon)\ **Post date:** [November 27, 2012, 2:40am UTC](https://boards.straightdope.com/t/math-closed-form-from-a-recursion-relation/642225/3 "2012-11-27T02:40:22Z")
Yeah, if b=1, then a must be even in your cases. I’m not sure if that’s intentional. ETA: Also, if b\>1 and a\>b, then a must be odd if b is even, and vice versa. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [November 27, 2012, 2:42am UTC](https://boards.straightdope.com/t/math-closed-form-from-a-recursion-relation/642225/4 "2012-11-27T02:42:22Z")
Ah, yes, I suppose that does fall afoul of my statement that a is nonnegative. To be clear, I only care about the values of P for both positive, but P(-1,1) = 0, since a \< b. In other words, P(1,1) = 1/2. EDIT: I’d really prefer a general method for such problems, anyway, rather than focusing on the specific problem I have before me right now. I was waffling about whether to include the actual problem, and only did so to forestall questions. ---
**Author:** ![Jragon](https://avatars.discourse-cdn.com/v4/letter/j/e19b73/32.png) [@Jragon](https://boards.straightdope.com/u/Jragon)\ **Post date:** [November 27, 2012, 2:49am UTC](https://boards.straightdope.com/t/math-closed-form-from-a-recursion-relation/642225/5 "2012-11-27T02:49:59Z")
I don’t think there’s a general algorithm for doing it, but tricks I tend to use when I have to do it is abusing things like ceilings, floors, and mods. For instance, a\ P(a,b)= 0 is the same assertion as floor(a/b)=0. That might not end up being useful, but those functions are usually where I start. ETA: I mean the assertion is the same for your domain (excluding the negative case). ---
**Author:** ![Jragon](https://avatars.discourse-cdn.com/v4/letter/j/e19b73/32.png) [@Jragon](https://boards.straightdope.com/u/Jragon)\ **Post date:** [November 27, 2012, 3:22am UTC](https://boards.straightdope.com/t/math-closed-form-from-a-recursion-relation/642225/6 "2012-11-27T03:22:08Z")
Actually, now I remember, there is an algorithm for this. It’s been so long I’d forgotten. It’s mostly used for analyzing what the big O of a recursive algorithm is, but it works for this too. The general idea is plugging in and pattern matching. The minus is that for something like this with so many catches it’ll give you a nasty piecewise function. It does take a bit of creativity sometimes. Let’s take the case when b=1 What’s a/(a+1)P(a-2,1)+1/(a+1)? Well, that’s just a/(a+1)((a-2)/(a-1)P(a-4,1)+1/(a-1))+1/(a+1) Essentially, just keep plugging in P(a-2n,1) until you get the point of what the pattern is. Do this for two or three iterations, until you’re sure of the pattern, and then put in a big ol’ […] P(0,1). In this case, I think you’re going to have to split the b=1 case into b=1 and a%2=0 and b=1 and a%2=1, but the functions should come out almost the same, it’s just the terminating case that’s different. Then it’s just a matter of condensing the function with summations, Big Pis, etc. I can tell already that the a\>=b\>1 case is going to get REALLY gnarly, I’ve never had to do this with two recursive variables, good luck. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [November 27, 2012, 3:55am UTC](https://boards.straightdope.com/t/math-closed-form-from-a-recursion-relation/642225/7 "2012-11-27T03:55:51Z")
The methods out there are for single variable recurrences. I don’t know of any general tricks for multivariate ones. You might be able to do something with generating functions, but there’s no guarantee that you’ll get anything nice. ---
**Author:** ![Jragon](https://avatars.discourse-cdn.com/v4/letter/j/e19b73/32.png) [@Jragon](https://boards.straightdope.com/u/Jragon)\ **Post date:** [November 27, 2012, 4:02am UTC](https://boards.straightdope.com/t/math-closed-form-from-a-recursion-relation/642225/8 "2012-11-27T04:02:17Z")
> [@ultrafilter](#): > > The methods out there are for single variable recurrences. I don’t know of any general tricks for multivariate ones. You might be able to do something with generating functions, but there’s no guarantee that you’ll get anything nice. The main problem in this scenario is the P(a-2,b) in the “otherwise” function. If it was just P(a-1,b-1) it would be easy since it clearly will eventually hit the b=1 case. But yeah, in general the multivariate is going to range from hard to impossible. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [November 27, 2012, 4:30am UTC](https://boards.straightdope.com/t/math-closed-form-from-a-recursion-relation/642225/9 "2012-11-27T04:30:27Z")
> [@](#): > > Quoth **ultrafilter** : > > The methods out there are for single variable recurrences. I don’t know of any general tricks for multivariate ones. You might be able to do something with generating functions, but there’s no guarantee that you’ll get anything nice. Hm, that’s unfortunate. But it’s good to know; that probably means I shouldn’t waste too much time trying to find a closed-form solution, and just make do with what I have. > [@](#): > > Quoth **Jragon** : > > In this case, I think you’re going to have to split the b=1 case into b=1 and a%2=0 and b=1 and a%2=1, but the functions should come out almost the same, it’s just the terminating case that’s different. I noticed a while ago that it makes a big difference whether a+b is even or odd: The values of P are significantly higher for even a+b than for neighboring odd points. ---
**Author:** ![Jragon](https://avatars.discourse-cdn.com/v4/letter/j/e19b73/32.png) [@Jragon](https://boards.straightdope.com/u/Jragon)\ **Post date:** [November 27, 2012, 4:35am UTC](https://boards.straightdope.com/t/math-closed-form-from-a-recursion-relation/642225/10 "2012-11-27T04:35:25Z")
FWIW, in the case where a is even and b=1, the recurrence relation reduces to this equation (it works for the a=6 test case, I can’t assure you it always works, though, it was pretty quick and dirty): [http://1.618034.com/blog\_data/math/formula.22647.png](http://1.618034.com/blog_data/math/formula.22647.png) ---
**Author:** ![Jragon](https://avatars.discourse-cdn.com/v4/letter/j/e19b73/32.png) [@Jragon](https://boards.straightdope.com/u/Jragon)\ **Post date:** [November 27, 2012, 4:42am UTC](https://boards.straightdope.com/t/math-closed-form-from-a-recursion-relation/642225/11 "2012-11-27T04:42:31Z")
> [@Jragon](#): > > equation … expression. I meant to put P(a,1)= in that, but I guess it’s an expression now. Also, those 6’s should be a’s. ---
**Author:** ![Jragon](https://avatars.discourse-cdn.com/v4/letter/j/e19b73/32.png) [@Jragon](https://boards.straightdope.com/u/Jragon)\ **Post date:** [November 27, 2012, 4:49am UTC](https://boards.straightdope.com/t/math-closed-form-from-a-recursion-relation/642225/12 "2012-11-27T04:49:55Z")
Like so (still didn’t put P(a,1)= in…): [http://1.618034.com/blog\_data/math/formula.22649.png](http://1.618034.com/blog_data/math/formula.22649.png) ---
**Author:** ![Jragon](https://avatars.discourse-cdn.com/v4/letter/j/e19b73/32.png) [@Jragon](https://boards.straightdope.com/u/Jragon)\ **Post date:** [November 27, 2012, 5:21am UTC](https://boards.straightdope.com/t/math-closed-form-from-a-recursion-relation/642225/13 "2012-11-27T05:21:30Z")
And here’s the whole equation, for evens and odds. Turns out all that happens is you need to ceil a/2 (catch case is a=1, when k goes from 1 to 0, just assume the sum goes away). [http://1.618034.com/blog\_data/math/formula.22663.png](http://1.618034.com/blog_data/math/formula.22663.png) ---
**Author:** ![Jragon](https://avatars.discourse-cdn.com/v4/letter/j/e19b73/32.png) [@Jragon](https://boards.straightdope.com/u/Jragon)\ **Post date:** [November 27, 2012, 5:27am UTC](https://boards.straightdope.com/t/math-closed-form-from-a-recursion-relation/642225/14 "2012-11-27T05:27:35Z")
Messed it up again… _sigh_. Ceil should be around the whole fraction. [http://1.618034.com/blog\_data/math/formula.22665.png](http://1.618034.com/blog_data/math/formula.22665.png) ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [November 27, 2012, 5:56am UTC](https://boards.straightdope.com/t/math-closed-form-from-a-recursion-relation/642225/15 "2012-11-27T05:56:07Z")
> [@Chronos](#): > > (a virtual cookie to anyone who recognizes what problem this is from) Mafia. P(a, b) is the probability that the non-Mafia players win if they kill people at uniform random each turn, starting from a non-Mafia players and b Mafia players. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [November 27, 2012, 6:11am UTC](https://boards.straightdope.com/t/math-closed-form-from-a-recursion-relation/642225/16 "2012-11-27T06:11:14Z")
(Which brings us to [this paper](http://arxiv.org/pdf/1009.1031v2.pdf), which considers essentially the same problem) ---
**Author:** ![Jragon](https://avatars.discourse-cdn.com/v4/letter/j/e19b73/32.png) [@Jragon](https://boards.straightdope.com/u/Jragon)\ **Post date:** [November 27, 2012, 6:28am UTC](https://boards.straightdope.com/t/math-closed-form-from-a-recursion-relation/642225/17 "2012-11-27T06:28:43Z")
> [@Indistinguishable](#): > > (Which brings us to [this paper](http://arxiv.org/pdf/1009.1031v2.pdf), which considers essentially the same problem) Wow, either I was **way** off or there are correct solutions for the P(a,1) case that look incredibly different. I think it might be the latter since mine seems to give the right answer when I test it, but I could have easily messed up somewhere. ETA: Oh, I think I just got a really wordy alternate form of (a-1)!!/a!! ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [November 27, 2012, 6:42am UTC](https://boards.straightdope.com/t/math-closed-form-from-a-recursion-relation/642225/18 "2012-11-27T06:42:59Z")
Do also keep in mind that the paper’s w = 1 - Chronos’s P, with n = a + b and m = b. So, your P(a, 1) should come out to 1 - a!!/(a + 1)!!. ---
**Author:** ![Derleth](https://avatars.discourse-cdn.com/v4/letter/d/b9e5f3/32.png) [@Derleth](https://boards.straightdope.com/u/Derleth)\ **Post date:** [November 27, 2012, 7:06am UTC](https://boards.straightdope.com/t/math-closed-form-from-a-recursion-relation/642225/19 "2012-11-27T07:06:04Z")
> [@Indistinguishable](#): > > 1 - a!!/(a + 1)!!. Is that a double factorial in your formula or are you just excited to see me? Up until this instant, I’d never heard of a double factorial, but [apparently, they’re the product of all positive integers less than or equal to n with the same parity as n](http://mathworld.wolfram.com/DoubleFactorial.html); that is, if n is even, it’s the product of all evens less than or equal to n; if n is odd, it’s all the odds. [Wikipedia has even more information, on up to the quadruple factorial, the superfactorial, and the hyperfactorial.](http://en.wikipedia.org/wiki/Factorial) [Super-_duper_-superfactorial!](http://www.youtube.com/watch?v=dZlFBSRrSR0) ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [November 28, 2012, 12:18am UTC](https://boards.straightdope.com/t/math-closed-form-from-a-recursion-relation/642225/20 "2012-11-28T00:18:06Z")
> [@Indistinguishable](#): > > (Which brings us to [this paper](http://arxiv.org/pdf/1009.1031v2.pdf), which considers essentially the same problem) Huh, I was completely unaware of the existence of this paper. Thanks! As it happens, my plan is to eventually incorporate more complicated roles, so that doesn’t supercede my work, but it should certainly be useful for understanding the simple case. Oh, and have a cookie. [Next page](https://boards.straightdope.com/t/math-closed-form-from-a-recursion-relation/642225.md?page=2)