Wednesday, 22 October 2014

Prove it - factorial is bigger than 2^n

I've been doing the scala coursera and wanted to write down the proof that

factorial(n) ≥ 2n when n ≥ 4

since it uses induction and I am out of practise.

Base case

For n = 4

factorial(4) = 4*3*2*1 = 24
and 24 = 2*2*2*2 = 16
and 24 ≥ 16

so factorial(n) ≥ 2n when n = 4

Induction step

For n >= 4 assume we have

factorial(n) >= 2n

and consider

factorial(n+1) = factorial(n) × (n+1)
 ≥ 2n × (n+1)
 ≥ 2n × 2 since (n+1) ≥ 2 when n ≥ 4
 = 2n+1

QED
(I also wanted to learn about writing maths in html)