Question on A057960

[Mitch Harris]

Max [mailto:maxale at gmail.com] wrote:
> On 4/25/06, Mitch Harris <Harris.Mitchell at mgh.harvard.edu> wrote:
> > Max [mailto:maxale at gmail.com] wrote:
> > > On 4/24/06, franktaw at netscape.net <franktaw at netscape.net> wrote:
> > > >
> > > > All published terms of A057960 satisfy a(n) =
> > > > floor(a(n-1)*(a(n-1)+1/2)/a(n-2).  (In fact, I have
> > > > verified the next 7 terms as well.)  Note that for A057960, a(n)
=
> > > > floor(a(n-1)*(sqrt(3)+1)).  (This is the formula from DELEHAM
Philippe -
> > > > writing sqrt(3) as "3^0, 5" - ugh.)
> > > >
> > > > Can anyone prove that this recurrence does, in fact, produce
this sequence?
> > >
> > > It's enough to show that
> > > 0 <= a(n-1)*(a(n-1)+1/2)/a(n-2) - a(n) < 1
> > > or
> > > 0 <= a(n-1)*(a(n-1)+1/2) - a(n-2)*a(n) < a(n-2)
> > >
> > > Using the explicit formula
> > > a(n) = (4 + (1+sqrt(3))^(n+2) + (1-sqrt(3))^(n+2)) / 12
> >
> >  From this, it would also be enough to notice that
> >
> >    1-sqrt(3) ~= -.73
> >
> > so that
> >
> >    |(1-sqrt(3))^n| < 1,
> >
> > where it also then follows that
> >
> >    1/4 < ((-.73)^n + 4)/12 < 5/12
> >
> > which is removed by the floor function.
> 
> First off, are you proving the formula from DELEHAM Philippe or what?

Yes. I read originally Frank's 'this' as referring to the closest
recurrence in his question that a(n) = floor(a(n-1)*(sqrt(3)+1)) (the 
recurrence that Deleham supplied). Please pardon the confusion.

> And what do you mean saying "removed by the floor function" ?

ah...my confusion magnifies. I was mixing up the recurrences and the
closed form version in my head (a(n) = ceiling((1+sqrt(3))^(n+2))/12 )
(which you give below); the ceiling, not the floor, 'removes' or rather
adds in the ignorable extra bit ((1-sqrt(3))^(n+2)+4)/12).

> In the formula a(n) = (4 + (1+sqrt(3))^(n+2) + (1-sqrt(3))^(n+2)) / 12
> ~= (1+sqrt(3))^(n+2) / 12 + ((-.73)^(n+2) + 4)/12
> the second summand represents a number about 4/12=1/3 that 
> makes a(n) integer.
> In other words, (1+sqrt(3))^(n+2) / 12 is close to an integer minus
> 1/3, and adding ((-.73)^n + 4)/12 makes it integer.
> But I do not see any floor function here and why it should remove
> ((-.73)^(n+2) + 4)/12.
> Conversely, we can state that
> ceiling( (1+sqrt(3))^(n+2)/12 ) = (1+sqrt(3))^(n+2)/12 +
> ((1-sqrt(3))^(n+2)+4)/12

Mitch