XLVIII OM - I - Zadanie 6

Zawody matematyczne:

XLVIII OM, 1996-1997

Etap:

Wielomian $P(x)$ stopnia $n$ spełnia warunek

$ P(k)=\frac{1}{k}\ \textrm{dla}\ k = 1,2,4,8,\dots,2^n. $

Obliczyć $P(0)$ .

Rozwiązanie

Sposób I

Niech $P(x) = a_0 + a_1x + \dots + a_nx^n$ . Weźmy pod uwagę wielomian

$ \qquad (1) T(x)=xP(x)-1 = -1+a_0x + a_1x^2 + \dots + a_nx^{n+1}. $

Podstawiając w miejsce zmiennej $x$ liczby $k = 1,2,4,\dots ,2^n$ otrzymujemy, na podstawie warunku zadania, równości

$ T(k) =kP(k)-1=k\cdot\frac{1}{k}- 1=0. $

Zatem liczby te są pierwiastkami wielomianu $T(x)$ . Jest to wielomian stopnia $n+1$ , a więc daje się przedstawić jako iloczyn

$ \qquad (2) T(x) = a_n(x-1)(x-2)(x-4) \cdot \ldots \cdot (x-2^n). $

Wymnażając dwumiany w nawiasach otrzymamy ,,zwykłe'' przedstawienie wielomianu $T(x)$ w postaci rozwiniętej. Będzie nas interesował współczynnik przy $x$ (w pierwszej potędze); jest on równy $a_n(-1)^n \cdot (q_0 + q_1 +\ldots + q_n)$ , gdzie $q_j$ jest iloczynem liczb $1, 2, 4, \ldots ,2^n$ , z usuniętym czynnikiem $2^j$ .

Jednocześnie - zgodnie ze wzorem (1) - współczynnik przy $x$ w wielomianie $T(x)$ jest równy $a_0$ . Tak więc

$ \begin{split} a_0 &= a_n(-1)^n(q_0 + q_1 +\ldots+q_n) =\\ &= a_n(-1)^n \left(\frac{1\cdot 2 \cdot 4 \cdot \ldots \cdot 2^n}{2^0} + \frac{1\cdot 2 \cdot 4 \cdot \ldots \cdot 2^n}{2^1}+ \ldots +\frac{1\cdot 2 \cdot 4 \cdot \ldots \cdot 2^n}{2^n}\right). \end{split} $

Podstawiając zaś we wzorach (1) i (2) $x = 0$ , i przyrównując otrzymane wartości, dostajemy równość

$ -1 = a_n(-1)^{n+1}(1\cdot 2 \cdot 4 \cdot \ldots\cdot 2^n). $

Z uzyskanych zależności wynika, że

$ a_0 = \frac{1}{2^0}+\frac{1}{2^1}+ \ldots +\frac{1}{2^n}=2-\frac{1}{2^n}. $

Jest to szukana wartość $P(0)$ .

Sposób II

Zastosujemy postępowanie rekurencyjne. Oznaczmy rozważany wielomian $P(x)$ przez $P_n(x)$ . Dla $n = 0$ mamy wielomian stały $P_n(x) = 1$ . Ustalmy liczbę naturalną $n\geq 1$ . Dzielimy wielomian $P_n(x)$ przez dwumian $(x - 2^n)$ (dzielenie z resztą); ilorazem jest pewien wielomian $Q_n(x)$ , stopnia $n-1$ , a reszta jest równa $P_n(2^n)$ , czyli $2^{-n}$ :

$ \qquad (3) P_n(x) = Q_n(x)\cdot(x-2^n) + 2^{-n}. $

Podstawiamy kolejno $x = 2^i$ dla $i = 0,1,2,\ldots,n-1$ . Traktując otrzymane związki jako równania względem $Q_n(2^i)$ obliczamy - korzystając z warunku zadania -

$ Q_n(2^i)= \frac{P_n(2^i)-P_n(2^n)}{2^i-2^n} = \frac{2^{-i}-2^{-n}}{2^i-2^n} = - \frac{1}{2^{n+i}} \ \textrm{dla}\ i = 0,1,2,\dots,n-1. $

