# Proving a Recursive Sequence by Induction.

I realise there's plenty of similar questions all over the site, but I'm yet to find one with either a fraction, or T(1) being equal to an algebraic constant.

The recurrence in question is: $$T(n) = a, n = 1$$ $$T(n) = c + T (\frac{n}{2}), n > 1$$

I am asked to prove by induction that $T(n) ∈ O(log n)$.

I believe the first step is to try and find an explicit formula involving n for the recurrence, and this formula is then used for the base case. It was suggested to use a ceiling function for $T(\frac{n}{2})$ since non-integers are undefined.

This leads to the first 9 cases being: $$T(1) = a$$ $$T(2) = c+a$$ $$T(3) = 2c+a$$ $$T(4) = 2c+a$$ $$T(5) = 3c+a$$ $$T(6) = 3c+a$$ $$T(7) = 3c+a$$ $$T(8) = 3c+a$$ $$T(9) = 4c+a$$

From here I should be able to find a formula, but it eludes me.

Once the formula is found I should then take the typical induction steps, but obviously I am yet to even get that far.

From

$$T(n)=c+T\left(\frac n2\right),$$ we deduce $$T(n)=2c+T\left(\frac n4\right),$$

$$\cdots$$

$$T(n)=ck+T\left(\frac n{2^k}\right).$$

When $k$ is such that $n/2^k=1$,

$$T(n)=ck+a.$$

Obviously this occurs with

$$k=\lfloor\log_2n\rfloor.$$