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]]
];
];
]
Your example:
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[17]:= coeffs = CoefficientList[Normal[Series[u[n],{n,0,12}]], n]
Out[17]= {0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24}
In[18]:= findLinearRecurrence[coeffs, v, n]
Out[18]= v[n] == 2 + v[-1 + n]
Here we get the recurrence for the Lucas numbers.
In[19]:= cLuc = LucasL[Range[8]]
Out[19]= {1, 3, 4, 7, 11, 18, 29, 47}
In[20]:= findLinearRecurrence[cLuc, vL, n]
Out[20]= vL[n] == vL[-2 + n] + vL[-1 + n]
(Same as Fibonacci, but different start value set.)
Daniel Lichtblau
Wolfram Research
- References:
- Code required for recurrence relations
- From: "Ant King" <mathstutoring@ntlworld.com>
- Code required for recurrence relations