# How to solve following recurrence relation

I need to solve the following recurrence relation:

\begin{align*} T(1) &= c_1\\ T(2) &= c_2\\ T(n) &= T(\lfloor\frac{n+2}{2}\rfloor) + c_3, \end{align*}

where $$c_1$$, $$c_2$$ and $$c_3$$ are constants. The thing is, I really don't know how to battle the $$T(\lfloor\frac{n+2}{2}\rfloor)$$ part. I don't need an explicit answer, I just need to know wherever it will be logarithmic (i.e. can be upper bounded by $$\mathcal{O}(\log{}n)$$). I'll be glad for any ideas how to prove/disprove it.

• does this happen to be about Fibonacci numbers and matrix multiplication? – 5201314 Mar 9 at 13:01

For simplicity assume $$n=2^k,k\in \mathbb \{3,4,\cdots \}$$. Then $$\left\lfloor\frac{n+2}{2}\right\rfloor=\left\lfloor\frac{n}{2}+\frac12\right\rfloor=\left\lfloor\frac{2^k}{2}+\frac12\right\rfloor=\left\lfloor2^{k-1}+\frac12\right\rfloor=\lfloor2^{k-1}\rfloor$$ So \begin{align*} T(n)&=T(2^{k-1})+c_3=T(2^{k-2})+2c_3=T(2^{k-3})+3c_3+\cdots =T(2)+kc_3\\ &= c_2+kc_3=c_2+c_3\log n=O(\log n) \end{align*}