XXX OM - I - Zadanie 10

Zawody matematyczne:

XXX OM, 1978-1979

Etap:

Dane są ciągi wielomianów $(P_n)$ , $(Q_n)$ określone, jak następuje:

$ \begin{split} P_0 = Q_0 &= 1, \\ P_n(x) &= P_{n-1}(x) + x^{2^{n-1}}\cdot Q_{n-1}(x),\\ Q_n(x) &= P_{n-1}(x) - x^{2^{n-1}} \cdot Q_{n-1}(x). \end{split} $

Niech $a_n$ będzie liczbą współczynników wielomianu $P_n$ równych 1. Udowodnić, że istnieje granica $\lim_{n\to \infty} \frac{a_n}{2^n}$ i obliczyć ją.

Rozwiązanie

Z określenia wielomianów $P_n$ i $Q_n$ wynika, że dla $n \geq 1$ każdy z nich ma stopień $2^n - 1$ oraz każdy ze współczynników tych wielomianów jest równy $1$ lub $-1$ . Jeżeli więc $a_n$ współczynników wielomianu $P_n$ jest równych $1$ , a $b_n$ współczynników tego wielomianu jest równych $-1$ , to

$ a_n + b_n = 2^n,\ a_n-b_n = P_n(1). $

Dodając te równości stronami otrzymujemy, że

$ (1) \qquad a_n = \frac{1}{2}(2^n + P_n(1)). $

Ze wzorów podanych w zadaniu wynika, że

$ P_n(1) = P_{n-1}(1) + Q_{n-1}(1)\ \textrm{i}\ Q_n(1) = P_{n-1}(1)- Q_{n-1}(1) $

dla $n \geq 1$ . Wobec tego

$ P_{n+1}(1) = P_n(1) + Q_n(1) = 2P_{n-1}(1). $

Ponieważ $P_0 = Q_0 = 1$ , więc $P_1(1) = 2$ . Wynika stąd przez łatwą indukcję, że $P_{2k-1} (1) = P_{2k} (1) = 2^k$ dla $k \geq 0$ . Zatem

$ P_n(1) \leq 2^{\frac{1}{2} (n+1)} = (\sqrt{2})^{n+1} < 2(\sqrt{2})^n\ \textrm{dla} \ n \geq 0. $

Wobec tego

$ 0 < \frac{P_n(1)}{2^n} < 2 \left( \frac{\sqrt{2}}{2} \right)^n. $

Na mocy twierdzenia o trzech ciągach wynika stąd, że ciąg $\left( \frac{P_n(1)}{2^n} \right)$ dąży do zera, ponieważ $0 < \frac{\sqrt{2}}{2} < 1$ oraz $\displaystyle \lim_{n \to \infty} \left( \frac{\sqrt{2}}{2} \right)^n = 0$ . Z (1) otrzymujemy $\frac{a_n}{2^n} = \frac{1}{2} + \frac{1}{2} \cdot \frac{P_n(1)}{2^n}$ . Na mocy powyższego ciąg $\left( \frac{a_n}{2^n} \right)$ jest więc zbieżny do $\frac{1}{2}$ .