Correction for A052944

[Pieter Moree]

Rainer Rosenthal wrote:

> Please let me forward a correction I received in de.sci.mathematik from
> Hermann Kremer, when I tolf them about A052944.
>
> I think he will be right (as nearly always), but I just wanted to
> ask here.
>
> Best regards
> Rainer Rosenthal
> r.rosenthal at web.de
>
> :   ID Number: A052944
> :   URL:       http://www.research.att.com/projects/OEIS?Anum=A052944 :
>  Sequence:  0,2,5,10,19,36,69,134,263,520,1033,2058,4107,8204,16397, :
>          32782,65551,131088,262161,524306,1048595,2097172,4194325, :
>        8388630,16777239,33554456,67108889,134217754,268435483, :
>    536870940,1073741853,2147483678
> :   Name:      a(n) = 2^n + n - 1
> :   G.f.: (-2+3*x)/(-1+2*x)/(-1+x)^2
>
> The G.f. is OK  ...
>
> :   Recurrence: {a(1)=5,a(0)=2,2*a(n)-a(n+1)+1-n}
>
> But not the recursion, which should read
>
>     { a(0)=0, a(1)=2, a(2)=5,  a(n+3) = 4*a(n+2) - 5*a(n+1) + 2*a(n) }
>
This is correct of course. It follows from the theory of recurrences
with constant coefficients that the characteristic polynomial for a
recurrence for numbers of the form
c*2^n+(a*n+b), a non-zero, is (x-2)*(x-1)^2=x^3-4x^2+5x-2.

Another recurrence for the
given sequence is clearly: a(n+1)=2*a(n)-n+2 with
a(0)=0.

Pieter Moree