Κεφάλαιο 3Γεννήτριες Συναρτήσεις

Δεδομένης μίας ακολουθίας απείρων όρων $a_0,a_1,a_2,\mathrm{\dots }$, η αντίστοιχη γεννήτρια συνάρτηση είναι μία σειρά δυνάμεων:

$$f(x)=a_0+a_{1}x+a_2{x}^2+\mathrm{\dots }=\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n$$

(3.1)

που είναι τυπική (formal) με την έννοια ότι ορίζεται αλγεβρικά και όχι αναλυτικά. Η ανωτέρω συνάρτηση ονομάζεται κανονική (ordinary) γεννήτρια συνάρτηση και είναι η απλούστερη μορφή γεννήτριας συνάρτησης, καθώς στη βιβλιογραφία αναφέρεται ένα πλήθος άλλων συνθετότερων γεννητριών συναρτήσεων, οι οποίες όμως δεν θα μας απασχολήσουν στα πλαίσια του βιβλίου αυτού. Στη συνέχεια, με τον επόμενο συμβολισμό ισοδυναμούμε την αρχική ακολουθία αριθμών με την αντίστοιχη γεννήτρια συνάρτηση:

$$<a_0,a_1,a_2,a_3,\dots <!--\; \dots \; -->>\leftrightarrow <!--\; \leftrightarrow \; -->a_0+a_{1}x+a_2{x}^2+a_3{x}^3\dots <!--\; \dots \; -->$$

(3.2)

Για παράδειγμα, έστω ότι δίνεται η απλή ακολουθία $<1,1,1,1,\dots <!--\; \dots \; -->>$, δηλαδή ισχύει $a_n=1$ για κάθε $n\ge 0$. Η αντίστοιχη γεννήτρια συνάρτηση είναι:

$$f(x)=\mathrm{\hspace{0.25em}1}+x+x^2+x^3+\mathrm{\dots }=\sum _{n=0}^{\mathrm{\infty }}{x}^n$$

(3.3)

Εύκολα προκύπτει ότι:

	$f(x)$	$=$	$1+x+x^2+x^3+\mathrm{\dots }$
		$=$	$1+x\cdot (1+x+x^2+x^3+\mathrm{\dots })$
		$=$	$1+x\cdot f(x)\Rightarrow$
	$f(x)$	$=$	${\displaystyle \frac{1}{1-x}}$

Επομένως, δοθείσης της ακολουθίας $a_n=1$ για κάθε $n\ge 0$, η αντίστοιχη γεννήτρια συνάρτηση είναι $f(x)=1/(1-x)$. Βέβαια, γνωρίζουμε από τις φθίνουσες γεωμετρικές προόδους, ότι η σχέση αυτή ισχύει μόνο αν , αλλά προς το παρόν δεν μας απασχολούν ζητήματα σύγκλισης. Ωστόσο, σημειώνεται το συμπέρασμα ότι με τη βοήθεια ιδιοτήτων της $f(x)$ μπορούμε να εξάγουμε πληροφορία για την αντίστοιχη ακολουθία αριθμών.

Ας εξετάσουμε ένα άλλο απλό παράδειγμα. Δίνεται η ακολουθία αριθμών $<1,-<!--\; -\; -->1,1,-<!--\; -\; -->1,\dots <!--\; \dots \; -->>$. Η αντίστοιχη γεννήτρια συνάρτηση είναι:

$$f(x)=\mathrm{\hspace{0.25em}1}-x+x^2-x^3+\mathrm{\dots }=\sum _{n=0}^{\mathrm{\infty }}{(-1)}^n{x}^n$$

(3.4)

Με την ίδια τεχνική, όπως προηγουμένως, προκύπτει ότι η αντίστοιχη γεννήτρια συνάρτηση είναι $f(x)=1/(1+x)$, δηλαδή ισχύει:

$$<1,-<!--\; -\; -->1,1,-<!--\; -\; -->1,\dots <!--\; \dots \; -->>\leftrightarrow <!--\; \leftrightarrow \; -->\frac{1}{1+x}$$

(3.5)

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

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

Στο προηγούμενο κεφάλαιο δόθηκε ορισμός της ακολουθίας Fibonacci δεύτερης τάξης. Στο σημείο αυτό θα συνδεθεί η έννοια αυτή με τις γεννήτριες συναρτήσεις. Συγκεκριμένα, θα αποδειχθεί ότι:

