Das Induktionsprinzip

(Induktion) Für jede induktive Teilmenge $\Bbb$T $\subset$ $\mbox{$\mathbb{N}$}$ gilt: Ist eine Zahl a $\in$ $\Bbb$T, so sind alle Zahlen b$\ge$a in $\Bbb$T.

Lösungen:

1. 1. Sei

      $$\mathbb {T} \left\{\vphantom{k\vert k\in \mbox{$\mathbb{N}$}\text{ und } 0\cdot 0!+ \dots +k\cdot k!=(k+1)!-1}\right. \in \mbox{$\mathbb{N}$} \left.\vphantom{k\vert k\in \mbox{$\mathbb{N}$}\text{ und } 0\cdot 0!+ \dots +k\cdot k!=(k+1)!-1}\right\}$$

      
      
      Es ist 0 $\in$ $\mathbb {T}$, denn 0 ^. 0! = 1! - 1.

      Sei k $\in$ $\mathbb {T}$. Dann ist:
      

      0 ^. 0! + ... + k ^. k! = (k + 1)! - 1

      0 ^. 0! + ... + k ^. k! + (k + 1)(k + 1)! = (k + 1)! - 1 + (k + 1)(k + 1)!

      0 ^. 0! + ... + k ^. k! + (k + 1)(k + 1)! = (k + 1)!(k + 2) - 1

      0 ^. 0! + ... + k ^. k! + (k + 1)(k + 1)! = (k + 2)! - 1

      
      Also ist $\mathbb {T}$ induktiv und daher ist $\mathbb {T}$ = $\mbox{$\mathbb{N}$}$.
   2. Wieder sei

      $$\mathbb {T} \left\{\vphantom{k\vert+1+\dots+k = \displaystyle\frac{(k+1)\cdot k}{2}}\right. {\frac{{(k+1)\cdot k}}{{2}}} \left.\vphantom{k\vert+1+\dots+k = \displaystyle\frac{(k+1)\cdot k}{2}}\right\}$$

      
      
      Es ist 0 = $${\frac{{1\cdot 0}}{{2}}}$$. Also ist 0 $\in$ $\mathbb {T}$. Sei k $\in$ $\mathbb {T}$. Man erhält:
      

      $${\frac{{(k+1)\cdot k}}{{2}}}$$ 1 + ... + k =

      $${\frac{{(k+1)\cdot k}}{{2}}} {\frac{{(k+1)\cdot (k+2)}}{{2}}}$$ 1 + ... + k + (k + 1) =

      
      Daher ist die Menge $\mathbb {T}$ induktiv und daher ist $\mathbb {T}$ = $\mbox{$\mathbb{N}$}$.
   3. Es ist 1^{1 .} 2^{2 ...} nⁿ$\le$n^{1 .} n^{2 ...} nⁿ = n^{${\frac{{(n+1)\cdot n}}{{2}}}$} nach Teil b der Aufgabe.
2. 1. Es ist f (x) + (x + 1) = ${\frac{{1}}{{2}}}$ ^. x ^. (x + 1) + (x + 1) = (x + 1) ^. (${\frac{{1}}{{2}}}$x + 1) = (x + 1) ^. ${\frac{{x+2}}{{2}}}$ = f (x + 1).
   2. Ich suche nach einer Polynomfunktion höchstens 3ten Grades mit
      
      

      Es ist also f (x) = a₁x + a₂x² + a₃x³. Also ist
      

      f (x + 1) = a₁(x + 1) + a₂(x + 1)² + a₃(x + 1)³

      = (a₁ + a₂ + a₃) + (a₁ +2a₂ +3a₃)x + (a₂ +3a₃)x² + a₃x³

      
      Andererseits ist
      

      f (x + 1) = f (x) + (x + 1)²

      = a₁x + a₂x² + a₃x³ + x² + 2x + 1

      = 1 + (a₁ +2)x + (a₂ +1)x² + a₃x³

      
      Koeffizientenvergleich liefert folgendes Gleichungssystem.

      
      

      a₁ + a₂ + a₃ = 1

      2a₂ +3a₃ = 2

      3a₃ = 1

      
      

      Dies ergibt a₃ = ${\frac{{1}}{{3}}}$, a₂ = ${\frac{{1}}{{2}}}$ und a₁ = ${\frac{{1}}{{6}}}$. Also ist f (x) = ${\frac{{1}}{{3}}}$x³ + ${\frac{{1}}{{2}}}$x² + ${\frac{{1}}{{6}}}$x.

      Wenn es daher ein Polynom mit der gewünschten Eigenschaft gibt, so muss es f sein. Tatsächlich hat f die verlangte Eigenschaft. Denn es ist
      

      $${\frac{{1}}{{3}}} {\frac{{1}}{{2}}} {\frac{{1}}{{6}}}$$ f (x + 1) - f (x) =

      = x² +2x + 1 = (x + 1)²

      
      
   3. Wir verwenden wieder die Methode von Teil b) an. Wir suchen also nach einem Polynom f höchstens 4ten Grades mit f (0) = 0 und f (x + 1) - (x + 1)³ = f (x). Ist f (x) = a₁x + a₂x² + a₃x³ + a₄x⁴, so folgt:
      

      f (x + 1) - f (x) - (x + 1)³ = 0

      
      Rechnet man aus und beachtet, dass beim Nullpolynom alle Koeffizienten 0 sind so ergibt sich folgendes Gleichungssystem.
      

      a₁ + a₂ + a₃ + a₄ = 1

      2a₂ +3a₃ +4a₄ = 3

      3a₃ +6a₄ = 3

      4a₄ = 1

      
      Es folgt f (x) = ${\frac{{1}}{{4}}}$x² + ${\frac{{1}}{{2}}}$x³ + ${\frac{{1}}{{4}}}$x⁴. Zu zeigen bleibt: f (x + 1) - f (x) = (x + 1)³. Dies kann man nachrechnen.
   4. Sei
      
      
      Wir haben :
      

      a₁(x + 1) + a₂(x + 1)² + a₃(x + 1)³ + a₄(x + 1)⁴ + a₅(x + 1)⁵ = a_x + a₂x² + a₃x³ + a₄x⁴ + a₅x⁵ + x⁴ +4x³ +6x² + 4x + 1

      
      Koeffizientenvergleich liefert folgendes Gleichungssystem:
      

      a₁ + a₂ + a₃ + a₄ + a₅ = 1

      2a₂ +3a₃ +4a₄ +5a₅ = 4

      3a₃ +6a₄ +10a₅ = 6

      4a₄ +10a₅ = 4

      5a₅ = 1

      
      Das liefert die Lösung

      $${\frac{{-1}}{{30}}} {\frac{{1}}{{3}}} {\frac{{1}}{{2}}} {\frac{{1}}{{5}}}$$

      
      
      Man rechnet nach, dass dieses Polynom die Bedingungen erfüllt.