possibly wrong comment with Motzkin numbers

[Max Alekseyev]

On 7/31/07, Joerg Arndt <arndt at jjj.de> wrote:

>  A024537 ,1, 2, 4, 9, 21, 50, 120, 289, 697, 1682 (=?= A018905)

Below I will prove that A018905 (except a missing first term) is a
duplicate of A024537.

Neil, as A024537 is much more developed (and have an extra initial term),
I suggest to mark A018905 as a dead duplicate of A024537.

Proof.

I will show that the explicit formula of A024537:
(*)   a(n) = 1/4*( 2 + (1-Sqrt(2))^(n+1) + (1+Sqrt(2))^(n+1) )
satisfies the recurrent relation given in the definition of A018905.

First note that the definition of A018905 is equivalent to:
a(n+1) = [a(n)^2 / a(n-1)] + 1
and below we will show that this formula follows from (*).

To simplify notation, let c=1+Sqrt(2).
Using formula (*), it is easy to get that:
a(n)^2 / a(n-1) = ( c^(n+2) + 4*c - 2*c^2 ) / 4 + O(c^(-n))
= ( c^(n+2) - 2 ) / 4 + O(c^(-n)) = a(n+1) - 1 + O(c^(-n))
where the terms hidden inside O() are positive and quickly become
negligible as n grows.

Therefore, [a(n)^2 / a(n-1)] + 1 = a(n+1).
Q.E.D.

Max



* Max Alekseyev <maxale at gmail.com> [Aug 01. 2007 08:34]:
> On 7/31/07, Joerg Arndt <arndt at jjj.de> wrote:
> > A comment with seq A001006
> > http://www.research.att.com/~njas/sequences/A001006
> > says (near top):
> >   Number of sequences of length n-1 consisting of positive integers
> >   such that the opening and ending elements are 1 or 2, and the
> >   absolute difference between any 2 consecutive elements is 0 or 1.
> >
> > This seems to be wrong, I get the counts
> >  A024537 ,1, 2, 4, 9, 21, 50, 120, 289, 697, 1682 (=?= A018905)
> >
> > Note the starts math, Motzkins start as
> >      [1,] 1, 2, 4, 9, 21, 51, 127, 323,
> 
> With a simple recurrence formula implementation in PARI/GP, I confirm
> that the comment in A001006 is correct:
> 
> { a(n,l) = if(n==1,(l==1)||(l==2),if(l<=0,0,a(n-1,l-1)+a(n-1,l)+a(n-1,l+1))) }
> 
> { f(n) = a(n,1)+a(n,2) }
> 
> ? vector(10,n,f(n))
> %1 = [2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798]

Yes, I was stupid again, I used strings with just the digits 0, 1, or 2,
This gives A024537 (modulo even more stupidity on my side).

> 
> Here a(n,l) counts the number of sequences of positive integers of
> length n, starting with 1 or 2 and ending with l.
> 
> Max

Thanks for checking!