(3.15)

Με τη βοήθεια αυτής της σχέσης, στη συνέχεια θα βρεθεί ο κλειστός τύπος του $n$-οστού αριθμού Fibonacci, ενώ επίσης οι τεχνικές για την εύρεση αυτού του κλειστού τύπου θα εφαρμοσθούν και σε άλλες περιπτώσεις.

Ορίζουμε, λοιπόν, τη συνάρτηση:

$$f(x)=f_0+f_{1}x+f_2{x}^2+f_3{x}^3+f_4{x}^4+\mathrm{\dots }$$

(3.16)

Είναι ευνόητο ότι ισχύουν οι σχέσεις:

		$\leftrightarrow$	$x$
		$\leftrightarrow$	$xf(x)$
		$\leftrightarrow$	$x^{2}f(x)$

Αθροίζοντας τις σχέσεις αυτές κατά μέλη, προκύπτει:

(3.17)

Το αριστερό σκέλος της σχέσης αυτής ταυτίζεται με το αριστερό σκέλος της αποδεικτέας σχέσης. Συνεπώς, πρέπει να αποδειχθεί και η ισότητα των δύο δεξιών σκελών. Όμως, το δεξιό σκέλος της τελευταίας σχέσης ισούται με $f(x)$, δηλαδή ισχύει:

	$f(x)$	$=$	$x+xf(x)+x^{2}f(x)\mathit{\hspace{1em}\hspace{1em} }\Rightarrow$
	$f(x)$	$=$	${\displaystyle \frac{x}{1-x-x^2}}$

Δεδομένης, λοιπόν, της γεννήτριας συνάρτησης για την ακολουθία Fibonacci, θα προσπαθήσουμε να εξάγουμε ένα κλειστό τύπο για το $n$-οστό αριθμό Fibonacci. Αρχικά, εκτελούμε μία παραγοντοποίηση του παρονομαστή της γεννήτριας συνάρτησης:

$$1-x-x^2=(1-c_{1}x)(1-c_{2}x)$$

(3.18)

όπου οι σταθερές $c_1,c_2$ ισούνται με:

$$c_1=\frac{1+\sqrt{5}}{2}\mathit{\hspace{1em}\hspace{1em}\hspace{1em}}{c}_2=\frac{1-\sqrt{5}}{2}$$

(3.19)

Στη συνέχεια, για τη διάσπαση του κλάσματος της γεννήτριας συνάρτησης γράφουμε τη σχέση ως εξής:

$$\frac{x}{1-x-x^2}=\frac{c_3}{1-c_{1}x}+\frac{c_4}{1-c_{2}x}$$

(3.20)

Αν δώσουμε δύο τυχαίες τιμές στη μεταβλητή $x$, λαμβάνουμε δύο γραμμικές εξισώσεις με αγνώστους τα $c_3,c_4$. Λύνοντας το παραγόμενο γραμμικό σύστημα με δύο αγνώστους και δύο εξισώσεις προκύπτει:

$$c_3=\frac{1}{\sqrt{5}}\mathit{\hspace{1em}\hspace{1em}\hspace{1em}}{c}_4=-\frac{1}{\sqrt{5}}$$

(3.21)

Συνεπώς, ισχύει:

$$\frac{x}{1-x-x^2}=\frac{1}{\sqrt{5}}\left(\frac{1}{1-c_{1}x}-\frac{1}{1-c_{2}x}\right)$$

(3.22)

Όμως, για κάθε όρο της ανωτέρω παρένθεσης ισχύει:

	${\displaystyle \frac{1}{1-c_{1}x}}$	$=$	$1+c_{1}x+c_1^2{x}^2+\mathrm{\dots }$
	${\displaystyle \frac{1}{1-c_{2}x}}$	$=$	$1+c_{2}x+c_2^2{x}^2+\mathrm{\dots }$

