Induction proof for an inequality with a recursive formula $a_n = a_{\lfloor{n/2}\rfloor} + a_{\lceil{n/2}\rceil} + 3n + 1$ We have this recursive formula defined
$a_1=3$ & 
$a_n = a_{\lfloor{n/2}\rfloor} + a_{\lceil{n/2}\rceil} + 3n + 1$ for $n \geq 2$.
And we need to prove $n \leq 2^k \Longrightarrow a_n \leq 3 * 
k2^k+4*2^k-1$ for all $n,k \in \mathbb{Z}^+$.
I think we wanna do the induction over k
For our basic case we choose $n = 2 , k = 1$ 
$a_2 = a_{\lfloor{2/2}\rfloor}+a_{\lceil{2/2}\rceil}+3*2+1 =$ 
$ 3 + 3 + (6+1) = 13$
$2\leq2^1 \Longrightarrow 13 \leq 3*1*2^1+4*2^1-1$
$2\leq2 \Longrightarrow 13 \leq 13$
Our basic case is proven, so we can move on to the induction step
So we will assume that the expression is true for $n \leq 2^k$ and we will now show it is true for $n \leq 2^{k+1}$
This is where I have kinda reached a dead end. My guess is that we want to move from $n \leq 2^k \Longrightarrow a_n \leq 3 * 
k2^k+4*2^k-1$ 
to
$n \leq 2^{k+1} \Longrightarrow a_n \leq 3 * 
(k+1)2^{k+1}+4*2^{k+1}-1$
And we could get closer to the P(k+1) expression by multiplying by 2 on both  sides of P(k) like this: $n*2 \leq 2^k*2 \Longrightarrow a_n*2 \leq (3 * 
k2^k+4*2^k-1)*2$
But I don't know
 A: This is NOT a complete answer! (... is I believe after edits)
I do not understand your recursion on $k$. $3k\cdot2^{k}+4\cdot2^{k}$ is strictly increasing in $k$ hence it suffices to show the inequality for the lowest $k$ such that $n\leq 2^{k}$ (for all $n$).
Let me reformulate your problem.
First, note that $a_{n}$ is strictly increasing. To see this, notice the $a_{n}$ sequence can be rewritten as $a_{1}=3$, $a_{2}=13$ and $a_{n}=a_{n-1}+3+a_{n/2}-a_{n/2-1}$ when $n$ is even and $a_{n}=a_{n-1}+3+a_{(n+1)/2}-a_{(n-1)/2}$ when $n$ is odd.
Second, given this, you need to prove the inequality only for values of $n$ and $k$ such that $n=2^{k}$. For $k\in\{0,1,2,\ldots\}$ this implies $n\in\{1,2,4,8,\ldots\}$.
Third, with $n=2^{k}$ and hence $k=\log{n}/\log{2}$, your inequality becomes $a_{n}\leq n\left(2\frac{\log{n}}{\log{2}}+4\right)-1$ for $n\in\{1,2,4,8,\ldots\}$. Or, alternatively, $a_{2^{k}}\leq2^k(3k+4)-1$ for $k\in\{0,1,2,\ldots\}$. My Mathematica in fact claims that the inequality holds with equality and I think this is the direction in which a complete argument should go.
Fourth, using the expressions for $a_{n}$ above, one can write $a_{2^{k}}$ for $k\in\{0,1,2,\ldots\}$ as a sequence $b_{k}$, with $b_{0}=3$, $b_{1}=13$ and $b_{k}=3b_{k-1}-2b_{k-2}+3\cdot2^{k-1}$. Solution to this recurrence relation, according to my Mathematica (and easily checked), is $b_{k}=3\cdot2^{k}k+2^{k+2}-1$.
