Author 
Topic: Integer series (Read 403 times) 

rmsgrey
Uberpuzzler
Gender:
Posts: 2846


Integer series
« on: Oct 14^{th}, 2019, 3:22am » 
Quote Modify

Encountered in a university corridor about a week ago, credited, if memory serves, to the Hungarian maths olympiad this year: Given that a_{0}=1, a_{1}=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 deadends.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Integer series
« Reply #1 on: Oct 14^{th}, 2019, 11:16pm » 
Quote Modify

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.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



rmsgrey
Uberpuzzler
Gender:
Posts: 2846


Re: Integer series
« Reply #2 on: Oct 15^{th}, 2019, 9:52am » 
Quote Modify

Things I've noticed: a_{0} plays no part in the sequence (beyond itself) leaving all other a_{n} as multiples of a_{1}. Also, for small positive n, a_{n} is always even, which suggests that the sequence will always be integer for any integer a_{1} (though it's possible I just haven't gone far enough to find a counterexample) 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.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Integer series
« Reply #3 on: Oct 16^{th}, 2019, 11:25am » 
Quote Modify

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.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



rmsgrey
Uberpuzzler
Gender:
Posts: 2846


Re: Integer series
« Reply #4 on: Oct 16^{th}, 2019, 5:47pm » 
Quote Modify

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...


IP Logged 



