TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 22

Aus VoWi
Zur Navigation springen Zur Suche springen

Man zeige für alle n\in \mathbb{N}\setminus\{0\}: \sum_{k=1}^n a_k b_k = a_n \sum_{k=1}^n b_k- \sum_{k=1}^{n-1}(a_{k+1}-a_k)\sum_{j=1}^k b_j

Hilfreiches[Bearbeiten]

Vollständige Induktion
Vollständige Induktion[Bearbeiten, WP]
  1. Induktionsanfang (IA)
  2. Induktionsschritt (IS): Induktionsvoraussetzung (IV) \Rarr Induktionsbehauptung (IB)

Leere Summe (\sum_{k=1}^0 ...) ist immer 0

Lösungsvorschlag von samuelp[Bearbeiten]

Induktionsanfang n=0[Bearbeiten]

Linke Seite: a_1\sum_{k=1}^1 b_k = a_1 b_1

Rechte Seite: a_1 \sum_{k=1}^1 b_k - \sum_{k=1}^{0}(a_{k+1}-a_k)\sum_{j=1}^k b_j= a_1 b_1 - 0

Induktionsschritt n \rightarrow n+1[Bearbeiten]

Induktionshypothese: \sum_{k=1}^n a_k b_k = a_n \sum_{k=1}^n b_k- \sum_{k=1}^{n-1}(a_{k+1}-a_k)\sum_{j=1}^k b_j

Induktionsbehauptung: \sum_{k=1}^{n+1} a_k b_k = a_{n+1} \sum_{k=1}^{n+1} b_k- \sum_{k=1}^{n}(a_{k+1}-a_k)\sum_{j=1}^k b_j

Linke Seite:


\begin{align}
\sum_{k=1}^{n+1} a_k b_k
&=\sum_{k=1}^{n} a_k b_k + a_{n+1}b_{n+1}\\
&\overset{I.H.}{=}a_n \sum_{k=1}^n b_k- \sum_{k=1}^{n-1}(a_{k+1}-a_k)\sum_{j=1}^k b_j + a_{n+1}b_{n+1}\\
&\overset{\pm X}{=}a_n \sum_{k=1}^n b_k- \sum_{k=1}^{n-1}(a_{k+1}-a_k)\sum_{j=1}^k b_j + a_{n+1}b_{n+1}+a_{n+1} \sum_{k=1}^{n} b_k-a_{n+1} \sum_{k=1}^{n} b_k\\
&\overset{1.}{=}a_{n+1}b_{n+1}+a_{n+1} \sum_{k=1}^{n} b_k-\sum_{k=1}^{n-1}(a_{k+1}-a_k)\sum_{j=1}^k b_j + (a_n-a_{n+1}) \sum_{k=1}^{n} b_k\\
&\overset{2.}{=}a_{n+1} \sum_{k=1}^{n+1} b_k-\sum_{k=1}^{n-1}(a_{k+1}-a_k)\sum_{j=1}^k b_j + (a_n-a_{n+1}) \sum_{k=1}^{n} b_k\\
&\overset{3.}{=}a_{n+1} \sum_{k=1}^{n+1} b_k-\sum_{k=1}^{n-1}(a_{k+1}-a_k)\sum_{j=1}^k b_j - (a_{n+1}-a_n) \sum_{k=1}^{n} b_k\\
&\overset{4.}{=}a_{n+1} \sum_{k=1}^{n+1} b_k-\sum_{k=1}^{n}(a_{k+1}-a_k)\sum_{j=1}^k b_j\\
\end{align}

  1. Herausheben von \sum_{k=1}^{n} b_k aus den Termen a_{n+1} \sum_{k=1}^{n} b_k und a_n \sum_{k=1}^{n} b_k (erster und letzer Term)
  2. Zusammenfassen von a_{n+1}b_{n+1}+a_{n+1} \sum_{k=1}^{n}b_k zu a_{n+1} \sum_{k=1}^{n+1}b_k
  3. Umdrehen der Differenz:  + (a_n-a_{n+1}) \rightarrow - (a_{n+1}-a_n)
  4. Zusammenfassen von -\sum_{k=1}^{n-1}(a_{k+1}-a_k)\sum_{j=1}^k b_j - (a_{n+1}-a_n) \sum_{k=1}^{n} b_k zu -\sum_{k=1}^{n}(a_{k+1}-a_k)\sum_{j=1}^k b_j

Die letzte Zeile der Umformungen entspricht der rechten Seite. Dadurch haben wir die Induktionsbehauptung gezeigt.