       Re: Code required for recurrence relations

• To: mathgroup at smc.vnet.net
• Subject: [mg90277] Re: [mg90235] Code required for recurrence relations
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Fri, 4 Jul 2008 03:58:05 -0400 (EDT)
• References: <200807031010.GAA03077@smc.vnet.net>

```Ant King wrote:
> Hi all
>
> I am running v. 6.03 and would like to know if anyone is aware of any code
> (or has a function) that will perform the following task
>
> Take a generating function, such as 2*x/(1-x)^2, and use it to extract the
> recurrence relation from whence it came - in this case it just generates the
> even numbers
>
> So the function will be something like f[2*x/(1-x)^2,u,n] and would output
> something like u[n]->u[n-1]+2
>
> Many thanks
>
> Ant

If it satisfies a linear recurrence with constant coefficients, one can
generally find it by looking for relations between consecutuve sets of
coefficients. The code below will do this.

findLinearRecurrence[vals_List, func_, n_] := Module[
{v2=Reverse[vals], nulls={}, res, j=0},
While[nulls=={},
j++;
nulls = NullSpace[Map[Append[#,1]&,
Partition[v2,j,1]]];
If [Length[nulls]>0,
res = First[nulls];
res = -Rest[res] / First[res];
Return[func[n] == res .
Append[Map[func[n-#]&, Range[Length[res]-1]],1]]
];
];
]

u[n_] := 2*n/(1-n)^2

Let's get a bunch of the values (the coefficients of the series given by
the generating function u[n]).

In:= coeffs = CoefficientList[Normal[Series[u[n],{n,0,12}]], n]
Out= {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24}

In:= findLinearRecurrence[coeffs, v, n]
Out= v[n] == 2 + v[-1 + n]

Here we get the recurrence for the Lucas numbers.

In:= cLuc = LucasL[Range]
Out= {1, 3, 4, 7, 11, 18, 29, 47}

In:= findLinearRecurrence[cLuc, vL, n]
Out= vL[n] == vL[-2 + n] + vL[-1 + n]

(Same as Fibonacci, but different start value set.)

Daniel Lichtblau
Wolfram Research

```

• Prev by Date: Re: Re: Problem with parametric minimization
• Next by Date: Re: Anomaly? or at least a surprise.
• Previous by thread: Re: Code required for recurrence relations
• Next by thread: Mathematica and Spaces on Mac Os X