Beweis per Vollständige Induktion

Question

Beweisen Sie per vollständiger Induktion, dass man mit n, n ≥ 0, verschiedenen Pizza-Toppings insgesamt 2 ⁿ verschiedene Pizzen machen kann.  (Eine Pizza ohne Belag gilt auch als Pizza). 

Ohne Toppings kann man nur eine Pizza machen: Pizza ohne alles; 

mit den Toppings {Tomatensoße} kann man zwei Pizzen machen: Pizza ohne alles, Pizza mit Tomatensoße; 

mit den Toppings {Tomatensoße, Käse} kann man vier Pizzen machen: Pizza ohne alles, Pizza mit Tomatensoße, Pizza mit Käse, Pizza mit Tomatensoße und Käse; usw.

Answer 1

nehmen wir an es gibt für \(n\) Toppings \(2^n\) mögliche Pizzen. Wenn man jetzt \(n+1\) Toppings hat so betrachtet man folgendes:

1) Mit den ersten \(1\) bis \(n\) Toppings lassen sich nach Voraussetzung \(2^n\) mögliche Pizzen machen.

2) Für jede dieser Pizzen gibt es eine neue Pizza, die dadurch entsteht, dass wir das \(n+1\).te Topping dazu nehmen.

Damit hätten wir aber auch schon alle möglichen Pizzen durch, es gibt also \(2^n+2^n= 2^{n+1} \) mögliche Pizzen.

Gruß