Weźmy pod uwagę wielomian $P_{n-1}(x)$ . Spełnia on warunki $P_{n-1}(k) = 1/k$ dla $k = 1,2,4,\dots ,2^{n-1}$ . To pozwala przepisać poprzednią równość jako

$ 2^nQ_n(2^i) = -2^{-i} = -P_{n-1}(2^i) \ \textrm{dla}\ i = 0,1,2,\ldots,n-1. $

Tak więc wielomiany $2^nQ_n(x)$ oraz $-P_{n-1}(x)$ , stopnia $n-1$ , przyjmują równe wartości w $n$ różnych punktach, i wobec tego są równe. Możemy w takim razie zastąpić czynnik $Q_n(x)$ przez $-2^{-n}P_{n-1}(x)$ we wzorze (3):

$ P_n(x) = -2^{-n} P_{n-1}(x) \cdot (x-2^n) + 2^{-n}. $

Podstawiamy $x=0$ i otrzymujemy zależność rekurencyjną:

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

Wzór ten jest słuszny dla każdej liczby naturalnej $n \geq 1$ . A skoro $P_0(0) = 1$ , dostajemy wynik:

$ P_n(0) = 1 + 2^{-1} + 2^{-2} + \ldots + 2^{-n} = 2-2^{-n}. $

Sposób III

Zachowujemy z poprzedniego rozwiązania oznaczenie $P_n(x)$ . Wyprowadzimy inną zależność rekurencyjną. Jak poprzednio, zauważamy, że $P_0(x) = 1$ ; w szczególności $P_0(0) = 1$ .

Ustalmy $n \geq 1$ . Wielomiany $P_n(x)$ i $P_{n-1}(x)$ przyjmują jednakowe wartości dla $x = 1,2,4,\ldots,2^{n-1}$ . Te liczby $(1, 2, 4, \ldots ,2^{n-1})$ są więc pierwiastkami wielomianu $P_n(x)-P_{n-1}(x)$ (stopnia $n$ ).

Oznaczając przez $a_n$ współczynnik przy $x^n$ w wielomianie $P_n(x)$ (zatem także w wielomianie $P_n(x) -P_{n-1}(x)$ ) otrzymujemy równość

$ P_n(x) - P_{n-1}(x) = a_n (x - 1)(x - 2)(x - 4)\cdot \ldots \cdot (x - 2^{n-1}). $

Przyjrzyjmy się teraz wielomianowi $R_n(x) = 2P_n(2x)$ ; jest to także wielomian stopnia $n$ , ze współczynnikiem przy $x^n$ równym $2^{n+1}a_n$ . Dla $x = 2^i$ (gdzie $i$ przebiega wartości $0,1,2,\ldots ,n-1$ ) mamy

$ R_n(2^i) = 2P_n(2^{i+1}) = 2 \cdot 2^{-(i+1)} = 2^{-i} = P_{n-1}(2^i). $

To znaczy, że liczby $1, 2, 4,\ldots ,2^{n-1}$ są jednocześnie pierwiastkami wielomianu $R_n(x) - P_{n-1}(x)$ , czyli wielomianu $2P_n(2x)-P_{n-1}(x)$ , i wobec tego

$ \begin{split} 2P_n(2x) -P_{n-1}(x) & = 2^{n+1} a_n (x-1)(x-2)(x-4)\cdot \ldots \cdot (x-2^{n-1}) =\\ & = 2^{n+1}(P_n(x)-P_{n-1}(x)). \end{split} $

Podstawiamy $x = 0$ i po prostym przekształceniu dostajemy równość

$ P_n(0) = \frac{2^{n+1}-1}{2^{n+1}-2} P_{n-1}(0) = \frac{1}{2} \cdot \frac{2^{n+1}-1}{2^{n}-1} P_{n-1}(0). $

Wiedząc, że $P_0(0) = 1$ , obliczamy:

