XLVIII OM - I - Zadanie 6

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

\[<br />
P(k)=\frac{1}{k}\ \textrm{dla}\  k = 1,2,4,8,\dots,2^n.<br />
\]

Obliczyć $ P(0) $.

Rozwiązanie

Sposób I

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

\[<br />
\qquad (1) T(x)=xP(x)-1 = -1+a_0x + a_1x^2 + \dots + a_nx^{n+1}.<br />
\]

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

\[<br />
T(k) =kP(k)-1=k\cdot\frac{1}{k}- 1=0.<br />
\]

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

\[<br />
\qquad (2) T(x) = a_n(x-1)(x-2)(x-4) \cdot \ldots \cdot (x-2^n).<br />
\]

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

\[<br />
\begin{split}<br />
a_0 &= a_n(-1)^n(q_0 + q_1 +\ldots+q_n) =\\<br />
&= 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).<br />
\end{split}<br />
\]

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

\[<br />
-1 = a_n(-1)^{n+1}(1\cdot 2 \cdot 4 \cdot \ldots\cdot 2^n).<br />
\]

Z uzyskanych zależności wynika, że

\[<br />
a_0 = \frac{1}{2^0}+\frac{1}{2^1}+ \ldots +\frac{1}{2^n}=2-\frac{1}{2^n}.<br />
\]

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} $:

\[<br />
\qquad (3) P_n(x) = Q_n(x)\cdot(x-2^n) + 2^{-n}.<br />
\]

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 -

\[<br />
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.<br />
\]

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

\[<br />
2^nQ_n(2^i) = -2^{-i} = -P_{n-1}(2^i) \ \textrm{dla}\ i = 0,1,2,\ldots,n-1.<br />
\]

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):

\[<br />
P_n(x) = -2^{-n} P_{n-1}(x) \cdot (x-2^n) + 2^{-n}.<br />
\]

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

\[<br />
P_n (0) = P_{n-1}(0) + 2^{-n}.<br />
\]

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

\[<br />
P_n(0) = 1 + 2^{-1} + 2^{-2} + \ldots + 2^{-n} = 2-2^{-n}.<br />
\]

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ść

\[<br />
P_n(x) - P_{n-1}(x) = a_n (x - 1)(x - 2)(x - 4)\cdot \ldots \cdot (x - 2^{n-1}).<br />
\]

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

\[<br />
R_n(2^i) = 2P_n(2^{i+1}) = 2 \cdot 2^{-(i+1)} = 2^{-i} = P_{n-1}(2^i).<br />
\]

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

\[<br />
\begin{split}<br />
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)).<br />
\end{split}<br />
\]

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

\[<br />
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).<br />
\]

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

\[<br />
P_n(0) = \prod_{m=1}^n \left( \frac{1}{2} \cdot \frac{2^{m+1}-1}{2^m-1} \right) =<br />
\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}.<br />
\]

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

\[<br />
\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<br />
\]

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

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

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

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

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:

\[<br />
\begin{split}<br />
D=\left|<br />
\begin{array}{cccc}<br />
1     & 1 & \ldots & 1 \\<br />
1/2   & 2 & \ldots & 2^n \\<br />
1/2^2 & 2^2 & \ldots & 2^{2n} \\<br />
\vdots & \vdots & \ddots & \vdots \\<br />
1/2^n & 2^n & \ldots & 2^{n^2} \\<br />
\end{array}<br />
 \right|<br />
& = V(\frac{1}{2},2,4, \ldots, 2^n) = \\<br />
& = \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).<br />
\end{split}<br />
\]

W takim razie

\[<br />
a_0=\frac{D_0}{D} = \prod_{m: 1 \leq m \leq n} \frac{2^m-\frac{1}{2}}{2^m-2^1} =<br />
\prod_{m=1}^n \left( \frac{1}{2} \cdot \frac{2^{m+1}-1}{2^m-1} \right).<br />
\]

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.

Komentarze

Dodaj nową odpowiedź