MaA 11 Talteori och bevis

10. Induktionsbevis

Iduktionsbevis är en form av bevisföring som vi använder då vi till exempel bevisar att en formel gäller. Tanken bakom bevisföringen är att vi först testar att formeln stämmer sedan visar vi att den stämmer på ett allmänt sätt.

Visa att summan av \( 0 + 1 + 2 + 3 + \ldots + n = \dfrac{n(n+1)}{2} \).

Vi har härlett formeln i kursen MaG då vi behandlade aritmetisk summa. Men hur visar vi att den stämmer utan att härleda den på nytt?

Vi visar att formeln bestämmer med hjälp av induktion. Först tar vi och testar att den fungear (grundsteget), sedan tar vi och visar att den fungerar allmänt (induktionssteget).

Grundsteget: Vi testar formeln med \( n = 1 \).

Vi får \( 0 + 1 = 1 \) och \( \dfrac{1(1+1)}{2} = 1 \). Formlen tycks stämma.

Induktionssteget: Vi använder oss av \( k + 1 \).

Då får vi \( 0 + 1 + 2 + \ldots + k + (k + 1) \) som vi skall visa att är samma som \( \dfrac{(k+1)(k+1+1)}{2} = \dfrac{(k+1)(k+2)}{2} = \dfrac{k^2+3k+2}{2} \).

Eftersom \( 0 + 1 + 2 + \ldots + k = \dfrac{k(k+1)}{2} \) är \( 0 + 1 + 2 + \ldots + k + (k + 1) = \dfrac{k(k+1)}{2} + ^{2)}(k+1) = \\ \dfrac{k(k+1)}{2} + \dfrac{2(k+1)}{2} = \dfrac{k^2+k+2k+2}{2} = \dfrac{k^2+3k+2}{2} \)

Då har vi visat att \( 0 + 1 + 2 + 3 + \ldots + n = \dfrac{n(n+1)}{2} \).

Då vi bevisar med hjälp av induktion testar vi först att formeln/påståendet stämmer. Detta steg kallar vi för grundsteget. Sedan tar vi och visar allmänt med ett mera än vad som finns i formeln. Detta kallar vi för induktionssteget.

Exempel 1 Bevisa med induktion att \( \displaystyle \sum_{k=0}^n k\cdot 2^k = (n-1)2^{n+1} + 2 \) då \( n \in \mathbf{N} \).

Lösning

Grundsteget: Vi testar med \( n = 1 \). Vi får \( 0 \cdot 2^0 + 1 \cdot 2^1 = 2 \) och \( (1-1)2^{1+1} + 2 = 0 + 2 = 2 \). Formeln tycks stämma.

Induktionssteget: Vi använder oss av \( k + 1 \). Då skall vi visa att \( \displaystyle \sum_{k=0}^{k+1} k \cdot 2^k = (k+1-1)2^{k+1+1}+2 = k \cdot 2^{k+2} +2 \).

Vi delar upp räkningarna.

\( \begin{array}{rcl} \displaystyle \sum_{k=0}^{k+1} k \cdot 2^k & = & \underbrace{0 \cdot 2^0 + 1\cdot 2^1 + k\cdot 2^k}_{\displaystyle\sum_{k=0}^{k} k \cdot 2^k} + (k+1) \cdot 2^{k+1} \\ & = & \displaystyle\sum_{k=0}^{k+1} k \cdot 2^k + (k+1) \cdot 2^{k+1} \\ & = & (k-1)2^{k+1} + 2 + (k+1) \cdot 2^{k+1} \\ & = & (k-1+k+1)2^{k+1} +2 \\ & = & 2k\cdot 2^{k+1} +2 \\ & = & k \cdot 2^{k+2} +2 \\ \end{array} \)

Vilket är det som vi skulle visa. Alltså stämmer formeln.

Exempel 2 Visa att \( 2^n \geq n^2 \) när \( n \in \mathbf{N} \) och \( n \geq 4 \).

Lösning

Grundsteget: Vi testar med \( n = 4 \). \( 2^4 = 16 \) och \( 4^2 = 16 \).

Formeln tycks stämma.

Induktionssteget: Vi använder oss av \( k + 1 \). Då skall vi visa att \( 2^{k+1} > (k+1)^2 \).

Vi gör som följande, observera att vi har ett större än tecken som vi jobbar med.

\( \begin{array}{rcl} 2^{k+1} & = & 2^k \cdot 2 \\ & > & k^2 \cdot 2 = 2k^2 = k^2 + k^2 \\ & \geq & k^2 + 5k = k^2 + 4k + k \\ & > & k^2 + 4k + 1 = (k+1)^2 \\ \end{array} \)

Eftersom grundsteget och induktionssteget stämmer stämmer det ursprungliga påståendet.

I exemplet ovan är ett typexempel över matematisk bevsiföring där man börjar med något \( 2^{k+1} \) och sedan skall man komma fram till något annat \( (k+1)^2 \). I praktiken börjar man från början, sedan räknar man från slutet och sedan försöker man få början och slutet att passa ihop.