$ P_n(0) = \prod_{m=1}^n \left( \frac{1}{2} \cdot \frac{2^{m+1}-1}{2^m-1} \right) = \frac{1}{2^n} \cdot \frac{2^2-1}{2^1-1} \cdot \frac{2^3-1}{2^2-1} \cdot \ldots \cdot \frac{2^{n+1}-1}{2^n-1} = \frac{2^{n+1}-1}{2^n}. $

Sposób IV

Rozwiązanie wykracza poza program szkolny; przedstawimy je szkicowo. Będziemy korzystali z najprostszych faktów z teorii równań liniowych i wyznaczników (literatura: dowolny akademicki podręcznik algebry liniowej).

Niech $P(x) = a_0 + a_1x + \ldots + a_nx^n$ . Dane w założeniach zadania warunki

$ \qquad (4) P(2^i) = \sum_{j=0}^n a_j (2^i)^j = \left( \frac{1}{2} \right)^i \ \textrm{dla}\ i = 0,1,\ldots,n $

traktujemy jak układ $n+1$ równań liniowych z niewiadomymi $a_0, a_1,\ldots, a_n$ . Wyznacznik tego układu $D = det [2^{ij}]_{0 \leq i,j \leq n}$ jest różny od zera; wynika to z następującego ogólnego faktu:

Jeśli $t_0,t_1,\ldots,t_n$ są dowolnymi liczbami rzeczywistymi, to

$ V(t_0, t_1, \ldots, t_n) = \det[t_i^j]_{0 \leq i,j \leq n} = \left| \begin{array}{cccc} 1 & 1 & \ldots & 1 \\ t_0 & t_1 & \ldots & t_n \\ t_0^2 & t_1^2 & \ldots & t_n^2 \\ \vdots & \vdots & \ddots & \vdots \\ t_0^n & t_1^n & \ldots & t_n^n \\ \end{array} \right| = \prod_{l,m: 0 \leq l<m \leq n} (t_m-t_l); $

jest to tzw. wyznacznik Vandermonde'a. W rozważanej tu sytuacji

$ D=\left| \begin{array}{cccc} 1 & 1 & \ldots & 1 \\ 1 & 2 & \ldots & 2^n \\ 1 & 2^2 & \ldots & 2^{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 1 & 2^n & \ldots & 2^{n^2} \\ \end{array} \right| = V(1,2,4, \ldots, 2^n) = \prod_{l,m: 0 \leq l<m \leq n} (2^m-2^l) \neq 0. $

Zatem układ równań (4) ma jednoznaczne rozwiązanie. Interesuje nas tylko niewiadoma $a_0$ ; wyraża się ona wzorem $a_0 = D_0/D$ , gdzie $D_0$ jest wyznacznikiem macierzy otrzymanej z macierzy układu (4) w wyniku zastąpienia jej skrajnej lewej kolumny (złożonej z samych jedynek) przez kolumnę złożoną z liczb znajdujących się po prawych stronach równań (4) . W konsekwencji $D_0$ także jest wyznacznikiem Vandermonde'a:

$ \begin{split} D=\left| \begin{array}{cccc} 1 & 1 & \ldots & 1 \\ 1/2 & 2 & \ldots & 2^n \\ 1/2^2 & 2^2 & \ldots & 2^{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 1/2^n & 2^n & \ldots & 2^{n^2} \\ \end{array} \right| & = V(\frac{1}{2},2,4, \ldots, 2^n) = \\ & = \prod_{m: 1 \leq m \leq n} (2^m-\frac{1}{2})\cdot \prod_{l,m: 1 \leq l<m \leq n} (2^m-2^l). \end{split} $

W takim razie

$ a_0=\frac{D_0}{D} = \prod_{m: 1 \leq m \leq n} \frac{2^m-\frac{1}{2}}{2^m-2^1} = \prod_{m=1}^n \left( \frac{1}{2} \cdot \frac{2^{m+1}-1}{2^m-1} \right). $

Otrzymaliśmy ten sam iloczyn, co w końcówce poprzedniego rozwiązania. Wynik (wartość $a_0 = P(0)$ ) — jak we wszystkich poprzednich rozwiązaniach.