# How can I solve a forward-backward-looking recurrence system?

I would like to (numerically) solve a forward-backward looking recurrence equation in Mathematica. The system is something like:

x[n+1] = x[n] + y[n]

y[n]   = 2* y[n+1]


subject to

x[0]=1,y[N]=1


The problem is that the boundary of x at the beginning (n=0) where the boundary of y is at the end (n=N) (hence forward-backward looking). The Mathematica command RecurrenceTable does not handle this.

I would need to obtain a result for an arbitrary level of n. Numerical results are fine. What would be the most efficient method to tackle this problem?

-

I must be missing something, this example is easily solved directly:

ClearAll[nn, x, y]
nn = 10
x[n_] := x[n - 1] + y[n - 1]
y[n_] := 2 y[n + 1]
x[0] = 1
y[nn] = 1
Table[{x[i], y[i]}, {i, 0, nn}] // MatrixForm


maybe the real problem is more interesting..?

-

Fairly starightforward approach: Using RSolve[]

RSolve[{x[n + 1] == x[n] + y[n], y[n] == 2*y[n + 1], x[0] == 1,
y[N] == 1}, {x[n], y[n]}, n]


Result:

$\left\{\left\{x(n)\to 2^{-n} \left(2^{n+N+1}+2^n-2^{N+1}\right), y(n)\to 2^{N-n}\right\}\right\}$

As for numerically solving the system: NSolve[]

Still, not an elegant .. erm .. "solution", but a start

NSolve[{x[n + 1] == x[n] + y[n], y[n] == 2*y[n + 1], x[0] == 1,
y[N] == 1}]


$\{\{x(0)\to 1.\, -\text{1.9472683003151566$\grave{ }$*${}^{\wedge}$-174} y(n),x(n)\to 0.517777\, -0.732998 y(n),x(n+1)\to 0.267002 y(n)+0.517777,y(n+1)\to 0.5 y(n),\: y(N)\to 1.\}\}$

-
Thanks!The NSolve solution sounds like the one I need (I am solving a more complex system and I doubt RSolve can help me). How can I convert the answer to numerical solitions in the form: x[0]=1,x[1]=...,x[2]=... etc? – Breugem Aug 23 '13 at 8:45
I think that NSolve is not doing what you think it is doing. It's treating x[n], x[n+1] etc as independent variables and just giving you a random solution to the underdetermined system. – Simon Woods Aug 23 '13 at 14:05

I made a package that deals with the problem. I share it below:

BeginPackage["GlobalSystemSolve"]

GlobalSystemSolve::usage =
"Globally solves a system of equations.
Input = {system,variables,boundaries,N}.
Example:
variables=Function[n,{x[n],y[n]}]
boundaries=Function[N,{x[1]\[Equal]10,y[N]\[Equal]1}]
system=Function[n,{x[n+1]==x[n]+y[n],y[n]==2*y[n+1]}]
N=3"

Begin["Private"]

varlist[variables_,N_]:=Flatten[Table[variables[n],{n,N}]]

globalsystem[system_,boundaries_,N_]:=Flatten[{Table[system[n,N],{n,N-1}],boundaries[N]}]

GlobalSystemSolve[system_,variables_,boundaries_,N_]:=NSolve[globalsystem[system,boundaries,N],varlist[variables,N]]

End[ ]

EndPackage[ ]

-
The brute force approach - I like it :-) By the way, it's not a good idea to use important system functions (such as N) as variable names. – Simon Woods Aug 23 '13 at 14:19
@Simon It seems we agree on most things Mathematica but on this one I take exception. You said variable names and that is true, but Breugem did not use N as a variable. Instead he used it as a pattern name, and it may be confusing to do so I don't believe it will cause any problems. Of course if you use N in the RHS you better mean it to be the argument not the function, but that's up to the programmer to manage. Personally I have taken to using capital letters for pattern names where I feel they are appropriate, though admittedly not N that I can recall. – Mr.Wizard Aug 28 '13 at 10:09
@Mr.Wizard, you're right of course. There's no actual problem with using N` like that (except that it might cause one to receive unwarranted comments on Q&A websites...) – Simon Woods Aug 28 '13 at 11:15