Αναδρομική Σχέση

Nick Rapanos · #1

Ίσως να μην είναι το πιο κατάλληλο section να αναρτήσω αυτό το θέμα, αλλά για κάποιο λόγο δεν μπορώ να κάνω post στο Seniors.

Να βρεθεί η ακολουθία που ικανοποιεί την αναδρομική σχέση:

$a_n=(n-1)(a_{n-1}+a_{n-2})$

με αρχικές συνθήκες a_1=0, a_2=1

.

Υ.Γ. Με χαρά βλέπω και τις αλλαγές που έγιναν στο forum καθώς και την ανταπόκριση που υπάρχει!

#2

Η απάντηση είναι $\displaystyle{ a_n = n!\sum_{k=0}^n \frac{(-1)^k}{k!}}$ και είναι φυσικά εύκολο να ελεγχθεί ότι είναι ορθή. Δεν θα κάνω τις πράξεις για τον έλεγχο αλλά θα δώσω κάποιες ιδέες για το πως προέκυψε. (Δεν ήρθε ουρανοκατέβατη.)

Αν η σχέση ήταν μόνο $a_n = (n-1)a_{n-1}$ για n > 2

τότε εύκολα θα βλέπαμε ότι a_n = (n-1)!a_1

. Παίζοντας λίγο με παρόμοιες συναρτήσεις, παρατηρούμε ότι η a_n = n!

ικανοποιεί την αναδρομική σχέση αλλά όχι τις αρχικές συνθήκες. Ορίζουμε λοιπόν a_n = n!b_n

και βλέπουμε ότι $\displaystyle{ b_n = \left(1 - \frac{1}{n} \right)b_{n-1} + \frac{b_{n-2}}{n}}$ με αρχικές συνθήκες b_1=0,b_2=1/2

. Ισοδύναμα έχουμε $\displaystyle{ b_n - b_{n-1} = \frac{b_{n-2} - b_{n-1}}{n}.}$ Από εδώ ορίζουμε $c_n = b_n - b_{n-1}$ και βλέπουμε ότι $\displaystyle{ c_n = -\frac{c_{n-1}}{n}}$ με c_2=1/2

και άρα $\displaystyle{ c_n = \frac{(-1)^{n}}{n!}. }$ Επομένως $\displaystyle{ b_n = b_{n-1} + c_n = b_{n-2} + c_{n-1} + c_n = \cdots = c_1 + \cdots + c_n}$ και άρα $a_n = n!(c_1 + \cdots + c_n)$ που δίνει το πιο πάνω αποτέλεσμα.

Εκ των υστέρων βέβαια, και γνωρίζοντας τι αντιπροσωπεύει το άθροισμα που βρήκαμε μπορούμε να πούμε ότι το a_n

ισούται με τον αριθμό των 1-1 και επί συναρτήσεων $\displaystyle{ f: \{1,2,\ldots,n\} \to \{1,2,\ldots,n\}}$ οι οποίες δεν έχουν σταθερό σημείο.

Να προσθέσω και μια απόδειξη ότι αν D_n

ισούται με τον αριθμό των πιο πάνω συναρτήσεων τότε ισχύει η αναδρομική σχέση $D_n = (n-1)(D_{n-1} + D_{n-2})$ . Πράγματα αν $f(n) = i \neq n$ τότε αναδρομικά υπάρχουν $D_{n-1}$ συναρτήσεις $\displaystyle{ f: \{1,2,\ldots,n-1\} \to \{1,2,\ldots,n\} \setminus \{i\}}$ με $f(i) \neq n$ χωρίς σταθερό σημείο και $D_{n-2}$ συναρτήσεις $\displaystyle{ f: \{1,2,\ldots,n-1\} \to \{1,2,\ldots,n\} \setminus \{i\}}$ με f(i) = n

χωρίς σταθερό σημείο. Αθροίζοντας για $i=1,2,\ldots,n-1$ βρίσκουμε την αναδρομική σχέση.

Nick Rapanos · #3

Ακριβώς!

