# Solve pair of recurrence relations

[Corrected equations and added simple example]

Can you solve a system of (loosely) coupled recurrence relations like this in Mathematica somehow?

{A[k] ==1+((n-k-2)/n) A[k+1] +(2/n) B[k+1] + (k/n) (A),
B[k]==1+((n-k-1)/n) B[k+1] + (k/n) A}


We want to solve it for $A$ as a closed form function of $n$.

$A[k]$ is defined for $0 \leq k \leq n-2$ and $B[k]$ is defined for $1 \leq k \leq n-1$.

Version 8 doesn't do anything useful but I suspect I am not asking it in the right way.

As a simple example, if you set $n=3$ then you get four simulataneous equations.

A == 1 + (2/3)*B + (1/3)*A
B == 1 + (1/3)*A + (1/3)*B
B == 1 + (2/3)*A
A == 1 + (2/3)*B + (1/3)*A


Solving for $A$ gives you $33/5$ I believe. To start things off, how do you get Mathematica to do this?

Update. If you just take the second recurrence alone.

B[k]==1+((n-k-1)/n) B[k+1] + (k/n) A


How can you get Mathematica to give a sensible solution for $B[k]$ in terms of $n$ and $A$? It seems Rsolve ought to be able to do this. I even tried

RSolve[{B[k] == 1 + ((n - k - 1)/n) B[k + 1] + ((k)/n) (A),
B[n - 1] == k A/n}, B[k], k]


which should be identical. However this now gives an empty solution with the following warning.

RSolve::bvnul: For some branches of the general solution, the given boundary conditions lead to an empty solution.


I would like to tell Mathematica to only try to solve it for the defined range of $k$. Is that possible?

• If replace A with constant and solve first for B[k] then solve for A[k] and replace B[k] with previous solution it works. – swish Dec 25 '12 at 13:49
• Please note that the second one isn't really "coupled" with the first but for a constant term A. So RSolve[B[k]==1+((n-k-2)/n) B[k+1]+((k+1)/n) (k+A),B[k],k] is able to cope with it. – Dr. belisarius Dec 25 '12 at 15:53
• I get a horrible expression from RSolve[B[k]==1+((n-k-2)/n) B[k+1]+((k+1)/n) (k+A),B[k],k] in terms of Gamma, DifferenceRoot, some Function and Pochhammer. Is there some way to extract the leading terms? – lip1 Dec 25 '12 at 20:54
• @lip1 If by "extract the leading terms" you mean generate the first few terms in the sequence, RecurrenceTable is what you are looking for. Unless you can set the value of n though, you get very long expressions. – 0xFE Dec 26 '12 at 3:44
• @belisarius I updated the question to fix some problems and clarify the ranges we are interested in. – lip1 Dec 27 '12 at 17:36

There may be a better way, but this solves it the same way you did. It generates all the equations and then solves them. If you only want $A_0$, use Sol[n][[1,1]].

Sol[n_] :=
Solve[Take[
Flatten[Table[{Subscript[B, k] ==
1 + ((n - k - 1) Subscript[B, k + 1])/n + (k Subscript[A, 0])/
n, Subscript[A, k] ==
1 + ((n - k - 2) Subscript[A, k + 1])/n + (
2 Subscript[B, k + 1])/n + (k Subscript[A, 0])/n}, {k, 0,
n - 1}]], {2, -2}]]


Edit:

Here's a graph of the first 80 values: And the first set of differences: That looks somewhere between $\sqrt{x}$ and $\log{x}$.

• Thanks. What I am looking for is a solution as a function of $n$. I just gave an example to make sure it was clear what was going on. I was hoping Rsolve might be able to do something useful. – lip1 Dec 27 '12 at 22:27
• @lip1 This is a function of n in the Mathematica sense. Do you mean a mathematical function, like a closed form expression? – 0xFE Dec 28 '12 at 0:21
• Yes that is what I am looking for. – lip1 Dec 28 '12 at 7:21
• I've tried fitting some models to it and I have gotten very close, but I haven't found a closed form function. – 0xFE Dec 28 '12 at 18:21
• user141063 Thanks! Shouldn't Rsolve be able to solve it explicitly? – lip1 Dec 28 '12 at 21:13