All packages presented here are avaible for download at
https : // combinatorics.risc.jku.at/software

<<RISC`GeneratingFunctions`

Package GeneratingFunctions version 0.8 written by Christian Mallinger
Copyright Research Institute for Symbolic Computation (RISC),
Johannes Kepler University, Linz, Austria

?REPlus

defining the sequences of Perrin and Lucas numbers

perrin = {a[n+3]-a[n+1]-a[n]==0,a[0]==3,a[1]==0,a[2]==2};
lucas = {a[n+2]-a[n+1]-a[n]==0,a[0]==2,a[1]==1};

computing a recurrence for the addition of Perrin and Lucas numbers

REPlus[perrin,lucas,a[n]]

REPlus[perrin[[1]],lucas[[1]],a[n]]

?RE*

?RESubsequence

Computing a recurrence for all odd - indexed Lucas numbers

RESubsequence[lucas,a[n],2n+1]

Cauchy product of Perrin and Lucas numbers

RECauchy[perrin,lucas,a[n]]

defining the Fibonacci sequence

fib = {F[n+2]-F[n+1]-F[n]==0,F[0]==0,F[1]==1};

Computing the recurrence for the Cauchy product of Fibonacci numbers with the constant sequence 1, i.e., for the partial sum of Fibonacci numbers

RECauchy[fib,{F[n]==1},F[n]]

Fibonacci, Perrin and Lucas numbers also exist as built -in functions in Mathematica

?Fibonacci

?Perrin

?LucasL

Fibonacci[0]

creating data for guessing

dataL = Table[LucasL[nn],{nn,0,20}];
dataP = Table[Perrin[nn],{nn,0,20}];

dataL

?GuessRE

Guessing the recurrence for Lucas numbers

GuessRE[dataL,a[n]]

Guessing the recurrence for Perrin numbers -> need to increase the maximal order used!

GuessRE[dataP,a[n]]

GuessRE[dataP,a[n],{0,3},{0,0}]

<<RISC`HolonomicFunctions`
<<RISC`Guess`

HolonomicFunctions Package version 1.7.3 (21-Mar-2017)
written by Christoph Koutschan
Copyright Research Institute for Symbolic Computation (RISC),
Johannes Kepler University, Linz, Austria

Guess Package version 0.52
written by Manuel Kauers
Copyright Research Institute for Symbolic Computation (RISC),
Johannes Kepler University, Linz, Austria

GuessMinRE[dataP,a[n]]

?Guess*

Example from lecture : both C - finite and hypergeometric

data = Table[2^(n-1)(n+2),{n,0,30}];

GuessMinRE[data,a[n]]

?GuessMultRE

GuessMultRE[data,{a[n],a[n+1],a[n+2]},{n},0]

GuessMinRE[Table[Fibonacci[n],{n,0,50}],f[n]]

Flatten[Table[s2[n+nn,k+kk],{nn,0,1},{kk,0,1}]]

GuessMultRE[Table[StirlingS2[nn,kk],{nn,0,20},{kk,0,20}],Flatten[Table[s2[n+nn,k+kk],{nn,0,1},{kk,0,1}]],{n,k},1]

?Annihilator

S[n] ... forward shift in n

ann=Annihilator[Sum[LucasL[3k] Fibonacci[n-k],{k,0,n}],S[n]]

ApplyOreOperator[ann,a[n]]

%[[1]]==0

Annihilator[LegendreP[n,x],{Der[x]}]

Annihilator[LegendreP[n,x],{Der[x],S[n]}]

Sum[LucasL[3k] Fibonacci[n-k],{k,0,n}]

We know that Lucas and Fibonacci numbers both satisfy a recurrence of order 2.
By closure properties, the subsequence L[3n] satisfies a recurrence of order 2.
The Cauchy product of the two sequences corresponds to the multiplication of the generating functions: each has a denominator of degree 2, so the product a denominator of degree at most 4, which translates into a recurrence of order at most 4. 
Hence, if we compute the coefficients of a C-finite recurrence of order 4 from the first 25 values of the sum, we know that it holds for all n.

Clear[s];
s[n_]:=Sum[LucasL[3k] Fibonacci[n-k],{k,0,n}];

Table[Sum[c[i] s[5j+i],{i,0,4}]==0,{j,0,4}]

Solve[Table[Sum[c[i] s[5j+i],{i,0,4}]==0,{j,0,4}]]

NullSpace[Table[s[5j+i],{j,0,4},{i,0,4}]]

deCatalan=AE2DE[{x y[x]^2-y[x]+1==0,y[0]==1},y[x]]

DE2RE[deCatalan,y[x],c[n]]

Annihilator[CatalanNumber[n],S[n]]