Πλήθος ακολoυθιών

#1

Δοθέντων $k \in \{0, 1, 2, 3\}$ και θετικού ακεραίου

έστω

το πλήθος των ακολoυθιών x_1,..., x_n

, όπου $x_i \in \{-1, 0, 1\}$ για i = 1,..., n

και
$x_1 + ...+ x_n\equiv k \pmod 4.$ Δείξτε ότι
(α) f_1(n) = f_3(n)

για κάθε

(b) $\displaystyle{f_0(n) =\frac{3^n + 2 + (-1)^n}{4}}$ για κάθε

#2

Επαναφορά το 2020!

#3

Ας γράψουμε και A_k(n)

για τα σύνολα των αντίστοιχων ακολουθιών. Παρατηρούμε ότι υπάρχει 1-1 αντιστοιχεία μεταξύ των A_1(n)

και

που δίνεται από τον τύπο $(x_1,\ldots,x_n) \mapsto (-x_1,\ldots,-x_n)$ .

Παρητηρούμε τώρα ότι έχουμε f_3(n)

ακολουθίες στο A_0(n+1)

με $x_{n+1} = 1$ , f_0(n)

με $x_{n+1}=0$ και f_1(n)

με $x_{n+1}=-1$ . Άρα

f_0(n+1) = f_3(n) + f_0(n) + f_1(n) = f_0(n) + 2f_1(n)

.

και ομοίως

f_1(n+1) = f_0(n) + f_1(n) + f_2(n)

Παρατηρούμε ότι f_0(n+1) - f_2(n+1) = f_0(n) - f_2(n)

άρα και

. Επομένως

f_1(n+1) = f_1(n) + 2f_0(n) - 1

και

$\begin{aligned} f_0(n+1) &= f_0(n) + 2f_1(n) \\ &= f_0(n) + 2f_1(n-1) + 4f_0(n-1) - 2 \\ &= f_0(n) + [f_0(n) - f_0(n-1)] + 4f_0(n-1) - 2 \\ &= 2f_0(n) + 3f_0(n-1) - 2 \end{aligned}$

Η χαρακτηριστική εξίσωση είναι η x^2 - 2x - 3

με ρίζες

και

. Έχουμε επίσης την ειδική λύση f_0(n) = 1/2

. Άρα η γενική λύση είναι της μορφής

$\displaystyle f_0(n) = A \cdot 3^n + B \cdot (-1)^n + \frac{1}{2}$

και από τις αρχικές συνθήκες f_0(1) = 1, f_0(2) = 3

, παίρνουμε 3A-B = 1/2

και

που δίνουν Α = 1/4

και

. Άρα καταλήγουμε στο ζητούμενο

$\displaystyle f_0(n) = \frac{3^n + (-1)^n + 2}{4}$

Πλήθος ακολoυθιών

Πλήθος ακολoυθιών

Re: Πλήθος ακολoυθιών

Re: Πλήθος ακολoυθιών

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