How to find negative numbers for my recurrence formula?

The generalized recurrence formula is

F[n_]:=F[n]=F[n-1]+F[n-p-1];


with the initial conditions

F[-p-1]=0; F[-p]=1; F[-p+1]=0; ...F[0]=0; F[1]=1; ... F[p+1]=1;.


Note that, for p=1 F[-1]=1;. I want to find positive and negative values according to p. For example, If p=2 then the formula has the form

F[n_]:=F[n]=F[n-1]+F[n-3];


with initial conditions F[0]=0; F[1]=1; F[2]=1; (for positive numbers) and F[0]=0; F[-1]=0; F[-2]=1; (for negative numbers).

I have achieved the calculation of positive numbers but I didn't find numbers for negative n values. Is there any code for the calculation for this process?

Thank you.

• Just to be clear: do you want two separate expressions for F[n], one for positive n and one for negative n? That's the only way I can think of to interpret your question that doesn't overdetermine the recursion relation. (Otherwise you have $p+1$ constants that you're trying to constrain with $2p+3$ equations, and I would worry that the system would be overdetermined.) – Michael Seifert Jan 14 '16 at 15:00
• For example, how to find the numbers for p=2 and the values n={1,2,3,4,5,6,7,8,9,10} and n={-1,-2,-3,-4,-5,-6,-7,-8,-9,-10} ? – drxy Jan 14 '16 at 15:05

One approach is to realize that the recursion for negative indices can be written separately. Here is your forward iteration f and the corresponding backwards iteration b. Just set the initial conditions and you can get any possible values.

Clear[f, b, p];
f[n_, p_] := f[n, p] = f[n - 1, p] + f[n - p - 1, p];
b[m_, p_] := b[m, p] = b[m + p + 1, p] - b[m + p, p];
b[0, p_] = 0;
b[1, p_] = 1;
b[2, p_] = 2;
b[3, p_] = 1;


So for example:

b[-4, 3]
1


or you can apply to a range of elements:

b[#, 3] & /@ Range[-1, -10, -1]
{-1, 1, 1, 1, -2, 0, 0, 3, -2, 0}

• This solved my problem. Thank you @bill s – drxy Jan 14 '16 at 20:19

The function RSolve will give a solution that is valid for both positive and negative values of its argument:

soln[p_] := RSolve[Join[{F[n] == F[n - 1] + F[n - p - 1]}, Table[F[i] == 1, {i, 1, p + 1}]], F[n], n];

soln[2]

(* {{F[n] -> Root[-1 - #1^2 + #1^3 &, 1]^n Root[-1 - 3 #1 + 31 #1^3 &, 1] +
Root[-1 - #1^2 + #1^3 &, 3]^n Root[-1 - 3 #1 + 31 #1^3 &, 2] +
Root[-1 - #1^2 + #1^3 &, 2]^n Root[-1 - 3 #1 + 31 #1^3 &, 3]}} *)


The results are valid for both positive and negative $n$ (assuming, of course, that you're using a self-consistent set of initial conditions.) RSolve gives its results in terms of Root objects, which are cumbersome to deal with if you actually want numerical values; the easiest way to actually get the values of $F(n)$ is, I think, to just numerically evaluate them:

Round[N[Table[Evaluate[F[n] /. First[soln[2]]], {n, -10, 10}]]]

(* {-2, 3, 0, -2, 1, 1, -1, 0, 1, 0, 0, 1, 1, 1, 2, 3, 4, 6, 9, 13, 19} *)

Round[N[Table[Evaluate[F[n] /. First[soln[5]]], {n, -10, 10}]]]

(* {-1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5} *)


That said, this solution takes some time (about 30 seconds for the $p = 5$ case on my machine), so there may be a cleverer way to do it.

• Great solution. Thank you so much ! – drxy Jan 14 '16 at 15:22
• Oh my God ! It's so slow for the higher p values. How can I deal with ? – drxy Jan 14 '16 at 15:25