# 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. Dec 25, 2012 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. Dec 25, 2012 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?
– Simd
Dec 25, 2012 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, 2012 at 3:44
• @belisarius I updated the question to fix some problems and clarify the ranges we are interested in.
– Simd
Dec 27, 2012 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.
– Simd
Dec 27, 2012 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, 2012 at 0:21
• Yes that is what I am looking for.
– Simd
Dec 28, 2012 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, 2012 at 18:21
• user141063 Thanks! Shouldn't Rsolve be able to solve it explicitly?
– Simd
Dec 28, 2012 at 21:13