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$

Question

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?

Answer 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.