Indukcja matematyczna
W tym rozdziale omówimy jeden ze sposobów dowodzenia twierdzeń dotyczących liczb naturalnych. Zasadę indukcji matematycznej opisuje poniższe twierdzenie.
Niech \(T(n)\) będzie formą zdaniową określoną w zbiorze \(\mathbb{N}\). Jeżeli
- zdanie \(T(n_0)\) jest prawdziwe dla pewnej liczby naturalnej \(n_0\) oraz
- z założenia, że zdanie \(T(k)\) jest prawdziwe, wynika prawdziwość zdania \(T(k+1)\), gdzie \(k\in \mathbb{N}\) oraz \(k\geq n_0\),
Metoda indukcji matematycznej stosowana jest często do udowodnienia wzorów postaci \(\alpha(n)=\beta(n)\), czyli do wykazania, że forma zdaniowa \[ T(n):\quad\alpha(n)=\beta(n) \] jest prawdziwa dla wszystkich liczb naturalnych \(n\geq n_0\). Zgodnie z zasadą indukcji matematycznej (pkt \(1\)) należy najpierw sprawdzić, czy zdanie \[ T(n_0):\quad\alpha(n_0)=\beta(n_0) \] jest prawdziwe, przekształcając prawą stronę \(P=\beta(n_0)\) tak, aby można było zauważyć, że jest ona równa lewej stronie \(L=\alpha(n_0)\). Następnie, zgodnie z pkt \(2\) zasady indukcji matematycznej, trzeba sformułować założenie indukcyjne \[ T(k):\quad \alpha(k)=\beta(k) \] oraz tezę indukcyjną \[ T(k+1):\quad \alpha(k+1)=\beta(k+1) \] dla \(k\in \mathbb{N}\) oraz \(k\geq n_0\). Wykorzystując założenie indukcyjne, udowadniamy tezę indukcyjną, najczęściej przekształcając lewą stronę \(L=\alpha(k+1)\) tak, aby otrzymać jej prawą stronę \(P=\beta(k+1)\). Spełnienie warunków \(1\) i \(2\) gwarantuje prawdziwość wzoru \(\alpha(n)=\beta(n)\) dla dowolnego \(n\geq n_0\).
Schemat dowodu indukcyjnego:- sprawdzamy prawdziwość zdania \(T(n_0)\),
- zapisujemy założenie indukcyjne \(T(k)\) oraz tezę indukcyjną \(T(k+1)\) i przeprowadzamy dowód \(T(k+1)\).
Przykład
Udowodnimy za pomoca indukcji matematycznej prawdziwość wzoru \[1+2+3+\ldots+n={n(n+1)\over 2}\] dla każdego \(n\in\mathbb{N}\).
- Sprawdzimy najpierw, czy wzór jest prawdziwy dla najmniejszej liczby naturalnej, czyli dla \(n_0=1\). Wstawiamy więc do lewej i prawej strony dowodzonego wzoru liczbę \(1\) w miejsce zmiennej \(n\) i otrzymujemy \[ \eqalign{ L&=1\cr P&={1\cdot (1+1) \over 2}=1\cr } \] Ponieważ \(L=P\), to dowodzony wzór jest prawdziwy dla \(n_0=1\).
- Zakładamy teraz, że dowodzony wzór jest prawdziwy dla liczby naturalnej \(k\), czyli formułujemy założenie indukcyjne. Wstawiamy więc do wzoru \[1+2+3+\ldots+n={n(n+1)\over 2}\] liczbę \(k\) w miejsce zmiennej \(n\) i otrzymujemy
założenie indukcyjne: \[\czerwony{\boldsymbol{ 1+2+3+\ldots+k={k(k+1)\over 2}}} \]
Tezą indukcyjną jest prawdziwość dowodzonego wzoru dla kolejnej liczby naturalnej, czyli dla \(k+1\). Wstawiamy więc do wzoru \[1+2+3+\ldots+n={n(n+1)\over 2}\] liczbę \(k+1\) w miejsce zmiennej \(n\) i otrzymujemy tezę indukcyjną: \[1+2+3+\ldots+(k+1)=\frac{(k+1)(k+2)}{2}\] Kolejnym krokiem jest udowodnienie zapisanej przez nas tezy indukcyjnej przy pomocy przyjętego założenia indukcyjnego. W tym celu przekształcimy lewą stronę tezy tak, aby widoczna była w niej lewa strona założenia.
Dowód: \[\eqalign{ L&=1+2+3+\ldots+(k+1)=1+2+3+\ldots+k+(k+1)=\cr &=\czerwony{\boldsymbol{\big[1+2+3+\ldots+k\big]}}+(k+1)\cr }\] Zastępujemy wyróżnioną lewą stronę założenia indukcyjnego prawą stroną tego założenia \[\eqalign{ L&=\czerwony{\boldsymbol{k(k+1)\over 2}}+k+1\cr }\] Ponieważ prawa strona tezy ma postać pojedynczego ułamka, sprowadzamy nasze ułamki do wspólnego mianownika \[\eqalign{ L&={k(k+1)\over 2}+{2(k+1)\over 2}={k(k+1)+2(k+1)\over 2}=\cr &={(k+1)(k+2)\over 2}=P\cr } \]
Za pomocą indukcji matematycznej udowodnimy, że \[n!\ge 2^{n-1}\] dla każdego \(n\in\mathbb{N}\).
- Sprawdzimy najpierw, czy nierówność jest prawdziwa dla najmniejszej liczby naturalnej, czyli dla \(n_0=1\). Wstawiamy więc do lewej i prawej strony dowodzonej nierówności liczbę \(1\) w miejsce zmiennej \(n\) i otrzymujemy \[ \eqalign{ L&=1!=1\cr P&=2^{1-1}=2^0=1\cr } \] Skoro \(L = P\), to nierówność \(L\ge P\) jest prawdziwa dla \(n_0=1\).
- Zakładamy teraz, że dowodzona nierówność jest prawdziwa dla liczby naturalnej \(k\), czyli formułujemy założenie indukcyjne. Wstawiamy więc do dowodzonej nierówności liczbę \(k\) w miejsce zmiennej \(n\) i otrzymujemy założenie indukcyjne: \[\czerwony{\boldsymbol{ k!\ge 2^{k-1}}} \]
Tezą indukcyjną jest prawdziwość dowodzonej nierówności dla kolejnej liczby naturalnej, czyli dla \(k+1\). Wstawiamy więc do dowodzonej nierówności liczbę \(k+1\) w miejsce zmiennej \(n\) i otrzymujemy tezę indukcyjną: \[ (k+1)!\ge 2^{k}\]
Kolejnym krokiem jest udowodnienie zapisanej przez nas tezy indukcyjnej przy pomocy przyjętego założenia indukcyjnego. W tym celu przekształcimy lewą stronę tezy tak, aby widoczna była w niej lewa strona założenia.
Dowód: Z definicji silni wiemy, że \(k!(k+1)=(k+1)!\), dlatego \[L=(k+1)!=\czerwony{\boldsymbol{k!}}(k+1)\] Zastępujemy wyróżnioną lewą stronę założenia indukcyjnego prawą stroną tego założenia. Ponieważ liczba \(k+1\) jest dodatnia, gdy \(k\in\mathbb{N}\), to nie zmieniamy przy tym kierunku nierówności. \[L=(k+1)!=\czerwony{\boldsymbol{k!}}(k+1)\geq \czerwony{\boldsymbol{2^{k}}}(k+1) \] Ponieważ dla liczby naturalnej \(k\geq 1\) liczba \(k+1\) jest nie mniejsza niż \(2\), to \[L\geq \czerwony{\boldsymbol{2^{k}}}(k+1)\geq 2^k\cdot 2=2^{k+1}=P\]
Za pomocą indukcji matematycznej udowodnimy, że dla każdego \(x>-1\) oraz \(n\in\mathbb{N}\) \[(1+x)^n\geq 1+nx\]
- Sprawdzimy najpierw, czy nierówność jest prawdziwa dla najmniejszej liczby naturalnej, czyli dla \(n_0=1\). \[ \eqalign{ L&=(1+x)^1=1+x\cr P&=1+1\cdot x=1+x\cr } \] Skoro \(L = P\), to nierówność \(L\ge P\) jest prawdziwa dla \(n_0=1\).
- Założenie indukcyjne: Zakładamy, że wzór jest prawdziwy dla \(n=k\), czyli \[\czerwony{\boldsymbol{(1+x)^k\geq 1+kx}} \]
Teza indukcyjna: Wzór
jest prawdziwy dla \(n=k+1\), tzn. \[ (1+x)^{k+1}\geq 1+(k+1)x\]
Dowód: Zastępujemy wyróżnioną lewą stronę założenia indukcyjnego prawą stroną tego założenia. Ponieważ przy założeniu, że \(x>-1\), liczba \(x+1\) jest dodatnia, to nie zmieniamy przy tym kierunku nierówności. \[L=(1+x)^{k+1}=\czerwony{\boldsymbol{(1+x)^k}}\cdot (1+x)\geq \czerwony{\boldsymbol{(1+kx)}} \cdot (1+x)=1+x+kx+kx^2\] Ponieważ dla liczby naturalnej \(k\) i liczby rzeczywistej \(x>-1\) liczba \(kx^2\) jest nieujemna, to \[L\geq 1+x+kx+kx^2\geq 1+x+kx=1+(k+1)x=P\]
Uwaga
Udowodniona powyżej nierówność \[\bigwedge_{x>-1}\ \bigwedge_{n\in\mathbb{N}} \ (1+x)^n\geq 1+nx\] nazywana jest nierównością Bernoulliego.
W analogiczny sposób można pokazać, że dla \(x>-1\) i \(x\neq 0\) oraz \(n\in\mathbb{N}\backslash\{1\}\) zachodzi nierówność ostra \[(1+x)^n> 1+nx\]
Zadanie
Udowodnij, że dla każdego \(n\in\mathbb{N}\) prawdziwa jest równość:
-
\(\displaystyle 1^2+2^2+3^2+\ldots +n^2={n(n+1)(2n+1)\over 6}\)Skorzystamy z zasady indukcji matematycznej.
- Sprawdzimy najpierw, czy wzór jest prawdziwy dla \(n_0=1\) \[ \eqalign{ L&=1^2=1\cr P&={1\cdot 2\cdot 3 \over 6}=1\cr } \] Ponieważ \(L=P\), zatem wzór jest prawdziwy dla \(n_0=1\).
- Założenie indukcyjne: Zakładamy, że wzór jest prawdziwy dla \(n=k\), czyli \[ \czerwony{\boldsymbol{1^2+2^2+3^2+\ldots +k^2={k(k+1)(2k+1)\over 6} }}\] Teza indukcyjna: Wzór jest prawdziwy dla \(n=k+1\), tzn. \[ 1^2+2^2+3^2+\ldots +(k+1)^2={(k+1)(k+2)(2k+3)\over 6} \] Dowód: Korzystając z założenia indukcyjnego w miejscu oznaczonym \(\czerwony{\boldsymbol{(\mathrm{z})}}\), udowodnimy tezę indukcyjną \[ \eqalign{ L&=1^2+2^2+3^2+\ldots +(k+1)^2=\cr &=\czerwony{\boldsymbol{\left[1^2+2^2+3^2+\ldots +k^2\right]}}+(k+1)^2 \buildrel \czerwony{\boldsymbol{(\mathrm{z})}} \over {=} \cr &=\czerwony{\boldsymbol{k(k+1)(2k+1)\over 6}} +(k+1)^2={k(k+1)(2k+1)\over 6} +{6(k+1)^2\over 6}=\cr &= {(k+1)[k(2k+1)+6(k+1)]\over 6}={(k+1)\left(2k^2+k+6k+6\right)\over 6}=\cr &={(k+1)\left(2k^2+7k+6\right)\over 6}={(k+1)\cdot 2(k+2)(k+{3\over 2})\over 6}=\cr &={(k+1)(k+2)(2k+3)\over 6}=P\cr } \]
-
\(\displaystyle {1\over 1\cdot 2}+{1\over 2\cdot 3}+{1\over 3\cdot 4}+\ldots +{1\over n(n+1)}={n\over n+1}\)Skorzystamy z zasady indukcji matematycznej.
- Dla \(n_0=1\) \[\eqalign{ L&={1\over 1\cdot 2}={1\over 2}\cr P&={1\over 2}\cr }\] Ponieważ \(L=P\), zatem wzór jest prawdziwy dla \(n_0=1\).
- Założenie indukcyjne: Dla \(n=k\) \[ \czerwony{\boldsymbol{{1\over 1\cdot 2}+{1\over 2\cdot 3}+{1\over 3\cdot 4}+\ldots +{1\over k(k+1)}={k\over k+1} }}\] Teza indukcyjna: Dla \(n=k+1\) \[ {1\over 1\cdot 2}+{1\over 2\cdot 3}+{1\over 3\cdot 4}+\ldots +{1\over (k+1)(k+2)}={k+1\over k+2} \] Dowód: \[ \eqalign{ L&={1\over 1\cdot 2}+{1\over 2\cdot 3}+{1\over 3\cdot 4}+\ldots +{1\over (k+1)(k+2)}=\cr &=\czerwony{\boldsymbol{\left[{1\over 1\cdot 2}+{1\over 2\cdot 3}+{1\over 3\cdot 4}+\ldots +{1\over k(k+1)}\right]}}+{1\over (k+1)(k+2)}\buildrel \czerwony{\boldsymbol{(\mathrm{z})}} \over {=} \cr &=\czerwony{\boldsymbol{k\over k+1}}+{1\over (k+1)(k+2)}={k(k+2)\over (k+1)(k+2)} +{1\over (k+1)(k+2)}=\cr &= {k^2+2k+1\over (k+1)(k+2)}={(k+1)^2\over (k+1)(k+2)}={k+1\over k+2}=P\cr } \]
-
\(\displaystyle 1^3+2^3+3^3+\ldots +n^3={n^2\left(n+1\right)^2\over 4}\)Skorzystamy z zasady indukcji matematycznej.
- Dla \(n_0=1\) \[ \eqalignno{ L&=1^3=1\cr P&={1^2\cdot 2^2 \over 4}=1\cr } \] Ponieważ \(L=P\), zatem wzór jest prawdziwy dla \(n_0=1\).
- Założenie indukcyjne: Dla \(n=k\) \[ \czerwony{\boldsymbol{1^3+2^3+3^3+\ldots +k^3={k^2\left(k+1\right)^2\over 4}}} \] Teza indukcyjna: Dla \(n=k+1\) \[ 1^3+2^3+3^3+\ldots +(k+1)^3={(k+1)^2\left(k+2\right)^2\over 4} \] Dowód: \[ \eqalign{ L&=1^3+2^3+3^3+\ldots +(k+1)^3=\cr &=\czerwony{\boldsymbol{\left[1^3+2^3+3^3+\ldots +k^3\right]}}+(k+1)^3 \buildrel \czerwony{\boldsymbol{(\mathrm{z})}} \over {=} \cr &=\czerwony{\boldsymbol{k^2\left(k+1\right)^2\over 4}} +(k+1)^3={k^2(k+1)^2\over 4} +{4(k+1)^3\over 4}=\cr &= {(k+1)^2[k^2+4(k+1)]\over 4}={(k+1)^2\left(k^2+4k+4\right)\over 4}=\cr &={(k+1)^2(k+2)^2\over 4}=P\cr } \]
Zadanie
Udowodnij, że dla każdego \(n\in\mathbb{N}\) prawdziwa jest nierówność:
-
\(2+3^n\geq 2^n+3\)Skorzystamy z zasady indukcji matematycznej.
- Sprawdzimy najpierw, czy nierówność jest prawdziwa dla najmniejszej liczby naturalnej, czyli dla \(n_0=1\). \[\eqalign{ L&=2+3^1=5\cr P&=2^1+3=5\cr }\] Skoro \(L=P\), to nierówność \(L\geq P\) jest prawdziwa dla \(n_0=1\).
- Założenie indukcyjne: Dla \(n=k\) \[2+3^k\geq 2^k+3 \quad \Longleftrightarrow\quad \czerwony{\boldsymbol{3^k\geq 2^k+1}}\] Teza indukcyjna: Dla \(n=k+1\) \[ 2+3^{k+1}\geq 2^{k+1}+3\] Dowód: \[ \eqalign{ L&=2+3^{k+1}=2+\czerwony{\boldsymbol{3^k}}\cdot 3 \overset{\czerwony{\boldsymbol{(\mathrm{z})}}}{\geq} 2+\czerwony{\boldsymbol{\left(2^k+1\right)}}\cdot 3=2+2^k\cdot 3+3\geq 2^k\cdot 2+3=2^{k+1}+3=P\cr } \]
-
\(\displaystyle \frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\dots+\frac{1}{\sqrt{n}}\geq\sqrt{n}\)Skorzystamy z zasady indukcji matematycznej.
- Sprawdzimy najpierw, czy nierówność jest prawdziwa dla najmniejszej liczby naturalnej, czyli dla \(n_0=1\). \[\eqalign{ L&=\frac{1}{\sqrt{1}}=1\cr P&=\sqrt{1}=1\cr }\] Skoro \(L=P\), to nierówność \(L\geq P\) jest prawdziwa dla \(n_0=1\).
- Założenie indukcyjne: Dla \(n=k\) \[\czerwony{\boldsymbol{\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\dots+\frac{1}{\sqrt{k}}\geq\sqrt{k}}}\] Teza indukcyjna: Dla \(n=k+1\) \[\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\dots+\frac{1}{\sqrt{k+1}}\geq\sqrt{k+1}\] Dowód: \[ \eqalign{ L&=\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\dots+\frac{1}{\sqrt{k+1}}=\cr &=\czerwony{\boldsymbol{\frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+\dots+\frac{1}{\sqrt{k}}}}+\frac{1}{\sqrt{k+1}} \overset{\czerwony{\boldsymbol{(\mathrm{z})}}}{\geq} \czerwony{\boldsymbol{\sqrt{k}}}+\frac{1}{\sqrt{k+1}}=\cr &=\frac{\sqrt{k}\cdot \sqrt{k+1}+1}{\sqrt{k+1}}\geq \frac{\sqrt{k}\cdot \sqrt{k}+1}{\sqrt{k+1}}=\frac{k+1}{\sqrt{k+1}}=\sqrt{k+1}= P\cr } \]
-
\(\displaystyle 1+\frac{1}{2^2}+\frac{1}{3^2}+\dots+\frac{1}{n^2}\leq 2-\frac{1}{n}\)Skorzystamy z zasady indukcji matematycznej.
- Sprawdzimy najpierw, czy nierówność jest prawdziwa dla najmniejszej liczby naturalnej, czyli dla \(n_0=1\). \[\eqalign{ L&=1\cr P&=2-\frac{1}{1}=1\cr }\] Skoro \(L=P\), to nierówność \(L\leq P\) jest prawdziwa dla \(n_0=1\).
- Założenie indukcyjne: Dla \(n=k\) \[1+\frac{1}{2^2}+\frac{1}{3^2}+\dots+\frac{1}{k^2}\leq 2-\frac{1}{k}\] Teza indukcyjna: Dla \(n=k+1\) \[1+\frac{1}{2^2}+\frac{1}{3^2}+\dots+\frac{1}{(k+1)^2}\leq 2-\frac{1}{k+1}\] Dowód: \[ \eqalign{ L&=1+\frac{1}{2^2}+\frac{1}{3^2}+\dots+\frac{1}{(k+1)^2}=\cr &=\czerwony{\boldsymbol{1+\frac{1}{2^2}+\frac{1}{3^2}+\dots+\frac{1}{k^2}}}+ \frac{1}{(k+1)^2}\overset{\czerwony{\boldsymbol{(\mathrm{z})}}}{\leq} \czerwony{\boldsymbol{2-\frac{1}{k}}}+ \frac{1}{(k+1)^2}=\cr &=2-\left[\frac{(k+1)^2}{k(k+1)^2}-\frac{k}{k(k+1)^2}\right]=2-\frac{k^2+2k+1-k}{k(k+1)^2} =\cr &=2-\frac{k^2+k+1}{k(k+1)^2}\leq 2-\frac{k^2+k}{k(k+1)^2}=2-\frac{k(k+1)}{k(k+1)^2}= 2-\frac{1}{k+1}=P\cr } \]
Zadanie
Udowodnij, że dla każdego \(n\in\mathbb{N}\):
-
liczba \(10^n-1\) jest podzielna przez \(9\)Skorzystamy z zasady indukcji matematycznej.
- Ponieważ dla \(n_0=1\) liczba \(10^n-1=10^1-1=9\) jest podzielna przez \(9\), więc zdanie jest prawdziwe dla \(n_0=1\).
- Założenie indukcyjne: Załóżmy, że zdanie jest prawdziwe dla \(n=k\), tzn. liczba \(10^k-1\) jest podzielna przez \(9\). Oznacza to, że można ją zapisać w postaci \[10^k-1=9p, \quad \text{gdzie}\quad p\in\mathbb{Z},\] stąd \[\czerwony{\boldsymbol{10^k=1+9p}}, \quad \text{gdzie}\quad p\in\mathbb{Z}\] Teza indukcyjna: Zdanie jest prawdziwe dla \(n=k+1\), czyli istnieje taka liczba całkowita \(q\), że \[10^{k+1}-1=9q\] Dowód: Szukamy odpowiedniej liczby całkowitej \(q\) \[\eqalign{ L&=10^{k+1}-1=\czerwony{\boldsymbol{10^k}}\cdot 10-1 \overset{\czerwony{\boldsymbol{(\text{z})}}}{=} \czerwony{\boldsymbol{(1+9p)}}\cdot 10-1=10+90p-1=\cr &=90p+9=9\underbrace{(10p+1)}_{q}=P\cr }\] Przyjmujemy za \(q=10p+1\). Ponieważ \(p\) jest liczba całkowitą, to otrzymujemy \(q\in\mathbb{Z}\), dla którego \(L=P\).
-
liczba \(11^{n+2}+12^{2n+1}\) jest podzielna przez \(133\)Skorzystamy z zasady indukcji matematycznej.
- Dla \(n_0=1\) liczba \(11^{n+2}+12^{2n+1}\) jest równa \[11^3+12^3=1331+1728=3059=23\cdot 133,\] co oznacza, że jest ona podzielna przez \(133\), więc zdanie jest prawdziwe dla \(n_0=1\).
- Założenie indukcyjne: Załóżmy, że zdanie jest prawdziwe dla \(n=k\), tzn. liczba \(11^{k+2}+12^{2k+1}\) jest podzielna przez \(133\). Oznacza to, że można ją zapisać w postaci \[11^{k+2}+12^{2k+1}=133 p, \quad \text{gdzie}\quad p\in\mathbb{Z},\] stąd \[\czerwony{\boldsymbol{11^{k+2}=133 p -12^{2k+1}}}, \quad \text{gdzie}\quad p\in\mathbb{Z}\] Teza indukcyjna: Zdanie jest prawdziwe dla \(n=k+1\), czyli istnieje taka liczba całkowita \(q\), że \[11^{k+3}+12^{2k+3}=133q\] Dowód: Szukamy odpowiedniej liczby całkowitej \(q\) \[\eqalign{ L&= 11^{k+3}+12^{2k+3}=\czerwony{\boldsymbol{11^{k+2}}}\cdot 11 + 12^{2k+3} \overset{\czerwony{\boldsymbol{(\text{z})}}}{=} \cr &\overset{\czerwony{\boldsymbol{(\text{z})}}}{=}\czerwony{\boldsymbol{\left(133 p -12^{2k+1}\right)}}\cdot 11 + 12^{2k+3}=\cr &=11\cdot 133 p - 11\cdot 12^{2k+1} + 12^{2k+3}=\cr &=11\cdot 133 p - 11\cdot 12^{2k+1} + 12^{2k+1}\cdot 12^2=\cr &=11\cdot 133 p - 11\cdot 12^{2k+1} + 12^{2k+1}\cdot 144=\cr &=11\cdot 133 p + 12^{2k+1}\cdot (144-11)=\cr &=11\cdot 133 p + 133\cdot 12^{2k+1}=\cr &=133\underbrace{\left(11 p + 12^{2k+1}\right)}_{q}=P }\] Przyjmujemy \(q=11\cdot p + 12^{2k+1}\). Ponieważ \(p\) i \(k\) są liczbami całkowitymi, to otrzymujemy \(q\in\mathbb{Z}\), dla którego \(L=P\).
-
liczba \(n^3-n\) jest podzielna przez \(6\)Skorzystamy z zasady indukcji matematycznej.
- Ponieważ dla \(n_0=1\) liczba \(n^3-n=1^3-1=0\) jest podzielna przez \(6\), więc zdanie jest prawdziwe dla \(n_0=1\).
- Założenie indukcyjne: Załóżmy, że zdanie jest prawdziwe dla \(n=k\), tzn. liczba \(k^3-k\) jest podzielna przez \(6\). Oznacza to, że można ją zapisać w postaci \[k^3-k=6 p, \quad \text{gdzie}\quad p\in\mathbb{Z}\] skąd \[\czerwony{\boldsymbol{k^3=k+6 p}}, \quad \text{gdzie}\quad p\in\mathbb{Z}\] Teza indukcyjna: Zdanie jest prawdziwe dla \(n=k+1\), czyli istnieje taka liczba całkowita \(q\), że \[(k+1)^3-(k+1)=6 q\]Dowód: Wyznaczamy odpowiednią liczbę całkowitą \(q\) \[\eqalign{ L&=(k+1)^3-(k+1)=\left(k^3+3k^2+3k+1\right) -k-1=\czerwony{\boldsymbol{k^3}}+3k^2 +2k \overset{\czerwony{\boldsymbol{(\text{z})}}}{=}\cr &\overset{\czerwony{\boldsymbol{(\text{z})}}}{=} \czerwony{\boldsymbol{k+6 p}} +3k^2 +2k=3k^2+3k+6 p=3(k^2+k)+6 p=\cr &=3k(k+1) +6p=6\cdot {k(k+1)\over 2}+6p=6\underbrace{\left[{k(k+1)\over 2}+p\right]}_{q}=P\cr }\] Ponieważ \(k(k+1)\) jest iloczynem dwóch kolejnych liczb naturalnych, więc jedna z nich jest parzysta. Zatem liczba \(k(k+1)\) jest parzysta, a liczba \({k(k+1)\over 2}\) jest liczbą naturalną. Dodatkowo \(p\in\mathbb{Z}\), więc \(q={k(k+1)\over 2}+p\) jest liczbą całkowitą, dla której \(L=P\).
-
liczba \(n^7-n\) jest podzielna przez \(7\)Skorzystamy z zasady indukcji matematycznej.
- Ponieważ dla \(n_0=1\) liczba \(n^7-n=1^7-1=0\) jest podzielna przez \(7\), więc zdanie jest prawdziwe dla \(n_0=1\).
- Założenie indukcyjne: Załóżmy, że zdanie jest prawdziwe dla \(n=k\), tzn. liczba \(k^7-k\) jest podzielna przez \(7\). Oznacza to, że można ją zapisać w postaci \[k^7-k=7p, \quad \text{gdzie}\quad p\in\mathbb{Z},\] skąd \[\czerwony{\boldsymbol{k^7=k+7 p}}, \quad \text{gdzie}\quad p\in\mathbb{Z}\]Teza indukcyjna: Zdanie jest prawdziwe dla \(n=k+1\), czyli istnieje liczba całkowita \(q\) taka, że \[(k+1)^7-(k+1)=7q\] Dowód: Wyznaczamy odpowiednią liczbę całkowitą \(q\) \[\eqalign{ L&=(k+1)^7-(k+1)=\cr &=\left(\czerwony{\boldsymbol{k^7}}+7k^6+21k^5+35k^4+35k^3+21k^2+7n+1\right) -k-1 \overset{\czerwony{\boldsymbol{(\text{z})}}}{=}\cr &\overset{\czerwony{\boldsymbol{(\text{z})}}}{=} \czerwony{\boldsymbol{k+7\cdot p} }+7k^6+21k^5+35k^4+35k^3+21k^2+6k=\cr &=7\cdot p +7k^6+21k^5+35k^4+35k^3+21k^2+7k=\cr &=7\underbrace{\left(p +k^6+3k^5+5k^4+5k^3+3k^2+k\right)}_{q}=P\cr }\] Przyjmujemy \(q=p +k^6+3k^5+5k^4+5k^3+3k^2+k\). Ponieważ \(p\) i \(k\) są liczbamy całkowitymi, to otrzymujemy \(q\in \mathbb{Z}\), dla którego \(L=P\).