Αντικαθιστώντας τις τιμές αυτές προκύπτει:

	$f(x)$	$=$	${\displaystyle \frac{1}{\sqrt{5}}}\left({\displaystyle \frac{1}{1-c_{1}x}}-{\displaystyle \frac{1}{1-c_{2}x}}\right)$
		$=$	${\displaystyle \frac{(1+c_{1}x+c_1^2{x}^2+\mathrm{\dots })-(1+c_{2}x+c_2^2{x}^2+\mathrm{\dots })}{\sqrt{5}}}\mathit{\hspace{1em}}\Rightarrow$
	$f_n$	$=$	${\displaystyle \frac{c_1^n-c_2^n}{\sqrt{5}}}={\displaystyle \frac{1}{\sqrt{5}}}\left({\left({\displaystyle \frac{1+\sqrt{5}}{2}}\right)}^n-{\left({\displaystyle \frac{1-\sqrt{5}}{2}}\right)}^n\right)$

Είναι γνωστά τα κλασικά αναπτύγματα των ${(a+b)}^2$ και ${(a+b)}^3$. Γενικεύοντας ισχύει:

$${(a+b)}^n=a^n+\left(\begin{array}{c}n\\ 1\end{array}\right)a^{n-1}b+\left(\begin{array}{c}n\\ 2\end{array}\right)a^{n-2}{b}^2+\mathrm{\dots }+\left(\begin{array}{c}n\\ n-1\end{array}\right)a{b}^{n-1}+b^n$$

(3.23)

Αντικαθιστώντας $a=1$ και $b=x$ προκύπτει:

$${(1+x)}^n=\mathrm{\hspace{0.25em}1}+\left(\begin{array}{c}n\\ 1\end{array}\right)x+\left(\begin{array}{c}n\\ 2\end{array}\right)x^2+\mathrm{\dots }+\left(\begin{array}{c}n\\ n-1\end{array}\right)x^{n-1}+x^n=\sum _{i=0}^n\left(\begin{array}{c}n\\ i\end{array}\right)x^i$$

(3.24)

Προκύπτει, λοιπόν, ότι η γεννήτρια συνάρτηση ${(1+x)}^n$ μπορεί να χρησιμεύσει για την εύρεση του πλήθους των συνδυασμών των $n$ αντικειμένων λαμβανόμενων ανά $k$, για $0\le k\le n$. Δηλαδή, ο συντελεστής του όρου $x^k$ είναι το πλήθος των συνδυασμών που μπορούμε να επιλέξουμε $k$ αντικείμενα από ένα σύνολο $n$ αντικειμένων. Για το λόγο αυτό, μία γεννήτρια συνάρτηση που υπολογίζει το πλήθος συνδυασμών ή διατάξεων ονομάζεται απαριθμήτρια (enumerator).

Ότι η γεννήτρια συνάρτηση ${(1+x)}^n$ πράγματι εκτελεί την απαρίθμηση των συνδυασμών μπορεί να εξηγηθεί ως εξής: Έστω ένα μονομελές σύνολο $\{a_1\}$. Υπάρχει 1 τρόπος να επιλεγούν 0 αντικείμενα, 1 τρόπος να επιλεγεί 1 αντικείμενο και 0 τρόποι να επιλεγούν περισσότερα αντικείμενα από το σύνολο αυτό. Άρα, για την περίπτωση αυτή, η γεννήτρια συνάρτηση είναι $(1+x)$. Δοθέντος ενός άλλου μονομελούς συνόλου $\{a_2\}$, ισχύει το ίδιο σκεπτικό ως προς τη γεννήτρια συνάρτηση. Είναι ευνόητο ότι η γεννήτρια συνάρτηση για την επιλογή από την ένωση ανεξαρτήτων συνόλων είναι το γινόμενο των αντίστοιχων γεννητριών συναρτήσεων. Επομένως, η γεννήτρια συνάρτηση για την επιλογή αντικειμένων από το διμελές σύνολο $\{a_1,a_2\}$ είναι ${(1+x)}^2$. Προφανώς, υπάρχει 1 τρόπος να επιλεγούν 0 αντικείμενα, 2 τρόποι να επιλεγεί 1 αντικείμενο, 1 τρόπος να επιλεγούν 2 αντικείμενα και 0 τρόποι να επιλεγούν περισσότερα αντικείμενα από το σύνολο αυτό. Αυτό το σκεπτικό μπορεί να γενικευθεί.

