Bewijs door Volledige Inductie

Te bewijzen :	t₀=−1 , t₁=1 , t_n= 4.t_n−1− 3.t_n−2 >⇒ t_n = 3ⁿ − 2
Bewijs :
Deel I	Vermits de recursieve formule "twee stappen terug" gaat, moeten we de formule eerst controleren voor twee waarden van n, nl. n = 0 en n = 1 Voor n = 0 levert de formule t_n = 3ⁿ −2 → t₀ = 3⁰ − 2 = − 1 → O.K. Voor n = 1 levert de formule t_n = 3ⁿ −2 → t₁ = 3¹ − 2 = 1 → O.K.

Nu gaan we bewijzen dat S( k ) ⇒ S( k+1)
m.a.w. dat als de stelling geldt voor n = k, ze ook zal gelden voor n = k+1

Deel II	Gegeven :	t_k = 3^k − 2 (k = 1,2,..) ( I.H.)
	Te bewijzen:	t_k+1 = 3^k+1 − 2
	Bewijs :	t_k+1 = 4.t_k − 3.t_k−1
		__ = 4.(3^k − 2) − 3.(3^k−1 − 2)
		__ = 4.3^k − 8 − 3^k + 6
		__ = 3.3^k − 2
		__ = 3^k+1 − 2 Q.E.D.

Door het principe van volledige inductie is de stelling waar voor n = 1 (Deel I),
n = 2 (Deel II), n = 3 (Deel II), n = 4 ... 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