wu :: forums
wu :: forums - Integer series

Welcome, Guest. Please Login or Register.
Oct 16th, 2021, 10:25pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: ThudnBlunder, towr, william wu, SMQ, Eigenray, Icarus, Grimbal)
   Integer series
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Integer series  (Read 359 times)
rmsgrey
Uberpuzzler
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2844
Integer series  
« on: Oct 14th, 2019, 3:22am »
Quote Quote Modify 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: male
Posts: 13729
Re: Integer series  
« Reply #1 on: Oct 14th, 2019, 11:16pm »
Quote Quote Modify 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
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2844
Re: Integer series  
« Reply #2 on: Oct 15th, 2019, 9:52am »
Quote Quote Modify 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: male
Posts: 13729
Re: Integer series  
« Reply #3 on: Oct 16th, 2019, 11:25am »
Quote Quote Modify 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
*****





134688278 134688278   rmsgrey   rmsgrey


Gender: male
Posts: 2844
Re: Integer series  
« Reply #4 on: Oct 16th, 2019, 5:47pm »
Quote Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board