Solve the recurrence

T $($n$)=$ T $($n$/2)+$ T $($n$/4)+$ T $($n$/8)+$ T $($n$/16)++$ T $(2)+$ T $(1)$

T $(1)=1$

You should write the solution, a few sentences explaining how you guessed that solution, and a formal proof that the solution is correct