Στην επίλυση αναδρομικών εξισώσεων έχει εξ ολοκλήρου αφιερωθεί το Κεφάλαιο 2. Στο σημείο αυτό θα παρουσιασθεί ένας ακόμη τρόπος επίλυσης αναδρομικών εξισώσεων, ο οποίος στηρίζεται στην προηγούμενη θεωρία των γεννητριών συναρτήσεων.

Αρχικά, ας εξετάσουμε μία απλή περίπτωση. Δίνεται, λοιπόν, η αναδρομική εξίσωση: $t_k=3t_{k-1}$. Έστω ότι $f(x)$ είναι η ζητούμενη γεννήτρια συνάρτηση. Διαδοχικά έχουμε:

	$f(x)$	$=$	$a_0+a_{1}x\mathit{\hspace{1em}}+a_2{x}^2\mathit{\hspace{1em}}+a_3{x}^3\mathit{\hspace{1em}\hspace{1em} }+a_4{x}^4+\mathrm{\dots }$
	$3xf(x)$	$=$	$\mathrm{ }3a_{0}x+\mathrm{\hspace{0.25em}3}{a}_1{x}^2+3a_2{x}^3+\mathrm{\dots }$
	$f(x)-3xf(x)$	$=$	$a_0+(a_1-3a_0)x+(a_2-3a_1)x^2+\mathrm{\dots }$

Όμως, οι παρενθέσεις της τελευταίας σχέσης ισούνται με 0. Επομένως, ισχύει:

	$f(x)-3xf(x)$	$=$	$a_0\mathit{\hspace{1em}\hspace{1em}}\Rightarrow$
	$f(x)$	$=$	${\displaystyle \frac{a_0}{1-3x}}=a_0(1+3x+3^2{x}^2+3^3{x}^3+\mathrm{\dots })$

Συνεπώς, ισχύει $t_k=3^k{a}_0$, όπου βέβαια $a_0$ είναι η αρχική συνθήκη.

Ας εξετάσουμε τώρα μία πιο σύνθετη αναδρομική εξίσωση:

$$t_k=\mathrm{\hspace{0.25em}2}{t}_{k-1}+3t_{k-2}$$

(3.30)

όπου $k\ge 2$, ενώ επίσης ισχύει $t_0=t_1=1$. Η προκύπτουσα ακολουθία είναι: 1, 1, 5, 13, 41, 121, 365, $\mathrm{\dots }$. Για την εύρεση κλειστού τύπου για το $t_k$ θεωρούμε τη γεννήτρια συνάρτηση $f(x)$ όπου:

$$f(x)=\mathrm{\hspace{0.25em}1}+x+5x^2+13x^3+41x^4+121x^5+365x^6+\mathrm{\dots }$$

(3.31)

Και πάλι με μία σειρά αλγεβρικών χειρισμών μπορούμε να βρούμε τον κλειστό τύπο της γεννήτριας συνάρτησης και, επομένως, τον τύπο κάθε συντελεστή:

	$f(x)$	$=$	$a_0+a_{1}x\mathit{\hspace{1em}}+a_2{x}^2\mathit{\hspace{1em}}+a_3{x}^3\mathit{\hspace{1em}\hspace{1em} }+a_4{x}^4+\mathrm{\dots }$
	$2xf(x)$	$=$	$\mathrm{ }2a_{0}x+\mathrm{\hspace{0.25em}2}{a}_1{x}^2+\mathrm{\hspace{0.25em}2}{a}_2{x}^3+\mathrm{\dots }$
	$3x^{2}f(x)$	$=$	$\mathrm{ }3a_0{x}^2+\mathrm{\hspace{0.25em}3}{a}_1{x}^3+\mathrm{\dots }$

Αφαιρώντας κατά μέλη έχουμε:

$$f(x)-2xf(x)-3x^{2}f(x)=a_0+(a_1-2a_0)x+(a_2-2a_1-3a_0)x^2+(a_3-2a_2-3a_1)x^3+\mathrm{\dots }$$

(3.32)