Κι εγώ έφτασα σε αυτή την αναδρομική προσπαθώντας να λύσω το πρόβλημα που περιγράφει ο Δημήτρης (γνώστο και ως Derangement Problem) και μετά παρατήρησα ότι

$a_n-na_{n-1}=-(a_{n-1}-(n-1)a_{n-2})\Longrightarrow u_n=-u_{n-1}$
...

Μια άλλη λύση για το Derangement Problem προκύπτει με χρήση της αρχής εγκλεισμού-αποκλεισμού.

Υ.Γ. Θα ήθελα να διευκρινίσω για τα νεότερα μέλη του forum ότι με τον όρο σταθερό σημείο ο Δημήτρης εννοεί κάποιο i=1,2,...,n

τέτοιο ώστε f(i)=i

.

#4

Μια λύση με γεννήτριες συναρτήσεις.

$\displaystyle{{a_n} = \left( {n - 1} \right)\left( {{a_{n - 1}} + {a_{n - 2}}} \right) \Rightarrow {a_{n + 2}} = \left( {n + 1} \right)\left( {{a_{n + 1}} + {a_n}} \right)}$ , $\displaystyle{{a_1} = 0}$ και $\displaystyle{{a_2} = 1}$ . Εύκολα προκύπτει ότι $\displaystyle{{a_0} = 1}$

Ορίζουμε $\displaystyle{{a_n} = n!{b_n}}$ , τότε $\displaystyle{\left( {n + 2} \right)!{b_{n + 2}} = \left( {n + 1} \right)\left( {\left( {n + 1} \right)!{b_{n + 1}} + n!{b_n}} \right) \Rightarrow \left( {n + 2} \right){b_{n + 2}} = \left( {n + 1} \right){b_{n + 1}} + {b_n}}$ και $\displaystyle{{b_0} = 1}$ , $\displaystyle{{b_1} = 0}$ .

Έστω $\displaystyle{f\left( x \right) = \sum\limits_{n = 0}^\infty {{b_n}{x^n}} }$ , τότε

$\displaystyle{\left( {n + 2} \right){b_{n + 2}} = \left( {n + 1} \right){b_{n + 1}} + {b_n} \Rightarrow \sum\limits_{n = 0}^\infty {\left( {n + 2} \right){b_{n + 2}}{x^{n + 1}}} = \sum\limits_{n = 0}^\infty {\left( {n + 1} \right){b_{n + 1}}{x^{n + 1}}} + \sum\limits_{n = 0}^\infty {{b_n}{x^{n + 1}}} \Rightarrow }$

$\displaystyle{ \Rightarrow {\left( {\sum\limits_{n = 0}^\infty {{b_{n + 2}}{x^{n + 2}}} } \right){'}} = x{\left( {\sum\limits_{n = 0}^\infty {{b_{n + 1}}{x^{n + 1}}} } \right){'}} + x\sum\limits_{n = 0}^\infty {{b_n}{x^n}} \Rightarrow {\left( {\sum\limits_{n = 2}^\infty {{b_n}{x^n}} } \right){'}} = x{\left( {\sum\limits_{n = 1}^\infty {{b_n}{x^n}} } \right){'}} + x\sum\limits_{n = 0}^\infty {{b_n}{x^n}} \Rightarrow }$

