# [seqfan] Re: 3 nonlinear recurrences

Maximilian Hasler maximilian.hasler at gmail.com
Sun Sep 20 19:57:27 CEST 2009

```Georgi Guninski wrote:
> [1]
> A059480 A recurrence equation.
> a(n) = a(n - 1) + (n + 1)*a(n - 2)

This is not a nonlinear, but a linear recurrence:
The sequence obtained for a(0)=alpha and a(1)=beta is
alpha a0 + beta a1, where a0 and a1 are the sequences obtained for
(alpha,beta)=(1,0) resp. (0,1),
a0=(1,0,3,3,18,36,162,450,1908,6408,27396,104292,460440,...)
a1=(0,1,1,5,10,40,110,430,1420,5720,21340,89980,367400,...)

> a[i+1]=( a[i-2]*a[i-1]-a[i-1]^2+a[i-2]*a[i]+a[i-1]*a[i])/a[i-2]
> (i think i proved this by substituting the definition and simplifying to
> 0)

But what is the purpose of this more complicated formula?

> [2]
> A135686 Two sequence type recursion of a generalized Stirling number
> type using the Fibonacci sequence
>
> a[n]=a[n-1]+fibonacci[n]*a[n-2]

This also is a linear recurrence.

>w0,w1,w2,w3,w4,w5,w6,w7= -1, 1, -1, -1, -1, 1, 1, 1
> a[i+2] =(w0*a[i-1]^2*a[i]  - (w1*a[i-2]*a[i]^2+w2*a[i-1]*a[i]^2+w3*a[i-2]*a[i-1]*a[i+1]+w4*a[i-2]*a[i]*a[i+1]))/(w5*a[i-2]*a[i-1])

This also is more complicated that the original formula.
In particular, why do you use w0,w2,...,w7 instead of just putting the
minus sign for the negative ones ?

> [3]
> a[0]=0,a[1]=1
> a[n]=a[n-1]+2^n * a[n-2]

again a linear recurrence

> a[i+1]=(-2*a[i-1]^2+a[i-2]*a[i]+2*a[i-1]*a[i])/a[i-2]

You get this if you write 2^(n+1)=2*2^n in the equation for a(n+1)
and substitute 2^n by its expression in terms of (a(n)-a(n-1))/a(n-2).

You can of course "disguise" any linear recurrence in this manner, but
I don't think this is very useful.

Maximilian

```