Show the recursive sequence is increasing 
How do I show that the recursive sequence
$$a_n = a_{\lfloor n/2 \rfloor} + a_{\lceil n/2 \rceil} +3n+1, \quad
 n\geq 2, \phantom{x} a_1 = 3$$
is an increasing sequence?

1. attempt:
If I can show that $a_{n+1}-a_n>0$, I would be able to show it is increasing.
\begin{align*}
a_{n+1} - a_n & = a_{\left\lfloor \frac{n+1}{2} \right\rfloor} + a_{\left\lceil \frac{n+1}{2} \right\rceil} +3(n+1)+1 - ( a_{\lfloor n/2 \rfloor} + a_{\lceil n/2 \rceil} +3n+1) \\
& = a_{\left\lfloor \frac{n+1}{2} \right\rfloor} + a_{\left\lceil \frac{n+1}{2} \right\rceil}+3 - a_{\lfloor n/2 \rfloor} - a_{\lceil n/2 \rceil}
\end{align*}
I can't put $a$ together because the indexes are different (because of the ceils and floors).
2. attempt: 
Proof by induction
Base case: $n=2$ then $a_2 = a_1 + a_1 + 3\cdot 2 + 1 = 3+3+7=13$ so $a_1<a_2$. 
Testing with more gives: $a_1 < a_2 < a_3 =26 < a_4 = 39<... $
Assume $a_n<a_{n+1}$.
Now I want to show that $a_{n+1} < a_{n+2}$
$$ a_{n+2} = a_{\lfloor (n+2)/2 \rfloor} + a_{\lceil (n+2)/2 \rceil} +3(n+2)+1$$
Again I get stuck since I don't know how to handle the ceils and floors. 
$\phantom{x}$
How do I go about showing the sequence is increasing? Maybe I'm making it harder than it actually is - is there by any chance an easier way?

Suppose for all $m\le n-1$, $a_{m+1}\ge a_m$. 
Case 1: $n=2k$. Note that
$$ \lfloor \frac{2k+1}2 \rfloor=k,\lceil\frac{2k+1}2 \rceil=k+1. $$ 
Then
\begin{eqnarray}
a_{n+1} - a_n & =&a_{2k+1}-a_{2k}\\
&=& a_{\left\lfloor \frac{2k+1}{2} \right\rfloor} + a_{\left\lceil \frac{2k+1}{2} \right\rceil} +3(2k+1)+1 - ( a_{\lfloor 2k/2 \rfloor} + a_{\lceil 2k/2 \rceil} +3\cdot2k+1) \\
& = &a_{k+1} - a_{k}+3\\
&\ge&a_{k+1} - a_{k}\\
&\ge&0
\end{eqnarray}
Do the same for $n=2k-1$.
