Let G_n be defined recursively as G_?1=0 and G₀=1 and for n?1, Gn=G_n?1+G_n?2+1

Prove that for all h?0, G_h?2^h/2.

The proof should have a clearly defined predicate P(n).