0
$\begingroup$

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.

Improve this question
$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – Michael Seifert Jan 14 '16 at 15:00
  • $\begingroup$ 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} ? $\endgroup$ – drxy Jan 14 '16 at 15:05
3
$\begingroup$

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}
Improve this answer
$\endgroup$
  • $\begingroup$ This solved my problem. Thank you @bill s $\endgroup$ – drxy Jan 14 '16 at 20:19
3
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.