Όμως, εξ ορισμού είναι γνωστό ότι $a_n-2a_{n-1}-3a_{n-2}=0$ και, επομένως, ισχύει:

	$f(x)-2xf(x)-3x^{2}f(x)$	$=$	$a_0+(a_1-2a_0)x\mathit{\hspace{1em}\hspace{1em}}\Rightarrow$
	$f(x)$	$=$	${\displaystyle \frac{1-x}{1-2x-3x^2}}$
		$=$	${\displaystyle \frac{1-x}{(1-3x)(1+x)}}$
		$=$	${\displaystyle \frac{1}{2}}{\displaystyle \frac{1}{1-3x}}+{\displaystyle \frac{1}{2}}{\displaystyle \frac{1}{1+x}}$

Στην τελευταία σχέση διαπιστώνουμε γνωστούς κλειστούς τύπους. Έτσι, καταλήγουμε ότι:

$$t_n=\frac{1}{2}{\mathrm{\hspace{0.25em}3}}^n+\frac{1}{2}{(-1)}^n$$

(3.33)

Ας εξετάσουμε ένα τελευταίο αλλά συνθετότερο παράδειγμα. Δίνονται οι αναδρομικές εξισώσεις:

	$a_n$	$=$	$2a_{n-1}+b_{n-1}$
	$b_n$	$=$	$a_{n-1}+2b_{n-1}$

όπου $a_0=1$ και $b_0=0$. Παρατηρούμε, όμως, ότι οι δύο εξισώσεις αυτές είναι «διαπλεκόμενες», γεγονός που καθιστά την επίλυσή τους δυσκολότερη.

Αρχικά, λοιπόν, δεχόμαστε ότι ισχύει:

$$A(x)=\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n\mathit{\hspace{1em}\hspace{1em}}\kappa \alpha \iota \mathit{\hspace{1em}\hspace{1em}}B(x)=\sum _{n=0}^{\mathrm{\infty }}{b}_n{x}^n$$

(3.34)

Πολλαπλασιάζουμε τις αρχικές αναδρομικές εξισώσεις επί $x^n$, οπότε προκύπτει:

	$a_n{x}^n$	$=$	$2a_{n-1}{x}^n+b_{n-1}{x}^n$
	$b_n{x}^n$	$=$	$a_{n-1}{x}^n+\mathrm{\hspace{0.25em}2}{b}_{n-1}{x}^n$

Λόγω της ύπαρξης του δείκτη $n$–1, στις επόμενες σχέσεις το άθροισμα αρχίζει από 1 και όχι από 0. Έχουμε λοιπόν:

	${\displaystyle \sum _{n=1}^{\mathrm{\infty }}}{a}_n{x}^n$	$=$	${\displaystyle \sum _{n=1}^{\mathrm{\infty }}}2a_{n-1}{x}^n+{\displaystyle \sum _{n=1}^{\mathrm{\infty }}}{b}_{n-1}{x}^n$
	${\displaystyle \sum _{n=1}^{\mathrm{\infty }}}{b}_n{x}^n$	$=$	${\displaystyle \sum _{n=1}^{\mathrm{\infty }}}{a}_{n-1}{x}^n+{\displaystyle \sum _{n=1}^{\mathrm{\infty }}}2b_{n-1}{x}^n$

Συνεπώς, ισχύει:

	$A(x)-a_0{x}^0$	$=$	$2x{\displaystyle \sum _{n=1}^{\mathrm{\infty }}}2a_{n-1}{x}^{n-1}+x{\displaystyle \sum _{n=1}^{\mathrm{\infty }}}{b}_{n-1}{x}^{n-1}$
	$B(x)-b_0{x}^0$	$=$	$x{\displaystyle \sum _{n=1}^{\mathrm{\infty }}}{a}_{n-1}{x}^{n-1}+\mathrm{\hspace{0.25em}2}x{\displaystyle \sum _{n=1}^{\mathrm{\infty }}}2b_{n-1}{x}^{n-1}$

ή ισοδύναμα:

	$A(x)-1$	$=$	$2x{\displaystyle \sum _{n=0}^{\mathrm{\infty }}}2a_{n-1}{x}^{n-1}+x{\displaystyle \sum _{n=0}^{\mathrm{\infty }}}{b}_{n-1}{x}^{n-1}$
	$B(x)-0$	$=$	$x{\displaystyle \sum _{n=0}^{\mathrm{\infty }}}{a}_{n-1}{x}^{n-1}+\mathrm{\hspace{0.25em}2}x{\displaystyle \sum _{n=0}^{\mathrm{\infty }}}2b_{n-1}{x}^{n-1}$

