Herleitung Potenzmenge.

Question

Aufgabe

Aus einer n-elementigen Menge können (■(n@k)) verschiedene Teilmengen entnommen werden. Erläutern Sie, aufgrund welcher Überlegungen diese Zahl in der Form angegeben werden kann (Herleitung)!

Problem/Ansatz:

Potenzmenge, Induktion??

Comments

$$\sum \limits_{n=0}^{k}\begin{pmatrix} n\\k \end{pmatrix}$$

Answer 1

Dies (■(n@k)) ist nicht lesbar.

Daher beweise ich (durch vollständige Induktion) den Satz:

Aus einer n-elementigen Menge können 2ⁿ verschiedene Teilmengen entnommen werden.

IAnf: Für n=1 gibt es {  } und {a} also 2=2¹ Teilmengen

IBeh: Aus einer n-elementigen Menge können 2ⁿ verschiedene Teilmengen entnommen werden.

IBew: Wenn ein Element hizugenommen wird, bleiben alle schon gefundenen 2ⁿ Teilmegen in der Potenzmenge und außerdem  alle um das neue Element ergänzten. Das sind 2·2ⁿ=2ⁿ⁺¹ Teilmengen.