Let Gn be defined recursively as G₁=0 and G₀=1 and for n>=1, G_n=G_n-1+G_n-2+1

Prove that for all n>=0, G_n>=2^n/2. The proof should have a clearly defined predicate P(n).