wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Integer series
        
(Message started by: rmsgrey on Oct 14^th, 2019, 3:22am)

Title: Integer series
Post by rmsgrey on Oct 14^th, 2019, 3:22am

Encountered in a university corridor about a week ago, credited, if memory serves, to the Hungarian maths olympiad this year:

Given that a₀=1, a₁=2 and (n+3)a_n+2=(6n+9)a_n+1-na_n

Prove that a_n is an integer for all n>0

So far, I've had some ideas, and proved a few things, but not yet seen any light, so I'll hold off on sharing what I've come up with to avoid biasing people down what may be dead-ends.

Title: Re: Integer series
Post by towr on Oct 14^th, 2019, 11:16pm

I can turn it into another sequence where I need to prove it's always a multiple of a factorial, but that doesn't seem to be an improvement. The only benefit there is I lose the division.

Title: Re: Integer series
Post by rmsgrey on Oct 15^th, 2019, 9:52am

Things I've noticed:

a₀ plays no part in the sequence (beyond itself) leaving all other a_n as multiples of a₁. Also, for small positive n, a_n is always even, which suggests that the sequence will always be integer for any integer a₁ (though it's possible I just haven't gone far enough to find a counter-example)

It also implies that it should be possible to express each term in terms of just the previous term and a function of n.

You can rephrase the condition by dividing through by (n+3) to leave a remainder:
R(n)=3a_n-9a_n+1
with
R(n) | n+3
which also rearranges the equation to:
a_n+2=6a_n+1-a_n+R(n)/(n+3)
which may or may not go anywhere.

Title: Re: Integer series
Post by towr on Oct 16^th, 2019, 11:25am

Hmm, the sequence can be found in the integer sequence database. And there's at least one formula where it's obvious all elements in the sequence must be integer. But even then, I'm still struggling to prove that that formula is equivalent to the one here.

Title: Re: Integer series
Post by rmsgrey on Oct 16^th, 2019, 5:47pm

A001003, the little Schroeder numbers, lists an equivalent form (starting (n+1)a_n rather than (n+3)a_n+2 ) as the first formula.

Given that the big Schroeder numbers (the given sequence) describe an integer property - the number of paths from SW corner to NE corner of an nxn square without rising above the diagonal, where individual steps are N, E or NE to the next lattice point, finding a suitable formula for them that can be shown to be equivalent to the given one would do it.

On the other hand, finding such a formula is not entirely trivial...