και

	$A(x)-1$	$=$	$2xA(x)+xB(x)$
	$B(x)-0$	$=$	$xA(x)+\mathrm{\hspace{0.25em}2}xB(x)$

Φθάσαμε σε ένα γραμμικό σύστημα 2 εξισώσεων με 2 αγνώστους, το οποίο επιλύεται και δίνει:

	$A(x)$	$=$	${\displaystyle \frac{1-2x}{1-4x+3x^2}}={\displaystyle \frac{1}{2}}{\displaystyle \frac{1}{1-x}}+{\displaystyle \frac{1}{2}}{\displaystyle \frac{1}{1-3x}}$
	$B(x)$	$=$	${\displaystyle \frac{x}{1-4x+3x^2}}=-{\displaystyle \frac{1}{2}}{\displaystyle \frac{1}{1-x}}+{\displaystyle \frac{1}{2}}{\displaystyle \frac{1}{1-3x}}$

Επομένως, από αυτές τις γεννήτριες συναρτήσεις προκύπτει ότι οι σειρές δυνάμεων είναι:

$$A(x)=\sum _{n=0}^{\mathrm{\infty }}\frac{1+3^n}{2}{x}^n\mathit{\hspace{1em}\hspace{1em}}\kappa \alpha \iota \mathit{\hspace{1em}\hspace{1em}}B(x)=\sum _{n=0}^{\mathrm{\infty }}\frac{3^n-1}{2}{x}^n$$

(3.35)

Το αντικείμενο των γεννητριών συναρτήσεων είναι τεράστιο. Οι απαρχές του πηγαίνουν πίσω στον De Moivre. Στο κεφάλαιο αυτό εξετάσθηκαν οι κανονικές γεννήτριες συναρτήσεις. Στη βιβλιογραφία αναφέρεται ένα πλήθος άλλων τύπων γεννητριών συναρτήσεων, όπως οι εκθετικές, οι πιθανοτικές, οι σειρές Lambert, οι σειρές Bell, οι σειρές Dirichlet και άλλες. Το βιβλίο του Wilf διαπραγματεύεται αποκλειστικά το αντικείμενο αυτό [197]. Μάλιστα το βιβλίο είναι διαθέσιμο στο Διαδίκτυο και περιέχει λυμένες και άλυτες ασκήσεις. Στα βιβλία των Govinda Rao [65], Liu [104], Bryant [24], Graham-Knuth-Patashnik [66] και Hofri [77] υπάρχουν εκτενή αντίστοιχα κεφάλαια (η σειρά των βιβλίων αντιστοιχεί σε αυξανόμενο βαθμό δυσκολίας). Η Άσκηση 6 προέρχεται από το άρθρο [57], ενώ οι Ασκήσεις 9-10 από το άρθρο [59].

1. 1.

   Να βρεθούν οι γεννήτριες συναρτήσεις των ακολουθιών:

   • –

     , και

   • –

     .

2. 2.

   Δίνεται η ακολουθία: . Θα ανέμενονταν οι επόμενες τιμές της ακολουθίας να είναι: 10, 12 κοκ. Ποιά είναι η γεννήτρια συνάρτηση που παράγει αυτή την ακολουθία; Να βρεθούν άλλες γεννήτριες συναρτήσεις που να δίνουν ακολουθίες με τους ίδιους 4 πρώτους όρους, αλλά η συνέχεια να είναι διαφορετική.

3. 3.

   Να βρεθεί η συνάρτηση για τους συντελεστές του $x^n$ των γεννητριών συναρτήσεων:

   • –

     $f(x)=\frac{x^3}{1-x^2}$, και

   • –

     $f(x)=\frac{x^2-1}{1+3x^3}$.

4. 4.

   Ποιοί είναι οι συντελεστές των δυνάμεων του $x$ που αντιστοιχούν στη γεννήτρια συνάρτηση:

   • –

     $f(x)=\frac{1}{1-2x^3}$, και

   • –

     $f(x)=\frac{1}{1-2x}$.

