Matematyka 1NI/Indukcja matematyczna
Indukcja matematyczna
Zadanie 1
Wykazać, że dla dowolnego [math]n\in\mathbb{N}[/math] prawdziwa jest równość:
Do obu stron założenia indukcyjnego należy dodać brakujący wyraz.
- Sprawdzamy prawdziwość równości (1) dla [math]n=1\,[/math].
Lewa strona: [math]L=1^3+(2\cdot 1+1)^3=28\,[/math].
Prawa strona: [math]P=2(1+1)^4-(1+1)^2=28\,[/math]. Zatem [math]L=P.\,[/math] - Wykonujemy krok indukcyjny.
Założenie indukcyjne: [math]1^3+3^3+\ldots +(2n+1)^3=2(n+1)^4-(n+1)^2\,[/math]
Teza indukcyjna: [math]1^3+3^3+\ldots +(2n+3)^3=2(n+2)^4-(n+2)^2.\,[/math]
Wychodzimy od założenia indukcyjnego i dodajemy do obu stron wyrażenie [math](2n+3)^3\,[/math]. Po lewej stronie otrzymamy w ten sposób lewą stronę tezy indukcyjnej, natomiast prawą przekształcimy w następujący sposób:[math] \begin{array}{ccl} 2(n+1)^4&\!\!\!\! -&\!\!\! (n+1)^2+(2n+3)^3=\\ &\!\!\!=&\!\!\! 2(n+1)^4-(n+1)^2+(2(n+1)+1)^3\\ &\!\!\!=&\!\!\! 2(n+1)^4-(n+1)^2+8(n+1)^3+12(n+1)^2+6(n+1)+1\\ &\!\!\!=&\!\!\!2\underbrace{\left[(n+1)^4+4(n+1)^3+6(n+1)^2+4(n+1)+1\right]}_{((n+1)+1)^4}-\underbrace{\left[(n+1)^2+2(n+1)+1\right]}_{((n+1)+1)^2}\\ &\!\!\!=&\!\!\! 2(n+2)^4-(n+2)^2\; . \end{array} \, [/math]
Otrzymaliśmy tezę indukcyjną, co kończy dowód.
Zadanie 2
Wykazać, że dla dowolnego [math]n\in\mathbb{N}\,[/math] i [math]n\geq 2\,[/math] prawdziwa jest równość:
Do obu stron założenia indukcyjnego należy dodać brakujący wyraz.
- Sprawdzamy prawdziwość równości (3) dla [math]n=2\,[/math].
Lewa strona: [math]L=\frac{1}{2^2-1}=\frac{1}{3}\,[/math].
Prawa strona: [math]P=\frac{(3\cdot 2+2)(2-1)}{4\cdot 2(2+1)}=\frac{1}{3}\,[/math]. Zatem [math]L=P\,[/math]. - Wykonujemy krok indukcyjny.
'Założenie indukcyjne: [math]\frac{1}{2^2-1}+\frac{1}{3^2-1}+\ldots\frac{1}{n^2-1}=\frac{(3n+2)(n-1)}{4n(n+1)}\,[/math].
Teza indukcyjna: [math]\frac{1}{2^2-1}+\frac{1}{3^2-1}+\ldots+\frac{1}{(n+1)^2-1}=\frac{(3n+5)n}{4(n+1)(n+2)}\,[/math].
Do obu stron założenia indukcyjnego dodajemy wyrażenie [math]\displaystyle\frac{1}{(n+1)^2-1}\,[/math]. Po lewej stronie otrzymamy lewą stronę tezy indukcyjnej. Prawą zaś przekształcimy w poniższy sposób:[math]\begin{array}{ccl} \displaystyle\frac{(3n+2)(n-1)}{4n(n+1)}&\!\!\!\!+&\!\!\! \displaystyle\frac{1}{(n+1)^2-1}=\displaystyle\frac{(3n+2)(n-1)}{4n(n+1)}+\displaystyle\frac{1}{n(n+2)}\\ &\!\!\!=&\!\!\! \displaystyle\frac{(3n+2)(n-1)(n+2)+4(n+1)}{4n(n+1)(n+2)}=\displaystyle\frac{3n^3+5n^2-4n-4+4n+4}{4n(n+1)(n+2)}\\ &\!\!\!=&\!\!\! \displaystyle\frac{(3n+5)n}{4(n+1)(n+2)}\; . \end{array}\,[/math]
Otrzymaliśmy tezę indukcyjną, więc dowód indukcyjny jest zakończony.
Zadanie 3
Wykazać wzór de Moivre'a:
dla dowolnego [math]\phi\in\mathbb{R}\, [/math] oraz [math]n\in \mathbb{N}\, [/math].
Obie strony założenia indukcyjnego należy pomnożyć przez czynnik [math](\cos\phi +i\sin\phi)\,[/math].
- Sprawdzamy prawdziwość równości (5) dla [math]n=1\,[/math].
Lewa strona: [math]L=(\cos\phi +i\sin\phi)^1=\cos\phi +i\sin\phi\,[/math].
Prawa strona: [math]P=\cos(1\cdot \phi) +i\sin(1\cdot \phi)=\cos\phi +i\sin\phi\,[/math]. Zatem [math]L=P\,[/math]. - Wykonujemy krok indukcyjny.
Założenie indukcyjne: [math](\cos\alpha +i\sin\alpha)^n=\cos n\alpha +i\sin n\alpha\, [/math].
Teza indukcyjna: [math](\cos\phi +i\sin\phi)^{n+1}=\cos (n+1)\phi +i\sin (n+1)\phi\,[/math].
Obie strony założenia indukcyjnego pomnożymy przez czynnik [math](\cos\phi +i\sin\phi)\,[/math]. Po lewej stronie otrzymujemy od razu lewą stronę tezy indukcyjnej. Otrzymaną prawą stronę przekształcimy wykorzystując wzory:[math] \sin(\alpha+\beta)=\sin\alpha\cos\beta+\cos\alpha\sin\beta\; ,\,[/math][math] \cos(\alpha+\beta)=\cos\alpha\cos\beta-\sin\alpha\sin\beta\; . \,[/math]Otrzymujemy:
[math] \begin{array}{ccl} (\cos n\phi +i\sin n\phi )(\cos\phi +i\sin\phi )&\!\!\!=&\!\!\! \cos n\phi \cos\phi -\sin n\phi \sin\phi +i(\sin n\phi \cos\phi +\cos n\phi \sin\phi )\\ &\!\!\!=&\!\!\! \cos (n+1)\phi +i\sin (n+1)\phi\; , \end{array}\, [/math]gdzie przyjęliśmy [math]\alpha=n\phi\,[/math] oraz [math]\beta=\phi\, [/math].
Uzyskaliśmy tezę indukcyjną, co kończy dowód indukcyjny.
Zadanie 4
Wykazać, że dla dowolnego [math]n\in\mathbb{N}\,[/math] i [math]n\geq 2\, [/math] zachodzi nierówność:
Do obu stron założenia indukcyjnego należy dodać brakujący wyraz.
- Sprawdzamy prawdziwość nierówności (9) dla [math]n=2\,[/math].
Lewa strona: [math]\displaystyle L=\frac{\sqrt{2}}{1}=\sqrt{2}\,[/math].
Prawa strona: [math]\displaystyle P=\sqrt{2-1}=\sqrt{1}=1\,[/math]. Zatem [math]L\gt P\,[/math]. - Wykonujemy krok indukcyjny.
Założenie indukcyjne: [math]\displaystyle\frac{\sqrt{2}}{1}+\frac{\sqrt{3}}{2}+\ldots\frac{\sqrt{n}}{n-1}\gt \sqrt{n-1}\,[/math].
Teza indukcyjna: [math]\displaystyle\frac{\sqrt{2}}{1}+\frac{\sqrt{3}}{2}+\ldots\frac{\sqrt{n+1}}{n}\gt \sqrt{n}\,[/math].
Do obu stron założenia indukcyjnego dodamy wyrażenie [math]\displaystyle\frac{\sqrt{n+1}}{n}\,[/math]. Po lewej stronie otrzymamy lewą stronę tezy indukcyjnej, a prawą przekształcimy w następujący sposób:[math] \sqrt{n-1}+\frac{\sqrt{n+1}}{n}= \frac{n-1}{\sqrt{n-1}}+\frac{\sqrt{n+1}}{n}\gt \frac{n-1}{\sqrt{n}}+\frac{\sqrt{n}}{n}=\frac{n-1}{\sqrt{n}}+\frac{1}{\sqrt{n}}=\frac{n}{\sqrt{n}}=\sqrt{n}\; . \,[/math]Stąd wyciągamy wniosek, iż
[math]\frac{\sqrt{2}}{1}+\frac{\sqrt{3}}{2}+\ldots\frac{\sqrt{n+1}}{n}\gt \sqrt{n}\; .\,[/math]
Otrzymaliśmy tezę indukcyjną, a tym samym wykazaliśmy prawdziwość nierówności w treści zadania.
Zadanie 5
Wiadomo, iż
dla [math]x_1,x_1\in\mathbb{R}\,[/math]. Wykazać na tej podstawie, że dla dowolnego [math]n\in\mathbb{N}\,[/math] i [math]n\geq 2\,[/math] zachodzi także
Należy wyjść od lewej strony tezy indukcyjnej i przekształcać ją, korzystając z założenia indukcyjnego.
- Prawdziwość nierówności (12) dla [math]n=2\, [/math] wynika z samej treści zadania, więc nie musimy jej sprawdzać.
- Wykonujemy krok indukcyjny.
Założenie indukcyjne: [math]|x_1+x_2+\ldots+x_n|\leq |x_1|+|x_2|+\ldots+|x_n|\,[/math].
Teza indukcyjna: [math]|x_1+x_2+\ldots+x_{n+1}|\leq |x_1|+|x_2|+\ldots+|x_{n+1}|\,[/math].
Aby wykazać tezę indukcyjną, lewą jej stronę zapiszemy w następujący sposób:[math] |\underbrace{x_1+x_2+\ldots+x_n}_{a}+\underbrace{x_{n+1}}_{b}|=|a+b|\leq |a|+|b|\; ,\,[/math]gdzie skorzystaliśmy z nierówności (11) w treści zadania. Z założenia indukcyjnego wynika natomiast, że
[math] |a|=|x_1+x_2+\ldots+x_n|\leq |x_1|+|x_2|+\ldots+|x_n|\; ,\,[/math]i w konsekwencji
[math] |x_1+x_2+\ldots+x_{n+1}|=|a+b|\leq |a|+|b|\leq |x_1|+|x_2|+\ldots+|x_{n+1}|\; .\,[/math]
Otrzymaliśmy tezę indukcyjną, a więc wykazaliśmy również prawdziwość (12).
Zadanie 6
Wykazać, że dla dowolnego [math]n\in\mathbb{N}\,[/math] zachodzi nierówność:
Należy wyjść od lewej strony tezy indukcyjnej i przekształcać ją, korzystając z założenia indukcyjnego.
- Sprawdzamy prawdziwość nierówności (16) dla [math]n=1\,[/math].
Lewa strona: [math]L=1\cdot 1=1\,[/math]. - Wykonujemy krok indukcyjny.
Założenie indukcyjne: [math]\displaystyle(1+2+\ldots + n)\left(\frac{1}{1}+\frac{1}{2}+\ldots\frac{1}{n}\right)\geq n^2\,[/math].
Teza indukcyjna: [math]\displaystyle(1+2+\ldots + (n+1))\left(\frac{1}{1}+\frac{1}{2}+\ldots\frac{1}{n+1}\right)\geq (n+1)^2\,[/math].
Będziemy przekształcać poniżej lewą stronę tezy indukcyjnej:[math]\begin{array}{ccl} (1+2+\ldots &\!\!\! +&\!\!\! (n+1))\bigg(\displaystyle\frac{1}{1}+\frac{1}{2}+\ldots\frac{1}{n+1}\bigg)=(1+2+\ldots + n)\bigg(\frac{1}{1}+\frac{1}{2}+\ldots\frac{1}{n}\bigg)\\ &\!\!\! +&\!\!\! (n+1)\bigg(\displaystyle\frac{1}{1}+\frac{1}{2}+\ldots\frac{1}{n}\bigg)+(1+2+\ldots + n)\frac{1}{n+1}+(n+1)\frac{1}{n+1}\; .\end{array}\,[/math]Teraz wykorzystamy założenie indukcyjne w odniesieniu do pierwszego wyrazu po prawej stronie. Z kolei dla drugiego wyrazu możemy wykorzystać oszacowanie:
[math] (n+1)\bigg(\frac{1}{1}+\frac{1}{2}+\ldots\frac{1}{n}\bigg)\geq \frac{3}{2}(n+1)\; .\,[/math]Zastosujemy także znany wzór na sumę kolejnych liczb naturalnych:
[math] 1+2+\ldots + n=\frac{n(n+1)}{2}\; .\,[/math]Zbierając to razem, otrzymujemy nierówność:
[math]\begin{array}{ccl}\displaystyle (1+2+\ldots &\!\!\! +&\!\!\! \displaystyle(n+1))\bigg(\frac{1}{1}+\frac{1}{2}+\ldots\frac{1}{n+1}\bigg)\\ &\!\!\! \geq &\!\!\! \displaystyle n^2+\frac{3}{2}(n+1)+\frac{n(n+1)}{2}\cdot\frac{1}{n+1}+1\\ &\!\!\! =&\!\!\! \displaystyle n^2+2n+1\frac{5}{2}\gt n^2+2n+1=(n+1)^2\; .\end{array}\,[/math]
Prawa strona: [math]P=1^2=1\,[/math]. Zatem [math]L\geq P\,[/math].
W ten sposób otrzymaliśmy tezę indukcyjną i wykazaliśmy prawdziwość (16).
Zadanie 7
Wykazać, że dla dowolnego [math]n\in\mathbb{N}\,[/math] zachodzi nierówność:
Obie strony założenia indukcyjnego należy pomnożyć przez brakujący czynnik.
- Sprawdzamy prawdziwość nierówności (21) dla [math]n=1\,[/math].
Lewa strona: [math]L=(2\cdot 1-1)!!=1\,[/math].
Prawa strona: [math]P=1^1=1\,[/math]. Zatem [math]L\leq P\,[/math]. - Wykonujemy krok indukcyjny.
Założenie indukcyjne: [math]\displaystyle(2n-1)!!\leq n^n\,[/math].
Teza indukcyjna: [math]\displaystyle(2n+1)!!\leq (n+1)^{n+1}\,[/math].
Obie strony założenia indukcyjnego pomnożymy teraz przez czynnik [math](2n+1)\,[/math]. W wyniku tego otrzymamy nierówność:[math] (2n-1)!!(2n+1)=(2n+1)!!\leq (2n+1)n^n\; . \,[/math]Po lewej stronie otrzymaliśmy lewą stronę tezy indukcyjnej, a oszacowaniem prawej zajmiemy się poniżej. Jeśli wykorzystać wzór dwumienny Newtona, to można napisać:
[math] \begin{array}{ccl} (n+1)^{n+1}&\!\!\!=&\!\!\!\displaystyle\sum_{k=0}^{n+1}\left(\begin{array}{c}n+1\\ k\end{array}\right)n^{n+1-k}1^k\\ &\!\!\!=&\!\!\!\left(\begin{array}{c}n+1\\ 0\end{array}\right)n^{n+1}+\left(\begin{array}{c}n+1\\ 1\end{array}\right)n^n+\ldots +\left(\begin{array}{c}n+1\\n+1\end{array}\right)\gt n^{n+1}+(n+1)n^n\; . \end{array}\,[/math]Po prawej stronie możemy teraz rozpoznać prawą stronę (22):
[math] (2n+1)n^n=n\cdot n^n+(n+1)n^n=n^{n+1}+(n+1)n^n\; , \,[/math]i na mocy (23) otrzymujemy tezę indukcyjną, co kończy dowód.
Zadanie 8
Wykazać, że dla dowolnego [math]n\in\mathbb{N}\,[/math] i [math]n\geq 2\,[/math] liczba postaci [math]n^7-n\,[/math] jest podzielna przez [math]7\,[/math].
Należy tak przekształcić liczbę [math](n+1)^7-(n+1)\,[/math], aby móc skorzystać z założenia indukcyjnego.
- Sprawdzamy, czy liczba [math]n^7-n\,[/math] podzielna jest przez [math]7\,[/math] dla [math]n=2\,[/math].
Ponieważ [math]2^7-2=2(2^6-1)=2(64-1)=2\cdot 63=18\cdot 7\; ,\,[/math] więc podzielność ma miejsce. - Wykonujemy krok indukcyjny.
Założenie indukcyjne: istnieje takie [math]l\in\mathbb{N}\,[/math], że [math]n^7-n=7\cdot l\,[/math].
Teza indukcyjna: istnieje takie [math]k\in\mathbb{N}\,[/math], że [math](n+1)^7-(n+1)=7\cdot k\,[/math].
Przekształćmy teraz lewą stronę tezy indukcyjnej, korzystając ze wzoru dwumiennego Newtona:[math] \begin{array}{ccl} &&\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!(n+1)^7-(n+1)= \displaystyle\sum_{k=0}^7\left(\begin{array}{c}7\\ k\end{array}\right)n^{7-k}1^k-(n+1)\\ &\!\!\! =&\!\!\! n^7 +\left(\begin{array}{c}7\\ 1\end{array}\right)n^6+\left(\begin{array}{c}7\\ 2\end{array}\right)n^5+\left(\begin{array}{c}7\\ 3\end{array}\right)n^4+\left(\begin{array}{c}7\\ 4\end{array}\right)n^3+\left(\begin{array}{c}7\\ 5\end{array}\right)n^2+\left(\begin{array}{c}7\\ 6\end{array}\right)n+1-n-1\\ \\ &\!\!\! =&\!\!\! \displaystyle\underline{n^7}+7(n^6+n)+21(n^5+n^2)+35(n^4+n^3)-\underline{n}\\ \\ &\!\!\! =&\!\!\! \displaystyle7(\underbrace{l+n^6+n+3n^5+3n^2+5n^4+5n^3}_k)\; . \end{array}\,[/math]Dokonując powyższych przekształceń skorzystaliśmy z założenia indukcyjnego, zastępując dwa podkreślone wyrazy wielkością [math]7\cdot l\,[/math]. W wyniku tego, po prawej stronie uzyskaliśmy prawą stronę tezy indukcyjnej, gdyż wyrażenie w nawiasie jest liczbą naturalną. Można je oznaczyć symbolem [math]k\,[/math]. Dowód indukcyjny jest więc ukończony.
Zadanie 9
Wykazać, że dla dowolnego [math]n\in\mathbb{N}\,[/math] liczba postaci [math]n(n+1)(2n+1)\,[/math] jest podzielna przez [math]6\,[/math].
Należy tak przekształcić liczbę [math](n+1)(n+2)(2n+3)\,[/math], aby móc skorzystać z założenia indukcyjnego.
- Sprawdzamy, czy liczba [math]n(n+1)(2n+1)\,[/math] podzielna jest przez [math]6\,[/math] dla [math]n=1\,[/math].
Ponieważ [math]1(1+1)(2\cdot 1+1)=6\,[/math], więc podzielność ma miejsce. - Wykonujemy krok indukcyjny.
Założenie indukcyjne: istnieje takie [math]l\in\mathbb{N}\,[/math], że [math]n(n+1)(2n+1)=6\cdot l\,[/math].
Teza indukcyjna: istnieje takie [math]k\in\mathbb{N}\,[/math], że [math](n+1)(n+2)(2n+3)=6\cdot k\,[/math].
Przekształćmy teraz lewą stronę tezy indukcyjnej w następujący sposób:[math] \begin{array}{ccl} (n+1)(n&\!\!\!\!\! +&\!\!\!\!\! 2)(2n+3)=(n+2)(n+1)(2n+1+2)\\ &\!\!\! =&\!\!\! \underline{n(n+1)(2n+1)}+2(n+1)(2n+3)+2n(n+1)\\ &\!\!\! =&\!\!\! 6\cdot l+2(n+1)(n+2n+3)=6\cdot l+6(n+1)^2=6[\underbrace{l+(n+1)^2}_k]\; . \end{array}[/math]Dokonując powyższych przekształceń skorzystaliśmy z założenia indukcyjnego, zastępując podkreślony wyraz wielkością [math]6\cdot l\,[/math]. W wyniku tego, po prawej stronie uzyskaliśmy prawą stronę tezy indukcyjnej, gdyż wyrażenie w nawiasie jest liczbą naturalną. Można je oznaczyć symbolem [math]k\,[/math]. Tym samym zakończyliśmy dowód indukcyjny.
Czasami dowód indukcyjny jest żmudniejszy niż dowód wprost. Wystarczy bowiem napisać [math]n(n+1)(2n+1)=n(n+1)(2n+4-3)=2 n(n+1)(n+2)-3 n (n+1)\,[/math]. Ponieważ spośród trzech kolejnych liczb naturalnych jedna jest podzielna przez trzy i spośród dwóch kolejnych liczb naturalnych jedna jest parzysta to liczba jest podzielna przez 6.
Zadanie 10
Wykazać, że dla dowolnego [math]n\in\mathbb{N}\,[/math] i [math]n\geq 2\,[/math] liczba postaci [math]4^n+6n-10\,[/math] jest podzielna przez [math]9\,[/math].
Należy tak przekształcić liczbę [math]4^{n+1}+6(n+1)-10\,[/math], aby móc skorzystać z założenia indukcyjnego.
- Sprawdzamy, czy liczba [math]4^n+6n-10\,[/math] podzielna jest przez [math]9\,[/math] dla [math]n=2\,[/math].
Ponieważ [math]4^2+6\cdot 2-10=18\,[/math], więc podzielność ma miejsce. - Wykonujemy krok indukcyjny.
Założenie indukcyjne: istnieje takie [math]l\in\mathbb{N}\,[/math], że [math]4^n+6n-10=9\cdot l\,[/math].
Teza indukcyjna: istnieje takie [math]k\in\mathbb{N}\,[/math], że [math]4^{n+1}+6(n+1)-10=9\cdot k\,[/math].
Przekształćmy teraz lewą stronę tezy indukcyjnej w następujący sposób:[math] \begin{array}{ccl} 4^{n+1}+6(n+1)-10&\!\!\! =&\!\!\! 4\cdot \underline{4^n}+6(n+1)-10=4(9l-6n+10)+6(n+1)-10\\ &\!\!\! =&\!\!\! 36l-24n+40+6n-4=9(\underbrace{4l-2n+4}_k)\; . \end{array}\,[/math]Dokonując powyższych przekształceń skorzystaliśmy z założenia indukcyjnego, zastępując podkreślony wyraz wielkością [math]9l-6n+10\,[/math]. W wyniku tego, po prawej stronie uzyskaliśmy prawą stronę tezy indukcyjnej, gdyż wyrażenie w nawiasie jest liczbą naturalną. Można je oznaczyć symbolem [math]k\,[/math]. Tym samym zakończyliśmy dowód indukcyjny.
Zadanie 11
Wykazać, że dla dowolnego [math]n\in\mathbb{N}\cup\{0\}\,[/math] wielomian:
jest podzielny przez [math](x-1)^2\,[/math].
Należy tak przekształcić wielomian [math]w_{n+1}(x)\,[/math], aby wykorzystać założenie indukcyjne.
- Sprawdzamy, czy wielomian [math]w_0(x)\,[/math] podzielny jest przez [math](x-1)^2\,[/math].
Ponieważ [math]w_0(x)=3x^2-6x+3=3(x-1)^2\,[/math], więc podzielność ma miejsce. - Wykonujemy krok indukcyjny.
Założenie indukcyjne: istnieje taki wielomian [math]q(x)\,[/math], że [math]w_n(x)=(x-1)^2q(x)\,[/math].
Teza indukcyjna: istnieje taki wielomian [math]p(x)\,[/math], że [math]w_{n+1}(x)=(x-1)^2p(x)\,[/math].
Przekształcimy teraz wielomian [math]w_{n+1}(x)\,[/math] w poniższy sposób:[math] \begin{array}{ccl} w_{n+1}(x)&\!\!\! =&\!\!\!(4n+7)x^{n+3}-(7n+13)x^{n+2}+(3n+5)x^{n+1}+1\\ &\!\!\! =&\!\!\!\underline{(4n+3)x^{n+3}}+4x^{n+3}-\underline{(7n+6)x^{n+2}}-7x^{n+2}\\ &\!\!\! +&\!\!\!\underline{(3n+2)x^{n+1}}+3x^{n+1}+\underline{x}-x+1\;. \end{array}\,[/math]Zbierając razem cztery podkreślone wyrażenia widzimy, że mają one postać [math]x\, w_n(x)\,[/math], co pozwoli nam wykorzystać założenie indukcyjne. Otrzymujemy:
[math] \begin{array}{ccl} w_{n+1}(x)&\!\!\! =&\!\!\! x\,w_n(x)+x^{n+1}(4x^2-7x+3)-(x-1)\\ &\!\!\! =&\!\!\! x(x-1)^2q(x)+x^{n+1}(x-1)(4x-3)-(x-1)\\ &\!\!\! =&\!\!\! x(x-1)^2q(x)+(x-1)[x^{n+1}(4x-3)-1]\; . \end{array}\,[/math]Wielomian [math]x^{n+1}(4x-3)-1\,[/math] zeruje się dla [math]x=1\,[/math], więc można go zapisać w postaci: [math](x-1)r(x)\,[/math], gdzie [math]r(x)\,[/math] jest także pewnym wielomianem. Pozwala nam to nadać wzorowi na [math]w_{n+1}(x)\,[/math] formę:
[math] w_{n+1}(x)=(x-1)^2[\underbrace{x\,q(x)+r(x)}_{p(x)}]\; . \,[/math]Wyrażenie w nawiasach prostokątnych znów jest wielomianem, co oznacza, że otrzymaliśmy tezę indukcyjną, a tym samym zakończyliśmy dowód indukcyjny.
Zadanie 12
Wykazać, że dla dowolnego [math]n\in\mathbb{N}\cup\{0\}\,[/math] wielomian:
ma podwójne miejsce zerowe dla [math]x=-1\,[/math].
Należy tak przekształcić wielomian [math]w_{n+1}(x)\,[/math], aby wykorzystać założenie indukcyjne.
Zadanie w istocie sprowadza się do wykazania podzielności wielomianu [math]w_n(x)\,[/math] przez [math](x+1)^2\,[/math]. Możemy więc postępować tak, jak w poprzednim zadaniu.
- Sprawdzamy, czy wielomian [math]w_0(x)\,[/math] podzielny jest przez [math](x+1)^2\,[/math].
Ponieważ [math]w_0(x)=2x^2+4x+2=2(x+1)^2\,[/math], więc podzielność ma miejsce. - Wykonujemy krok indukcyjny.
Założenie indukcyjne: [math]w_n(x)=(x+1)^2q(x)\,[/math], gdzie [math]q(x)\,[/math] jest pewnym wielomianem.
Teza indukcyjna: istnieje wielomian [math]p(x)\,[/math] taki, że [math]w_{n+1}(x)=(x+1)^2p(x)\,[/math].
Przekształcimy teraz wielomian [math]w_{n+1}(x)\,[/math] w następujący sposób:[math] \begin{array}{ccl} w_{n+1}(x)&\!\!\! =&\!\!\!(n+3)x^{n+3}+(n+5)x^{n+2}+x^{n+1}+(-1)^{n+1}\\ &\!\!\! =&\!\!\!\underline{(n+2)x^{n+3}}+x^{n+3}+\underline{(n+4)x^{n+2}}+x^{n+2}\\ &\!\!\! +&\!\!\!\underline{x^{n+1}}+\underline{(-1)^nx}-(-1)^nx+(-1)^{n+1}\;. \end{array}\,[/math]Zbierając razem cztery podkreślone wyrażenia widzimy, że mają one postać [math]x\, w_n(x)\,[/math], co pozwoli nam wykorzystać założenie indukcyjne. Otrzymujemy:
[math] \begin{array}{ccl} w_{n+1}(x)&\!\!\! =&\!\!\! x\,w_n(x)+x^{n+2}(x+1)+(-1)^{n+1}(x+1)\\ &\!\!\! =&\!\!\! x(x+1)^2q(x)+(x+1)[x^{n+2}+(-1)^{n+1}]\; . \end{array}\,[/math]Wielomian [math]x^{n+2}+(-1)^{n+1}\,[/math] zeruje się dla [math]x=-1\,[/math], więc można go zapisać w postaci: [math](x+1)r(x)\,[/math], gdzie [math]r(x)\,[/math] jest także pewnym wielomianem. Pozwala nam to nadać wzorowi na [math]w_{n+1}(x)\,[/math] formę:
[math] w_{n+1}(x)=(x+1)^2[\underbrace{x\,q(x)+r(x)}_{p(x)}]\; . \,[/math]Wyrażenie w nawiasach prostokątnych znów jest wielomianem, co oznacza, że otrzymaliśmy tezę indukcyjną, a tym samym zakończyliśmy dowód indukcyjny.
