IMC 2019/1/4

#1

Ορίζουμε την ακολουθία $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 · #2

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

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

Θα δουλέψουμε με τη γεννήτρια συνάρτηση

. Κάνουμε τις αντικαταστάσεις
$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) και έχουν εφαρμογές στη συνδυαστική, μεταξύ των άλλων.

IMC 2019/1/4

IMC 2019/1/4

Re: IMC 2019/1/4

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