Bewijs door Volledige Inductie

Te bewijzen :	Een verzameling met n elementen bezit 2ⁿ deelverzamelingen
m.a.w.	Als #(V) = n dan is $https://latex.codecogs.com/png.image?\dpi{110}\mathbb{P}\, (V)=2^n$
Bewijs :
Deel I	Voor de kleinste n-waarde, nl. 0 is V = ∅ (de lege verzameling) Die verzameling heeft één deelverzameling, ∅ zelf. Bovendien is 2⁰ ook gelijk aan één → O.K.

Deel II	Gegeven :	$https://latex.codecogs.com/png.image?\dpi{110}\text{Voor een verzameling V met k elementen is }\mathbb{P}\, (V)=2^k$
	Te bewijzen:	$https://latex.codecogs.com/png.image?\dpi{110}\text{Voor een verzameling V met k+1 elementen is }\mathbb{P}\, (V)=2^{k+1}$
	Bewijs :	Weze V ' = V ∪ {m} ( m ∉ V )
		Alle deelverzamelingen van V ' zijn dan de deelverzamelingen van V aangevuld met deelverzamelingen waarin zich m bevindt. Die verkrijg je gewoon door bij alle deelverzamlingen van V het element m bij te voegen. M.a.w. het totaal aantal zal het dubbel zijn van 2ⁿ, dus 2.2ⁿ = 2ⁿ⁺¹ Q.E.D.

Door het principe van volledige inductie is de stelling waar voor n = 0 (Deel I),
n = 1 (Deel II), n = 2 (Deel II), n = 3 ... m.a.w. voor elk natuurlijk getal n

I.H. = Inductiehypothese Q.E.D. = quod erat demonstrandum
Deel I = BASIC STEP
Deel II = INDUCTIVE STEP