I have to proof the following
$$n\leq 2^k \Rightarrow a_n \leq 3 \cdot k2^k +4\cdot 2^k -1 $$ for all $n,k \in \mathbb{Z}^+$
given the running time for a sorting algorithm that can be described recursively by $a_1 =3$ and $$a_n =a_{\lfloor n/2 \rfloor} + a_{\lceil n/2 \rceil} +3n +1, \quad n\geq 2$$
My answer: It should be possible to show this by strong induction.
$P(n):$ when $n\leq2^k$ the following holds $a_n \leq 3 \cdot k2^k +4\cdot 2^k -1$
Base step
$$P(1): 1 \leq 2^k \Rightarrow a_1 =3 \leq 3 \cdot k2^k +4\cdot 2^k -1 \quad \forall k\in\mathbb{Z}^+$$
Inductive step: Assume $P(1)...P(n)$ is true. We want to show that $P(n+1)$ is also true
$$ P(n+1): n+1 \leq 2^k \Rightarrow a_{n+1} = a_{\left\lfloor \frac{n+1}{2} \right\rfloor} + a_{\left\lceil \frac{n+1}{2} \right\rceil} +3(n+1) + 1 $$
Let $\frac{n+1}{2}=m$
$$ n+1 \leq 2^k \Rightarrow a_{n+1} = a_{\left\lfloor m \right\rfloor} + a_{\left\lceil m \right\rceil} +3n+4 $$
... and this is where I am stuck. How do I use $a_{\left\lfloor m \right\rfloor} + a_{\left\lceil m \right\rceil}$?
It is easy to prove that $a_n$ is an increasing function. Also what you want to prove is only related to $2^k$, so you want to prove the statement for that and an induction on $k$ is enough, and the floor or ceiling function won't bother you at all.