$\displaystyle{ \Rightarrow f'\left( x \right) = xf'\left( x \right) + xf\left( x \right) \Rightarrow \boxed{f'\left( x \right) + \frac{x}{{x - 1}}f\left( x \right) = 0}}$ .

Με κλασσική θεωρία επίλυσης γραμμικών διαφορικών εξισώσεων πρώτου βαθμού βρίσκουμε ότι $\displaystyle{f\left( x \right) = c\frac{1}{{x - 1}}{e^{ - x}}}$

και με δεδομένο ότι $\displaystyle{f\left( 0 \right) = {b_0} = 1}$ προκύπτει $\displaystyle{f\left( x \right) = \frac{1}{{1 - x}}{e^{ - x}} = \sum\limits_{k = 0}^\infty {{x^k}} \cdot \sum\limits_{k = 0}^\infty {{{\left( { - 1} \right)}^k}\frac{{{x^k}}}{{k!}}} = \sum\limits_{n = 0}^\infty {\left( {\sum\limits_{k = 0}^n {\frac{{{{\left( { - 1} \right)}^k}}}{{k!}}} } \right){x^k}} }$

Επομένως $\displaystyle{{b_n} = \sum\limits_{k = 0}^n {\frac{{{{\left( { - 1} \right)}^k}}}{{k!}}} }$ και $\displaystyle{{a_n} = n!\sum\limits_{k = 0}^n {\frac{{{{\left( { - 1} \right)}^k}}}{{k!}}} }$ .

Το ανάπτυγμα Taylor, απευθείας στην a_n

δεν "δούλεψε".

FERMA · #5

Αυτό το ν! τι συμβολίζει?
Φερμά
Β’ λυκείου

sokratis lyras · #6

Το

είναι το γινόμενο όλων των φυσικών αριθμών από το

εώς το

και διαβάζεται n παραγοντικό.

parmenides51 · #7

$\displaystyle{n!=n\cdot(n-1)\cdot(n-2)\cdot ... \cdot2\cdot1}$
διαβάζεται

παραγοντικό και πρέπει $n\in \mathbb{N}$ δηλαδή το

να είναι φυσικός αριθμός

πχ.
$\displaystyle{1!=1}$
$\displaystyle{2!=2\cdot1=2}$
$\displaystyle{3!=3\cdot2\cdot1=6}$
$\displaystyle{4!=4\cdot3\cdot2\cdot1=24}$
...
τέλος δεχόμαστε πως $\displaystyle{0!=1}$

FERMA · #8

Ευχαριστώ πολύ!!!!
Και αυτό σε ασκήσεις πως το χρησιμοποιώ?

sokratis lyras · #9

Αυτό το σύμβολο θα το συναντήσεις μόνο σε μαθηματικούς διαγωνισμούς ή αργότερα στο πανεπιστήμιο και όχι στο σχολείο.

FERMA · #10

Ακριβώς!!Για διαγωνισμούς ρωτάω.

spiros filippas · #11

Όπου συνδυαστική και παραγοντικο!!

sokratis lyras · #12

Ουσιαστικά,αυτό το σύμβολο δεν σε βοηθάει στην επίλυση ασκήσεων έκτος από τις συνδυαστικές ασκήσεις που θα συναντήσεις σε πανελλήνιους διαγωνισμούς και πάνω.Για περαιτέρω βοήθεια,θα σου πρότεινα να κοίταξεις βιβλια συνδυαστικής ή παλαία θέματα διαγωνισμών.

parmenides51 · #13

Ρίξε μια ματιά εδώ, αλλά ίσως σου πέσει βαρύ γιατί είναι πανεπιστημιακό.
Καλύτερα θα ήταν να έπαιρνες ένα βιβλίο που να τα περιγράφει.
Δεν μπορείς να απαντήσεις συνοπτικά πχ τι κάνεις με τις εξισώσεις. Είναι πολύ γενικό.
Συνήθως χρησιμοποιείται στον κλάδο των Μαθηματικών που λέγεται Συνδυαστική, σχετικό με τις Πιθανότητες.
Οι λέξεις που μπορείς να κάνεις αναζήτηση στο διαδίκτυο είναι ''παραγοντικό'' ,''βασική αρχή απαρίθμησης'' και ''συνδυαστική''.

Αναδρομική Σχέση

Αναδρομική Σχέση

Re: Αναδρομική Σχέση

Re: Αναδρομική Σχέση

Re: Αναδρομική Σχέση

Re: Αναδρομική Σχέση

Re: Αναδρομική Σχέση

Re: Αναδρομική Σχέση

Re: Αναδρομική Σχέση

Re: Αναδρομική Σχέση

Re: Αναδρομική Σχέση

Re: Αναδρομική Σχέση

Re: Αναδρομική Σχέση

Re: Αναδρομική Σχέση

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