Uppgifter

  1. Visa att \( 1 + 5 + 9 + \ldots + (4n+1) = (n+1)(2n+1) \) för \( n = 0, 1,2, \ldots \).

    Grundsteget: Vi testar med \( n = 0 \). Vi får \( (4\cdot 0 + 1) = 1 \) och \( (0+1)(2\cdot 0 + 1) = 1 \).

    Använder vi oss av \( n = 1 \) får vi \( (4\cdot 0 + 1) + (4\cdot 1 + 1) = 6 \) och \( (1+1)(2\cdot 1 + 1) = 6 \).

    Använder vi oss av \( n = 2 \) får vi \( (4\cdot 0 + 1) + (4\cdot 1 + 1) + (4\cdot 2 + 1) = 15 \) och \( (2+1)(2\cdot 2 + 1) = 15 \).

    Formeln tycks stämma. (Du väljer ett tal för \( n \).)

    Induktionssteget: vi använder oss av \( k + 1 \).

    Vi skall komma fram till \( (k+1+1)(2(k+1)+1) = (k+2)(2k+3) = 2k^2 + 7k + 6\).

    Vi får

    \( \begin{array}{rcl} 1 + 5 + \ldots + (4k+1) + (4(k+1)+1) & = & (k+1)(2k+1) + (4(k+1)+1) \\ & = & (k+1)(2k+1) + (4k+5) \\ & = & 2k^2 + 7k + 6 \\ \end{array} \)

    Alltså stämmer formeln.

  2. Bevisa med induktion att \( \displaystyle \sum_{k=0}^{n} k^3 = \dfrac{n^2(n+1)^2}{4} \).

    Grundsteget: vi testar med \( n = 1 \). Vi får \( 0^3 + 1^3 = 1 \) och \( \dfrac{1^2(1+1)^2}{4} = \dfrac{1\cdot 2^2}{4} = 1 \).

    Formeln tycks stämma.

    Induktionssteget: vi använder oss av \( k + 1 \).

    Vi skall komma fram till \( \dfrac{(k+1)^2(k+1+1)^2}{4} = \dfrac{k^4 + 6k^3 + 13k^2 + 12k + 4}{4} \).

    Vi får

    \( \begin{array}{rcl} 0^3 + 1^3 + \ldots k^3 + (k+1)^3 & = & \dfrac{k^2(k+1)^2}{4} + ^{4)}(k+1)^3 \\ & = & \dfrac{k^2(k+1)^2+4(k+1)^3}{4} \\ & = & \dfrac{k^4 + 6k^3 + 13k^2 + 12k + 4}{4} \\ \end{array} \)

    Alltså stämmer formeln.

  3. Antag att \( q \not=1 \). Bevisa med induktion att \( \displaystyle\sum_{k=0}^{n} q^k = \dfrac{1-q^{n+1}}{1-q} \) då \( n \in \mathbf{N} \).

    Grundsteget: Vi testar med \( n = 0 \). Vi får \( q^0 = 1 \) och \( \dfrac{1-q^{0+1}}{1-q} = \dfrac{1-q}{1-q} = 1\). Formeln tycks stämma.

    Induktionssteget: Vi jobbar med \( k +1 \).

    Vi skall komma fram till \( \dfrac{1-q^{k+1+1}}{1-q} = \dfrac{1-q^{k+2}}{1-q} \)

    Vi får

    \( \begin{array}{rcl} q^0 + q^1 + \ldots + q^k + q^{k+1} & = & \dfrac{1-q^{k+1}}{1-q} + ^{1-q)}q^{k+1} \\ & = & \dfrac{1-q^{k+1} + q^{k+1}(1-q)}{1-q} \\ & = & \dfrac{1-q^{k+1} + q^{k+1} -q^{k+2}}{1-q} \\ & = & \dfrac{1-q^{k+2}}{1-q} \\ \end{array} \)

    Formeln stämmer.

  4. Bevisa med induktion att \( 1^2 + 2^2 + 3^2 + \ldots + n^2 > \dfrac{n^3}{3} \) då \( n \in \mathbf{Z}_+ \).

    Grundsteget: vi testar med \( n = 1 \). Vi får \( 1^2 = 1 \) och \( \dfrac{1^3}{3} = \dfrac{1}{3} \)

    Formeln tycks stämma.

    Induktionssteget: vi använder oss av \( k + 1 \).

    Vi skall komma fram till \( \dfrac{(k+1)^3}{3} = \dfrac{k^3+3k^2+3k+1}{3}\).

    Vi får

    \( \begin{array}{rcl} 1^2 + 2^2 + \ldots +k^2 + (k+1)^2 & > & \dfrac{k^3}{3} + ^{3)}(k+1)^2 \\ & = & \dfrac{k^3 + 3(k+1)^2}{3} \\ & = & \dfrac{k^3 + 3k^2 + 6k + 3}{3} \\ & > & \dfrac{k^3+3k^2+3k+1}{3} \\ & = & \dfrac{(k+1)^3}{3} \\ \end{array} \)

    Alltså stämmer formeln.

  5. Bevisa med induktion att \( 1^2 + 2^2 + 3^2 + \ldots + (n-1)^2 < \dfrac{n^3}{3} \) då \( n \in \mathbf{Z}_+ \).

    Grundsteget: vi testar med \( n = 1 \). Vi får \( (1-1)^2 = 0 \) och \( \dfrac{1^3}{3} = \dfrac{1}{3} \)

    Formeln tycks stämma.

    Induktionssteget: vi använder oss av \( k + 1 \).

    Vi skall komma fram till \( \dfrac{(k+1)^3}{3} = \dfrac{k^3+3k^2+3k+1}{3}\).

    Vi får

    \( \begin{array}{rcl} 1^2 + 2^2 + \ldots +(k-1)^2 + (k+1-1)^2 & < & \dfrac{k^3}{3} + ^{3)}k^2 \\ & = & \dfrac{k^3+3k^2}{3} \\ & < & \dfrac{k^3+3k^2+3k+1}{3} \\ & = & \dfrac{(k+1)^3}{3} \\ \end{array} \)

    Alltså stämmer formeln.

  6. Visa att \( n! > 2^n \) då \( n \in \mathbf{N} \) och \( n \geq 4 \).

    Notationen ! betyder fakultet. För \( 4! = 1 \cdot 2 \cdot 3 \cdot 4 \).

    Grundsteget: vi testar med \( n = 4 \). Vi får \( 4! = 24 \) och \( 2^4 = 16 \)

    Formeln tycks stämma.

    Induktionssteget: vi använder oss av \( k + 1 \).

    Vi skall komma fram till \( 2^{k+1} \).

    Vi får

    \( \begin{array}{rcll} 1 \cdot 2 \cdot 3 \cdot \ldots \cdot k \cdot k+1 & > & 2^k \cdot (k+1) & \mid \text{ Vi utnyttjar } k+1 > 2\\ & > & 2^k \cdot 2 \\ & = & 2^{k+1} \\ \end{array} \)

    Alltså stämmer formeln.

  7. Bestäm sista siffran i talet \( 5^{123456} \) med hjälp av induktion.

    Vi visar först med hjälp av induktion att \( 5^k \equiv 5 ( \mod 10 ) \) för alla positiva heltal.

    Grundsteget: \( 5^1 \equiv 5 (\mod 10) \).

    Induktonssteget: Vi får \( 5^{k+1} = 5^k \cdot 5 \equiv 5 \cdot 5 \equiv 5 (\mod 10) \).

    Alltså gäller att \( 5^k \equiv 5 ( \mod 10 ) \) för alla positiva heltal.

    Då gäller också att \( 5^{123456} \equiv 5 (\mod 10) \). Så sista siffran är 5.

  8. Bevisa Aritmetiskens fundamentalsats, att varje heltal som är större än 1 kan entydigt skrivas som en produkt av primtal.

    Vi bevisar satsen med hjälp av induktion.

    Grundsteget: Då \( n = 2 \) gäller att primtalsfaktoriseringen är 1 och 2 eftersom 2 är ett primtal.

    Induktionssteget: Vi skriver \( k +1 \) som en produkt av primtal.

    Om talet \( k +1 \) är ett primtal är dess primtalsfaktorisering talet \( k +1 \) självt.

    Om talet \( k +1 \)in är ett primtal kan vi skriva det i formen \( k + 1 = ab \) är \( 2 \leq a < k \) och \( 2 \leq b < k \).

    Enligt induktionsatagandet kan \( a \) och \(b \) skrivas som produkter av primtal, \( a = a_1\cdot a_2 \cdot \ldots \cdot a_i \) och \( b = b_1\cdot b_2 \cdot \ldots \cdot b_i \).

    Men då kan vi skriva \( k+1 \) som en produkt av primtal, \( k+1 = ab = a_1\cdot a_2 \cdot \ldots \cdot a_i \cdot b_1\cdot b_2 \cdot \ldots \cdot b_i \).

    Alltså gäller induktionsantagandet.

    Alltså stämmer satsen.

  9. Bevisa Bernoullis olikhet, \( (1+x)^n \geq 1 + nx \), där \( x > -1 \) och \( n \in \mathbf{N} \).

    Vi bevisar den med induktion.

    Grundsteget: Vi testar med \( n = 0 \). Vi får \( (1+x)^0 = 1 \) och \( 1 + 0 \cdot x = 1\). Påståendet tycks stämma.

    Induktionssteget: Vi jobbar med \( k +1 \). Vi får då

    \( \begin{array}{rcl} (1+x)^{k+1} & = & (1+x)^k (1+x) \\ & \leq & (1+kx)(1+x) \\ & = & 1+x+kx+kx^2 \\ & \leq & 1 + x + kx \\ & = & 1 + (k+1)x \\ \end{array} \)

    Vilket var det vi skulle komma fram till. Satsen stämmer.