Induction with floor, ceiling $n\le2^k\implies a_n\le3\cdot k2^k+4\cdot2^k-1$ for $a_n=a_{\lfloor\frac{n}2\rfloor}+a_{\lceil\frac{n}2\rceil}+3n+1$

Via induction I need to prove an expression is true. the expression is:

$n \leq 2^k \longrightarrow a_n \leq 3 \cdot k2^k + 4 \cdot
2^k-1$

for all $n,k \in \mathbb{Z^+}$

$a_n$ is a recursive function where

$a_1 = 3$

$a_n = a_{\lfloor \frac{n}{2} \rfloor} + a_{\lceil \frac{n}{2} \rceil} + 3n+1$

I am stuck at the point where I need to prove that $P(n+1)$ is true

$a_{\lfloor \frac{n+1}{2} \rfloor} + a_{\lceil \frac{n+1}{2} \rceil} + 3(n+1) + 1 \leq 3 \cdot k 2^k + 4 \cdot 2^k -1 $

It is the fact that I don’t know how to rewrite the floor and ceiling functions to something else.

Can someone give me some ideas how to proceed with this?

Solutions Collecting From Web of "Induction with floor, ceiling $n\le2^k\implies a_n\le3\cdot k2^k+4\cdot2^k-1$ for $a_n=a_{\lfloor\frac{n}2\rfloor}+a_{\lceil\frac{n}2\rceil}+3n+1$"

Hint: Your induction should be for $k$, not for $n$

$P(k): n \leq 2^k \Longrightarrow a_n \leq 3 \cdot k2^k + 4 \cdot
2^k-1$

For $k=1$ it is trivial

Suppose $P(k)$ is true and prove that $P(k+1)$ is true

$P(k+1): n \leq 2^{k+1} \Longrightarrow a_n \leq 3 \cdot (k+1)2^{k+1} + 4 \cdot
2^{k+1}-1$

But if $n\le 2^{k+1}$ then both $\lfloor n/2\rfloor\le 2^k$ and $\lceil n/2\rceil\le 2^k$. Next, write the recurrence and apply the induction hypothesis.

$a_n = a_{\lfloor \frac{n}{2} \rfloor} + a_{\lceil \frac{n}{2} \rceil} + 3n+1 \le 2\cdot(3 \cdot k2^k + 4 \cdot
2^k-1)+3n+1\le 3 \cdot (k+1)2^{k+1} + 4 \cdot
2^{k+1}-1$

After simplifications, the last inequality is equivalent with $n\le 2^{k+1}$, which is true by assumption.