Indukcja matematyczna – zadania (1–14)
1 Suma liczb naturalnych
Udowodnij metodą indukcji równość
\[ 1+2+3+\dots+n=\frac{n(n+1)}{2}. \]
Rozwiązanie
Dla \(n=1\): lewa strona to \(1\), a prawa \(\frac{1\cdot2}{2}=1\). Zatem równość jest prawdziwa dla \(n=1\).
Przyjmujemy, że dla pewnego \(n\ge 1\) równość już zachodzi, czyli
\[ 1+2+\dots+n=\frac{n(n+1)}{2}. \]
To jest założenie indukcyjne.
Dodajemy do obu stron kolejną liczbę \(n+1\):
\[ 1+2+\dots+n+(n+1)=\frac{n(n+1)}{2}+(n+1). \]
Wyłączamy \((n+1)\) przed nawias:
\[ \frac{n(n+1)}{2}+(n+1)=(n+1)\left(\frac{n}{2}+1\right)=(n+1)\cdot\frac{n+2}{2}. \]
Otrzymujemy
\[ 1+2+\dots+(n+1)=\frac{(n+1)(n+2)}{2}. \]
Skoro równość jest prawdziwa dla \(n=1\) i z prawdziwości dla \(n\) wynika prawdziwość dla \(n+1\), to zachodzi dla wszystkich \(n\in\mathbb{N}\).
2 Suma liczb nieparzystych
Udowodnij metodą indukcji równość
\[ 1+3+5+\dots+(2n-1)=n^2. \]
Rozwiązanie
Dla \(n=1\): lewa strona to \(1\), prawa to \(1^2\). Równość zachodzi.
Załóżmy, że dla pewnego \(n\ge 1\) mamy
\[ 1+3+\dots+(2n-1)=n^2. \]
Rozważmy sumę dla \(n+1\). Do dotychczasowej sumy dokładamy następny wyraz \(2n+1\):
\[ 1+3+\dots+(2n-1)+(2n+1)=n^2+(2n+1). \]
Wykonujemy rachunek:
\[ n^2+(2n+1)=n^2+2n+1=(n+1)^2. \]
Zatem
\[ 1+3+\dots+(2(n+1)-1)=(n+1)^2. \]
Wynika stąd, że równość zachodzi dla każdego \(n\in\mathbb{N}\).
3 Suma ułamków
Udowodnij metodą indukcji równość
\[ \frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\dots+\frac{1}{n(n+1)}=\frac{n}{n+1}. \]
Rozwiązanie
Dla \(n=1\):
\[ \frac{1}{1\cdot 2}=\frac12,\qquad \frac{1}{1+1}=\frac12. \]
Równość zachodzi.
Załóżmy, że dla pewnego \(n\ge 1\)
\[ \frac{1}{1\cdot 2}+\frac{1}{2\cdot 3}+\dots+\frac{1}{n(n+1)}=\frac{n}{n+1}. \]
Rozważamy sumę dla \(n+1\):
\[ \left(\frac{1}{1\cdot 2}+\dots+\frac{1}{n(n+1)}\right)+\frac{1}{(n+1)(n+2)}. \]
Korzystamy z założenia indukcyjnego:
\[ \frac{n}{n+1}+\frac{1}{(n+1)(n+2)}. \]
Sprowadzamy do wspólnego mianownika \((n+1)(n+2)\):
\[ \frac{n}{n+1}=\frac{n(n+2)}{(n+1)(n+2)}. \]
Zatem
\[ \frac{n(n+2)}{(n+1)(n+2)}+\frac{1}{(n+1)(n+2)} =\frac{n(n+2)+1}{(n+1)(n+2)}. \]
Upraszczenie licznika:
\[ n(n+2)+1=n^2+2n+1=(n+1)^2. \]
Ostatecznie:
\[ \frac{(n+1)^2}{(n+1)(n+2)}=\frac{n+1}{n+2}. \]
To jest dokładnie prawa strona dla \(n+1\), więc równość zachodzi dla wszystkich \(n\).
4 Nierówność z pierwiastkami
Udowodnij metodą indukcji nierówność
\[ \frac1{\sqrt{1}}+\frac1{\sqrt{2}}+\frac1{\sqrt{3}}+\dots+\frac1{\sqrt{n}}>\sqrt{n}, \quad \text{dla } n>1. \]
Rozwiązanie
Dla \(n=2\):
\[ \frac1{\sqrt{1}}+\frac1{\sqrt{2}}=1+\frac{1}{\sqrt2}. \]
Sprawdzamy, że \(1+\frac{1}{\sqrt2}>\sqrt2\). Wystarczy zauważyć, że
\[ 1+\frac{1}{\sqrt2}-\sqrt2=\frac{\sqrt2+1-2}{\sqrt2}=\frac{\sqrt2-1}{\sqrt2}>0. \]
Załóżmy, że dla pewnego \(n\ge 2\)
\[ \frac1{\sqrt{1}}+\frac1{\sqrt{2}}+\dots+\frac1{\sqrt{n}}>\sqrt{n}. \]
Oznaczmy lewą stronę przez \(S_n\).
Wtedy
\[ S_{n+1}=S_n+\frac{1}{\sqrt{n+1}}. \]
Z założenia mamy \(S_n>\sqrt{n}\), więc
\[ S_{n+1}>\sqrt{n}+\frac{1}{\sqrt{n+1}}. \]
Chcemy wykazać, że prawa strona jest co najmniej \(\sqrt{n+1}\), czyli że
\[ \sqrt{n}+\frac{1}{\sqrt{n+1}}\ge \sqrt{n+1}. \]
To równoważne nierówności
\[ \frac{1}{\sqrt{n+1}}\ge \sqrt{n+1}-\sqrt{n}. \]
Obliczamy różnicę pierwiastków (racjonalizacja):
\[ \sqrt{n+1}-\sqrt{n}=\frac{(n+1)-n}{\sqrt{n+1}+\sqrt{n}}=\frac{1}{\sqrt{n+1}+\sqrt{n}}. \]
Ponieważ \(\sqrt{n+1}+\sqrt{n}\ge \sqrt{n+1}\), więc
\[ \frac{1}{\sqrt{n+1}+\sqrt{n}}\le \frac{1}{\sqrt{n+1}}. \]
Czyli rzeczywiście \(\sqrt{n+1}-\sqrt{n}\le \frac{1}{\sqrt{n+1}}\).
Stąd \(S_{n+1}>\sqrt{n+1}\). Nierówność zachodzi dla wszystkich \(n>1\).
5 Suma kwadratów
Udowodnij metodą indukcji równość
\[ 1^2+2^2+3^2+\dots+n^2=\frac{n(n+1)(2n+1)}{6}. \]
Rozwiązanie
Dla \(n=1\):
\[ 1^2=1,\qquad \frac{1\cdot2\cdot3}{6}=1. \]
Załóżmy, że dla pewnego \(n\ge 1\)
\[ 1^2+2^2+\dots+n^2=\frac{n(n+1)(2n+1)}{6}. \]
Dodajemy \((n+1)^2\) do obu stron:
\[ 1^2+2^2+\dots+n^2+(n+1)^2=\frac{n(n+1)(2n+1)}{6}+(n+1)^2. \]
Wyłączamy \((n+1)\):
\[ \frac{n(n+1)(2n+1)}{6}+(n+1)^2 =(n+1)\left(\frac{n(2n+1)}{6}+n+1\right). \]
Sprowadzamy do wspólnego mianownika 6:
\[ \frac{n(2n+1)}{6}+n+1=\frac{n(2n+1)+6n+6}{6}=\frac{2n^2+7n+6}{6}. \]
Rozkładamy trójmian:
\[ 2n^2+7n+6=(2n+3)(n+2). \]
Zatem
\[ (n+1)\left(\frac{2n^2+7n+6}{6}\right) =(n+1)\cdot\frac{(2n+3)(n+2)}{6}. \]
To daje
\[ \frac{(n+1)(n+2)(2n+3)}{6}. \]
Jest to dokładnie wzór po podstawieniu \(n\mapsto n+1\), bo
\[ \frac{(n+1)((n+1)+1)(2(n+1)+1)}{6}=\frac{(n+1)(n+2)(2n+3)}{6}. \]
Zatem równość zachodzi dla wszystkich \(n\in\mathbb{N}\).
6 Podzielność przez 6: \(n^3-n\)
Udowodnij metodą indukcji, że liczba postaci
\[ n^3-n,\quad \text{gdzie } n\in\mathbb{N}, \]
jest podzielna przez \(6\).
Rozwiązanie
Dla \(n=1\): \(1^3-1=0\), a 0 jest podzielne przez 6.
Załóżmy, że dla pewnego \(n\ge 1\) liczba \(n^3-n\) jest podzielna przez 6, czyli istnieje całkowite \(k\) takie, że
\[ n^3-n=6k. \]
Sprawdźmy przypadek \(n+1\):
\[ (n+1)^3-(n+1)=n^3+3n^2+3n+1-n-1=(n^3-n)+3n^2+3n. \]
Wyłączamy \(3n\):
\[ (n+1)^3-(n+1)=(n^3-n)+3n(n+1). \]
Pierwszy składnik \((n^3-n)\) jest podzielny przez 6 (założenie). Pozostaje sprawdzić, że \(3n(n+1)\) jest podzielne przez 6.
Iloczyn \(n(n+1)\) jest zawsze parzysty, bo jedna z liczb \(n\) i \(n+1\) jest parzysta. Zatem istnieje całkowite \(m\) takie, że \(n(n+1)=2m\). Wtedy
\[ 3n(n+1)=3\cdot 2m=6m, \]
czyli \(3n(n+1)\) jest podzielne przez 6.
Suma dwóch liczb podzielnych przez 6 jest podzielna przez 6, więc \((n+1)^3-(n+1)\) jest podzielne przez 6. Teza zachodzi dla wszystkich \(n\).
7 Podzielność przez 6: \(10^n-4\)
Udowodnij metodą indukcji, że liczba postaci
\[ 10^n-4,\quad \text{gdzie } n\in\mathbb{N}, \]
jest podzielna przez \(6\).
Rozwiązanie
Dla \(n=1\): \(10^1-4=6\), więc jest podzielne przez 6.
Załóżmy, że dla pewnego \(n\ge 1\) liczba \(10^n-4\) jest podzielna przez 6, czyli istnieje całkowite \(k\) takie, że
\[ 10^n-4=6k. \]
Rozważmy \(n+1\):
\[ 10^{n+1}-4=10\cdot 10^n-4. \]
Dodajemy i odejmujemy \(40\):
\[ 10\cdot 10^n-4=10(10^n-4)+36. \]
Teraz korzystamy z założenia:
\[ 10(10^n-4)=10\cdot 6k=60k, \]
czyli jest podzielne przez 6. Ponadto \(36\) jest podzielne przez 6. Zatem suma jest podzielna przez 6.
Wynika stąd, że \(10^n-4\) jest podzielne przez 6 dla każdego \(n\in\mathbb{N}\).
8 Podzielność przez 3: \(n^3+2n\)
Udowodnij metodą indukcji, że liczba postaci
\[ n^3+2n,\quad \text{gdzie } n\in\mathbb{N}, \]
jest podzielna przez \(3\).
Rozwiązanie
Dla \(n=1\): \(1^3+2\cdot 1=3\), więc jest podzielne przez 3.
Załóżmy, że dla pewnego \(n\ge 1\) istnieje całkowite \(k\) takie, że
\[ n^3+2n=3k. \]
Sprawdzamy wyrażenie dla \(n+1\):
\[ (n+1)^3+2(n+1)=n^3+3n^2+3n+1+2n+2. \]
Grupujemy składniki:
\[ (n+1)^3+2(n+1)=(n^3+2n)+3n^2+3n+3. \]
Wyłączamy 3:
\[ (n+1)^3+2(n+1)=(n^3+2n)+3(n^2+n+1). \]
Pierwszy składnik jest podzielny przez 3 (założenie), drugi również. Suma także jest podzielna przez 3.
Teza zachodzi dla wszystkich \(n\in\mathbb{N}\).
9 Podzielność przez 10: \(3^{4n+2}+1\)
Udowodnij metodą indukcji, że liczba postaci
\[ 3^{4n+2}+1,\quad \text{gdzie } n\in\mathbb{N}, \]
jest podzielna przez \(10\).
Rozwiązanie
Dla \(n=1\):
\[ 3^{4\cdot 1+2}+1=3^6+1=729+1=730, \]
co kończy się na 0, więc jest podzielne przez 10.
Załóżmy, że dla pewnego \(n\ge 1\) liczba \(3^{4n+2}+1\) jest podzielna przez 10, czyli istnieje całkowite \(k\) takie, że
\[ 3^{4n+2}+1=10k. \]
Stąd
\[ 3^{4n+2}=10k-1. \]
Rozważmy \(n+1\):
\[ 3^{4(n+1)+2}+1=3^{4n+6}+1=3^4\cdot 3^{4n+2}+1. \]
Ponieważ \(3^4=81\), mamy
\[ 3^{4(n+1)+2}+1=81\cdot 3^{4n+2}+1. \]
Podstawiamy \(3^{4n+2}=10k-1\):
\[ 81(10k-1)+1=810k-81+1=810k-80. \]
Wyłączamy 10:
\[ 810k-80=10(81k-8). \]
Zatem liczba dla \(n+1\) też jest podzielna przez 10.
Wynika stąd, że \(3^{4n+2}+1\) jest podzielne przez 10 dla każdego \(n\).
10 Podzielność przez 9: \(4^n+15n-1\)
Udowodnij metodą indukcji, że liczba postaci
\[ 4^n+15n-1,\quad \text{gdzie } n\in\mathbb{N}, \]
jest podzielna przez \(9\).
Rozwiązanie
Dla \(n=1\):
\[ 4^1+15\cdot 1-1=4+15-1=18, \]
a 18 jest podzielne przez 9.
Załóżmy, że dla pewnego \(n\ge 1\) istnieje całkowite \(k\) takie, że
\[ 4^n+15n-1=9k. \]
Stąd
\[ 4^n=9k-15n+1. \]
Liczymy wyrażenie dla \(n+1\):
\[ 4^{n+1}+15(n+1)-1=4\cdot 4^n+15n+14. \]
Podstawiamy \(4^n=9k-15n+1\):
\[ 4(9k-15n+1)+15n+14=36k-60n+4+15n+14. \]
\[ =36k-45n+18. \]
Wyłączamy 9:
\[ 36k-45n+18=9(4k-5n+2). \]
Zatem \(4^{n+1}+15(n+1)-1\) jest podzielne przez 9.
Wynika stąd, że \(4^n+15n-1\) jest podzielne przez 9 dla każdego \(n\in\mathbb{N}\).
11 Suma ciągu geometrycznego
Wyprowadź metodą indukcji wzór na sumę \(n\) wyrazów ciągu geometrycznego.
Rozwiązanie
Niech ciąg geometryczny ma pierwszy wyraz \(a_1\) i iloraz \(q\). Wtedy
\[ a_1,\ a_1q,\ a_1q^2,\ \dots,\ a_1q^{n-1}. \]
Oznaczmy sumę \(n\) pierwszych wyrazów przez
\[ S_n=a_1+a_1q+\dots+a_1q^{n-1}. \]
Dla \(n=1\):
\[ S_1=a_1. \]
Wzór \(a_1\frac{1-q^1}{1-q}\) daje \(a_1\frac{1-q}{1-q}=a_1\), więc zgadza się.
Załóżmy, że dla pewnego \(n\ge 1\) zachodzi
\[ S_n=a_1\frac{1-q^n}{1-q}, \]
gdzie \(q\neq 1\).
Wtedy
\[ S_{n+1}=S_n+a_1q^n. \]
Podstawiamy wzór na \(S_n\):
\[ S_{n+1}=a_1\frac{1-q^n}{1-q}+a_1q^n. \]
Sprowadzamy do wspólnego mianownika \(1-q\):
\[ a_1q^n=a_1q^n\cdot\frac{1-q}{1-q}. \]
Zatem
\[ S_{n+1}=a_1\frac{1-q^n+q^n(1-q)}{1-q} =a_1\frac{1-q^n+q^n-q^{n+1}}{1-q} =a_1\frac{1-q^{n+1}}{1-q}. \]
Otrzymaliśmy wzór dla \(n+1\), więc dla \(q\neq 1\) jest prawdziwy dla wszystkich \(n\). Gdy \(q=1\), ciąg jest stały: \(a_k=a_1\), więc \(S_n=na_1\).
12 Suma ciągu arytmetycznego
Wyprowadź metodą indukcji wzór na sumę \(n\) wyrazów ciągu arytmetycznego.
Rozwiązanie
Niech \(a_1\) będzie pierwszym wyrazem, a \(r\) różnicą. Wtedy
\[ a_k=a_1+(k-1)r. \]
Sumę \(n\) pierwszych wyrazów oznaczamy przez
\[ S_n=a_1+a_2+\dots+a_n. \]
Teza ma postać
\[ S_n=\frac{n}{2}\bigl(2a_1+(n-1)r\bigr). \]
Dla \(n=1\):
\[ S_1=a_1,\qquad \frac{1}{2}(2a_1+0\cdot r)=a_1. \]
Załóżmy, że dla pewnego \(n\ge 1\)
\[ S_n=\frac{n}{2}\bigl(2a_1+(n-1)r\bigr). \]
Wtedy
\[ S_{n+1}=S_n+a_{n+1}. \]
Ale
\[ a_{n+1}=a_1+nr. \]
Zatem
\[ S_{n+1}=\frac{n}{2}(2a_1+(n-1)r)+a_1+nr. \]
Sprowadzamy do wspólnego mianownika 2:
\[ S_{n+1}=\frac{n(2a_1+(n-1)r)+2a_1+2nr}{2}. \]
Porządkujemy:
\[ n(2a_1+(n-1)r)+2a_1+2nr =2a_1(n+1)+r\bigl(n(n-1)+2n\bigr). \]
\[ n(n-1)+2n=n^2-n+2n=n^2+n=n(n+1). \]
Stąd
\[ S_{n+1}=\frac{2a_1(n+1)+rn(n+1)}{2} =\frac{n+1}{2}\bigl(2a_1+nr\bigr). \]
A to jest dokładnie wzór po podstawieniu \(n\mapsto n+1\):
\[ \frac{n+1}{2}\bigl(2a_1+((n+1)-1)r\bigr)=\frac{n+1}{2}(2a_1+nr). \]
Zatem wzór na sumę jest prawdziwy dla wszystkich \(n\).
13 Nierówność: \((a+b)^n\)
Wykazać, że jeśli \(a>0\), \(b>0\), \(n\in\mathbb{N}\), to
\[ (a+b)^n \le 2^{\,n-1}\bigl(a^n+b^n\bigr). \]
Rozwiązanie
Dla \(n=1\):
\[ (a+b)^1=a+b,\qquad 2^{0}(a^1+b^1)=a+b, \]
więc jest równość.
Załóżmy, że dla pewnego \(n\ge 1\)
\[ (a+b)^n \le 2^{n-1}(a^n+b^n). \]
Mnożymy obie strony przez dodatnie \(a+b\):
\[ (a+b)^{n+1}\le 2^{n-1}(a+b)(a^n+b^n). \]
Pokażemy teraz, że
\[ (a+b)(a^n+b^n)\le 2(a^{n+1}+b^{n+1}). \]
Rozpisujemy:
\[ (a+b)(a^n+b^n)=a^{n+1}+a^nb+ab^n+b^{n+1}. \]
Wystarczy więc wykazać, że
\[ a^nb+ab^n\le a^{n+1}+b^{n+1}. \]
To wynika z nierówności
\[ (a^n-b^n)(a-b)\ge 0, \]
bo po wymnożeniu mamy
\[ a^{n+1}-a^nb-ab^n+b^{n+1}\ge 0, \]
czyli
\[ a^{n+1}+b^{n+1}\ge a^nb+ab^n. \]
Wobec tego
\[ (a+b)^{n+1}\le 2^{n-1}\cdot 2(a^{n+1}+b^{n+1})=2^n(a^{n+1}+b^{n+1}), \]
czyli nierówność zachodzi dla \(n+1\).
Zatem nierówność jest prawdziwa dla wszystkich \(n\in\mathbb{N}\) oraz \(a>0\), \(b>0\).
14 Podzielność przez \(x^2-2x+1\)
Udowodnić metodą indukcji, że wielomian
\[ P_n(x)=n x^{n+1}-(n+1)x^{n}+1,\quad \text{gdzie } n\in\mathbb{N}, \]
jest podzielny przez trójmian \(\,x^2-2x+1\).
Rozwiązanie
Dla \(n=1\):
\[ P_1(x)=1\cdot x^2-2x+1=x^2-2x+1=(x-1)^2. \]
Zatem \(P_1(x)\) jest podzielny przez \((x-1)^2\).
Załóżmy, że dla pewnego \(n\ge 1\) wielomian \(P_n(x)\) jest podzielny przez \((x-1)^2\). Oznacza to, że istnieje wielomian \(Q_n(x)\) taki, że
\[ P_n(x)=(x-1)^2Q_n(x). \]
Obliczamy \(P_{n+1}(x)\):
\[ P_{n+1}(x)=(n+1)x^{n+2}-(n+2)x^{n+1}+1. \]
Rozważmy różnicę \(P_{n+1}(x)-xP_n(x)\). Najpierw zapiszmy \(xP_n(x)\):
\[ xP_n(x)=x\bigl(nx^{n+1}-(n+1)x^n+1\bigr)=nx^{n+2}-(n+1)x^{n+1}+x. \]
Odejmujemy:
\[ P_{n+1}(x)-xP_n(x) =\bigl((n+1)x^{n+2}-(n+2)x^{n+1}+1\bigr)-\bigl(nx^{n+2}-(n+1)x^{n+1}+x\bigr). \]
Porządkujemy współczynniki przy tych samych potęgach:
\[ =x^{n+2}-x^{n+1}+1-x. \]
Wyłączamy \(x-1\):
\[ x^{n+2}-x^{n+1}+1-x=x^{n+1}(x-1)-(x-1)=(x-1)(x^{n+1}-1). \]
Teraz pokazujemy, że \(x^{n+1}-1\) jest podzielne przez \(x-1\). Rzeczywiście, zachodzi wzór
\[ x^{n+1}-1=(x-1)(x^n+x^{n-1}+\dots+x+1). \]
Wobec tego \((x-1)(x^{n+1}-1)\) jest podzielne przez \((x-1)^2\).
Mamy więc:
\[ P_{n+1}(x)=xP_n(x)+(x-1)(x^{n+1}-1). \]
Z założenia \((x-1)^2\) dzieli \(P_n(x)\), więc dzieli także \(xP_n(x)\). Drugi składnik też jest podzielny przez \((x-1)^2\), więc suma również jest podzielna przez \((x-1)^2\).
Zatem \(P_{n+1}(x)\) jest podzielny przez \((x-1)^2\). Na mocy indukcji \(P_n(x)\) jest podzielny przez \((x-1)^2\), czyli przez \(x^2-2x+1\), dla wszystkich \(n\in\mathbb{N}\).
