wu :: forums « wu :: forums - Integer series » Welcome, Guest. Please Login or Register. Apr 17th, 2024, 7:33am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: william wu, ThudnBlunder, Grimbal, Eigenray, Icarus, SMQ, towr)    Integer series « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Integer series  (Read 532 times)
rmsgrey
Uberpuzzler

Gender:
Posts: 2872
 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: 2872
 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: 2872
 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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »