Vollständige Induktion - Aus Produkt folgt Summe

Question

Ich muss eine Aufgabe zur vollständigen Induktion lösen. Allerdings weiß ich nach langem Nachdenken immernoch nicht wie ich vorgehen soll.

Für einen Anreiz, wie die Aufgabe zu lösen ist, wäre ich sehr dankbar.

Answer 1

Der Beweis wird indirekt geführt. Wir nehmen an, daß die Folgerung falsch sei und erzeugen einen Widerspruch.

Sei also:

$$\sum \limits_{i=1}^{m}a_{i} \leq n \\\text{Zeige nun mit Vollständiger Induktion die Hilfsaussage:}\\1+a_{i} \leq 2^{a_{i}} \text{ für alle}\, a_{i}\geq 1\\\text{ Der Induktionsanfang für}\, a_{i} = 1\text{ ist offensichtlich erfüllt. }\\\text{ Induktionsschluß: }1 + (a_{i} + 1) \leq 1 + 2^{a_{i}} \leq 2^{a_{i}+1}\\ \text{ Damit folgt:}\\ \prod \limits_{i=1}^{m}(1 + a_{i}) \leq \prod \limits_{i=1}^{m}2^{a_{i}} = 2^{\sum \limits_{i=1}^{m}a_{i}} \leq 2^{n} \text{ nach der Hilfsaussage und unserer Annahme}\\ \text{das steht im Widerspruch zur Voraussetzung, die Annahme also falsch und die Aussage bewiesen.}$$