Sometimes we find a recurrance and/or prove by induction on k rather than n. We can do this because of the relationship that 2^k=n.

Consider:

k values n values

0 1

1 2

2 4

... ...

k-1 n/2

k n

Here I will consider the recurrance relation:

Suppose
T(1) = 1
T(n) = 3T(n/2) + n
then
R(0) = 1 and
R(k) = 3R(k-1) + 2^k