5. 5.

   Κατά πόσους τρόπους μπορεί:

   • –

     να τοποθετηθούν $n$ πράσινα αντικείμενα σε ένα δοχείο;

   • –

     να επιλεγεί ένα αντικείμενο από ένα δοχείο με $n$ διαφορετικά χρωματιστά αντικείμενα;

6. 6.

   Δύο παίκτες Π1 και Π2 παίζουν τάβλι και το τελικό αποτέλεσμα είναι Σ1:Σ2. Να υπολογισθεί ο αριθμός των διαφορετικών τρόπων που μπορούμε να φθάσουμε στο αποτέλεσμα αυτό. Για παράδειγμα, αν το τελικό αποτέλεσμα είναι 2:1, τότε υπάρχουν 3 διαφορετικοί τρόποι: (α) 0:1, 1:1, 2:1, (β) 1:0, 1:1, 2:1 και (γ) 1:0, 2:0, 2:1.

7. 7.

   Χρησιμοποιώντας τον κανόνα της συνέλιξης να βρεθεί με πόσους τρόπους μπορούν να τοποθετηθούν $n$ φρούτα σε ένα δοχείο υπό τους εξής περιορισμούς:

   • –

     το πλήθος των μήλων να είναι άρτιο,

   • –

     το πλήθος των μπανανών να είναι πολλαπλάσιο του 3,

   • –

     το πλήθος των πορτοκαλιών να είναι τουλάχιστον 4 και

   • –

     το πλήθος των αχλαδιών να είναι το μέγιστο 1.

8. 8.

   Κατά πόσους τρόπους μπορούμε να δώσουμε $n\ge 3$ ευρώ σε 3 άτομα:

   • –

     με τον περιορισμό ότι κάθε άτομο θα πάρει τουλάχιστον 1 ευρώ;

   • –

     χωρίς κάποιον περιορισμό;

   Πόσες λύσεις έχει η εξίσωση $x+y+z=n$;

9. 9.

   Με πόσους τρόπους μπορεί να καλυφθεί ένα ορθογώνιο 2x$n$ με κομμάτια ντόμινο 2x1; Η άσκηση να επιλυθεί δοκιμάζοντας διαδοχικά για τιμές $n=0,1,2,\mathrm{\dots }$. Τι παρατηρείτε;

10. 10.

    Με πόσους τρόπους μπορεί να καλυφθεί ένα ορθογώνιο 3x$n$ με κομμάτια ντόμινο 2x1; Επίσης, με πόσους τρόπους μπορεί να καλυφθεί ένα παραλληλεπίπεδο 2x2x$n$ με τούβλα 2x1x1;

11. 11.

    Να βρεθεί η γεννήτρια συνάρτηση που παράγει την ίδια ακολουθία με την έξοδο των επομένων ψευδικωδικών:

    x <-- 3; i <--1;
    while i<=5 do
       print(x);
       x <-- 2x-2;
       i <-- 1+1;
    

    x <-- 1; i <--1;
    while i<=5 do
       print(x);
       x <-- 5x-6;
       i <-- 1+1;
    

    x <-- 6; i <--1;
    while i<=5 do
       print(x);
       x <-- trunc(x/3)+6;
       i <-- 1+1;
    

12. 12.

    Δίνεται η αναδρομική εξίσωση:

    $$t_k=t_{k-1}+t_{k-2}-t_{k-3}$$

    (3.36)

    όπου $k\ge 3$, ενώ επίσης ισχύει $t_0=t_1=t_2=1$. Με τη βοήθεια γεννήτριας συνάρτησης να βρεθεί κλειστός τύπος για το $t_k$.

13. 13.

    Δίνεται η αναδρομική εξίσωση:

    $$t_k=\mathrm{\hspace{0.25em}2}{t}_{k-1}-1$$

    (3.37)

    όπου $k\ge 1$, ενώ επίσης ισχύει $t_0=1$. Με τη βοήθεια γεννήτριας συνάρτησης να βρεθεί κλειστός τύπος για το $t_k$.

14. 14.

    Δίνεται η αναδρομική εξίσωση:

    $$3t_k=-4t_{k-1}+t_{k-2}$$

    (3.38)

    όπου $k\ge 2$, ενώ επίσης ισχύει $t_0=t_1=1$. Με τη βοήθεια γεννήτριας συνάρτησης να βρεθεί κλειστός τύπος για το $t_k$.