# AlgoDat: Tutorium 0

[TOC]

## Aufgabe 1


Zu zeigen: $\sum_{i=1}^{n} i^2 = \sum_{i=1}^{n+1}(i-1)^2$
Induktionsanfang: n = 0
$\sum_{i=1}^{0} i^2 = \sum_{i=1}^{0+1}(i-1)^2$
$\Leftrightarrow 0^2 = (1-1)^2$
$\Leftrightarrow 0=0$
Induktionsvoraussetzung: Die Aussage gilt für ein beliebiges n.
Induktionsschluss: n $\rightarrow$ n+1:
zz: $\sum_{i=1}^{n+1} i^2=\sum_{i=1}^{n+2}(i-1)^2$

$\sum_{i=1}^{n+1} i^2 =$
$=(n+1)^2 + \sum_{i=1}^{n} i^2=$

>nach Induktionsvoraussetzung

$=(n+1)^2 + \sum_{i=1}^{n+1}(i-1)^2=$
$=\sum_{i=1}^{n+2}(i-1)^2$
$\Box$

## Aufgabe 2

Zu zeigen: $|M| = n \Rightarrow |P(M)| = 2^n$
Induktionsanfang: $n = 0$
$M = \{\}, |M| = 0$
$P(M) = \{\{\}\}, |P(M)| = 1 = 2^0$
Induktionsvoraussetzung: Die Aussage gilt für ein beliebiges n.
Induktionsschluss: n $\rightarrow$ n+1:
zz: $|M| = n+1 \Rightarrow |P(M)| = 2^n+1$
Beispiele:
$P(\{n\})=\{\{\},\{n\}\}$
$P(\{n,n+1\})=\{\{\},\{n\},\{n+1\},\{n,n+1\}\}$

- jedes weitere Element in $M \Rightarrow$ Verdopplung von $|P(M)|$
- Beim Einfügen eines weiteren Elements in $M$:
Verknüpfung mit den vorhandenen Elementen in $P(M)$
$\Rightarrow 2*|P(M)| = 2*2^n = 2^n+1$
$\Box$
- formal: $\{U \cup\{x\}| U \in P(M)\}$

## Aufgabe 3

a)
zu zeigen: $b^{\log_{b}{a}}=a$
Verwende: $b^x=a \Leftrightarrow x=\log_{b}{a}$
$\log_{b}{a} = \log_{b}{a}$
$\Box$

## Aufgabe 4


###### tags: `Algorithmen und Datenstrukturen` `Uni` `Informatik`