---
# System prepended metadata

title: 'AlgoDat: Tutorium 0'
tags: [Algorithmen und Datenstrukturen, Informatik, Uni]

---

# AlgoDat: Tutorium 0

[TOC]

## Aufgabe 1

![Aufgabenstellung](https://i.imgur.com/OtQ73Wm.png)

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

![Aufgabenstellung](https://i.imgur.com/KOgkfu5.png)
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

![Aufgabenstellung](https://i.imgur.com/Ddt0Xis.png)
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

![Aufgabenstellung](https://i.imgur.com/eqCNOBp.png)

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