Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

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>