XXVI - I - Zadanie 6

Zawody matematyczne:

XXVI OM, 1974-1975

Etap:

Niech $T_n$ będzie ciągiem liczb całkowitych zdefiniowanym następująco :

$ T_n=n-1 \quad \text{ dla }n = 1, 2, 3, 4, $

$ (1)\qquad T_{2k-1}= T_{2k-2} + 2^{k-2}, $

$ (2)\qquad T_{2k} = T_{2k-5} + 2^k, \text{ dla } k\geq 3 $

Dowieść, że

$ T_{2k-1}=\left[ \frac{12}{7} \cdot 2^{k-1}\right] \text{ dla } A = 1,2,\ldots $

i znaleźć wzór dla $T_{2k}$ .

Rozwiązanie

Wypisując pięć początkowych wyrazów ciągu $T_n$ sprawdzamy bezpośrednio, że wzór (3) zachodzi dla $k = 1, 2, 3$ . Załóżmy z kolei, że zachodzi on dla każdej liczby naturalnej $k$ nie większej od $n$ , gdzie $n$ jest pewną liczbą naturalną $\geq 3$ . Udowodnimy wzór (3) dla liczby $n+1$ .

Z (1) i (2) wynika, że

$ T_{2n+1} = T_{2n} + 2^{n-1} = T_{2n-5} + 2^n + 2^{n-1}. $

Z założenia indukcyjnego mamy

$ T_{2n-5} = \left[ \frac{12}{7} \cdot 2^{n-3} \right] -1. $

Zatem

$ \begin{split} T_{2n+1} &= \left[ \frac{12}{7} \cdot 2^{n-3} \right] + 2^n + 2^{n-1} - 1 = \left[ \frac{12}{7} \cdot 2^{n-3} + 2^n + 2^{n-1} \right] -1=\\ & = \left[ \frac{12}{7} \cdot 2^{n-3} \left( 1 + \frac{7}{12} \cdot 8 + \frac{7}{12} \cdot 4 \right) \right] -1 = \left[ \frac{12}{7} \cdot 2^{n} \right] -1. \end{split} $

Na mocy zasady indukcji wzór (3) zachodzi więc dla każdej liczby naturalnej $k$ .

Z (2) i (3) wynika, że

$ T_{2k} = T_{2k-5} + 2^k = \left[ \frac{12}{7} \cdot 2^{n-3} \right] + 2^k -1 $

dla $k \geq 3$ . Sprawdzamy bezpośrednio, że również dla $k = 1$ i $k = 2$ zachodzi $\displaystyle T_{2k} = \left[ \frac{12}{7} \cdot 2^{n-3} \right] -1$ .