IMC 2019/1/4

Συντονιστής: Demetres

Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8145
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

IMC 2019/1/4

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Σάβ Αύγ 03, 2019 1:41 pm

Ορίζουμε την ακολουθία a_0, a_1, \ldots με την ακόλουθη αναδρομική σχέση:

\displaystyle a_0 = 1, a_1 = 2 και \displaystyle (n + 3)a_{n+2} = (6n + 9)a_{n+1} − na_n για \displaystyle n \geqslant 0.

Να αποδειχθεί ότι όλοι οι όροι της ακολουθίας είναι ακέραιοι.



Λέξεις Κλειδιά:
dement
Διευθύνον Μέλος
Δημοσιεύσεις: 1405
Εγγραφή: Τρί Δεκ 23, 2008 10:11 am

Re: IMC 2019/1/4

#2

Μη αναγνωσμένη δημοσίευση από dement » Τετ Αύγ 07, 2019 3:33 pm

Demetres έγραψε:
Σάβ Αύγ 03, 2019 1:41 pm
Ορίζουμε την ακολουθία a_0, a_1, \ldots με την ακόλουθη αναδρομική σχέση:

\displaystyle a_0 = 1, a_1 = 2 και \displaystyle (n + 3)a_{n+2} = (6n + 9)a_{n+1} − na_n για \displaystyle n \geqslant 0.

Να αποδειχθεί ότι όλοι οι όροι της ακολουθίας είναι ακέραιοι.
Θα δουλέψουμε με τη γεννήτρια συνάρτηση f. Κάνουμε τις αντικαταστάσεις
a_n \to f(x)

\displaystyle a_{n+1} \to \frac{f(x)-f(0)}{x}

\displaystyle a_{n+2} \to \frac{f(x)-f(0)-f’(0)x}{x^2}

(n+1)a_{n+1} \to f’(x)

na_n \to xf’(x)

\displaystyle (n+2)a_{n+2} \to \frac{f’(x)-f’(0)}{x}

με f(0) = 1, f’(0) = 2 και μετατρέπουμε την αναδρομική σχέση στη διαφορική εξίσωση (x^3 - 6x^2 + x)f’(x) - (3x-1)f(x) = x+1

Δουλεύοντας με την p(x) \equiv xf(x) έχουμε (x^2-6x+1)p’(x) - (x-3)p(x) = x+1.
Η διαφορική εξίσωση ολοκληρώνεται σχετικά εύκολα στη λύση \displaystyle p(x) = \frac{1 - x - \sqrt{1 - 6x + x^2}}{2}

Έτσι, αρκεί να αποδείξουμε ότι η σειρά Maclaurin (r_n) της \displaystyle -\frac{\sqrt{1 - 6x + x^2}}{2}, πέρα από τους δύο πρώτους όρους, είναι ακέραια. Από το γεγονός ότι το τετράγωνό της είναι \displaystyle \frac{1 - 6x + x^2}{4} και ο πρώτος όρος της r_0 = -1/2, εύκολα βλέπουμε ότι ο δεύτερος όρος της είναι r_1 = 3/2 και οι υπόλοιποι όροι (για τους οποίους ισχύει r_{n+1} = a_n) πληρούν την αναδρομική συνθήκη \displaystyle r_2 = a_1 = 2, \ r_{n+1} = 3 r_n + \sum_{k=2}^{n-1} r_k r_{n-1-k}. Έτσι, είναι όλοι ακέραιοι.

Σημ.: Ανακάλυψα ότι η ακολουθία έχει όνομα, λέγονται αριθμοί Schröder (ξαδέρφια των αριθμών Catalan) και έχουν εφαρμογές στη συνδυαστική, μεταξύ των άλλων.


Δημήτρης Σκουτέρης

Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
Απάντηση

Επιστροφή σε “Διαγωνισμοί για φοιτητές”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης