Author |
Topic: Integer series (Read 557 times) |
|
rmsgrey
Uberpuzzler
    
Gender: 
Posts: 2873
|
 |
Integer series
« on: Oct 14th, 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 a0=1, a1=2 and (n+3)an+2=(6n+9)an+1-nan
Prove that an 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.
|
|
 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 14th, 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: 2873
|
|
Re: Integer series
« Reply #2 on: Oct 15th, 2019, 9:52am » |
Quote Modify
|
Things I've noticed:
a0 plays no part in the sequence (beyond itself) leaving all other an as multiples of a1. Also, for small positive n, an is always even, which suggests that the sequence will always be integer for any integer a1 (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)=3an-9an+1
with
R(n) | n+3
which also rearranges the equation to:
an+2=6an+1-an+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 16th, 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: 2873
|
|
Re: Integer series
« Reply #4 on: Oct 16th, 2019, 5:47pm » |
Quote Modify
|
A001003, the little Schroeder numbers, lists an equivalent form (starting (n+1)an rather than (n+3)an+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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print