Recursion Tree Algorithm Math Quesiton

Question

Hello, I am rusty on my math. Can someone expand step by step whats going on in the induction hypothesis. Where does the 1 go? How is it being added? I just am not seeing the algebra steps that should be obvious to me.

Thanks.

Answer 1

Note that $$T(n)>2^{(n-1)/2}+2^{(n-2)/2}+1>2^{(n-2)/2}+2^{(n-2)/2}$$ because $$1>0, (n-1)/2>(n-2)/2$$ so by transitivity, $$T(n)>2^{(n-2)/2}+2^{(n-2)/2}=2^{n/2}$$