Bewijs door Volledige Inductie

Te bewijzen :	$C_{n}^{0}+C_{n}^{1}+C_{n}^{2}+ \cdots C_{n}^{n} = 2^n \quad \forall\: n\in \mathbb{N}$
m.a.w.	$\sum_{i=0}^{n}\: C_{n}^{\: i}=2^n$
Bewijs :
Deel I	Voor de kleinste n-waarde, nl. 0 is LL = C₀⁰ = 1 (de eerste term) RL = 2⁰ = 1

Deel II	Gegeven :	$C_{k}^{0}+C_{k}^{1}+C_{k}^{2}+ \cdots C_{k}^{k} = 2^k$ ^( I.H.)
	Te bewijzen:	$C_{k+1}^{0}+C_{k+1}^{1}+C_{k+1}^{2}+ \cdots C_{k+1}^{k} +C_{k+1}^{k+1}= 2^{k+1}$
	Bewijs :	Vermenigvuldig beide leden van de I.H. met 2, dan verkrijg je $2\: (C_{k}^{0}+C_{k}^{1}+C_{k}^{2}+ \cdots C_{k}^{k}) = 2^{k+1}$
		Net zoals je 2(A+B+C) kan schrijven als A + (A+B) + (B+C) + C schrijven we nu onze gelijkheidals $C_{k}^{0}+(C_{k}^{0}+C_{k}^{1})+(C_{k}^{1}+C_{k}^{2})+ \cdots (C_{k}^{1}+C_{k}^{2})+C_{k}^{k} = 2^{k+1}$
		of zelfs $C_{k+1}^{0}+(C_{k}^{0}+C_{k}^{1})+(C_{k}^{1}+C_{k}^{2})+ \cdots (C_{k}^{1}+C_{k}^{2})+C_{k+1}^{k+1} = 2^{k+1}$
		Voor de som tussen haakjes kunnen we een belangrijke eigenschap van de driehoek van PASCAL toepassen : $C_{n}^{p}+C_{n}^{p+1}=C_{n+1}^{p+1}$ Doe dit bij elk (...) en je verkrijgt precies de termen die je zou willen hebben.

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

Er bestaat een andere, meer bekende en niet-inductieve manier om de formule te bewijzen.
Tel het totaal aantal deelverzamelingen van een verzameling V met n elementen op twee manieren:
1^ste manier :
aantal deelverzamelingen met 0 elementen : C_n⁰ (= 1, de lege verzameling)
aantal deelverzamelingen met 1 elementen : C_n¹ (= n, het aantal singletons)
aantal deelverzamelingen met 2 elementen : C_n² (het aantal paren)
enz...
aantal deelverzamelingen met n elementen : C_nⁿ (=1, de verzameling V zelf, de zgn. onechte deelverzameling)
Tel die aantallen op en je verkrijgt het linkerlid van de gelijkheid.
2^de manier :
Een deelverzameling kiezen is in feite voor elk van de n elementen beslissen : "neem ik het of neem ik het niet".
Je hebt dus voor elk van de elementen twee mogelijkheden.
In totaal dus 2.2.2...2 = 2ⁿ mogelijkheden, het totaal aantal deelverzamelingen, het rechterlid van de gelijkheid