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.$$