# 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?

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.

• what exactly do you mean by if $n \leq 2^{k+1}$ then both $\lfloor n/2 \rfloor and... is \leq 2^{k+1}$ how is that usefull? – Nulle Jan 4 '17 at 16:06
• It is $\lfloor n/a\rfloor,\lceil n/2\rceil\le 2^{k}$. It is useful to apply the induction hypothesis $P(k)$ to conclude for example that $a_{\lceil n/2\rceil}\le 3 \cdot k2^k + 4 \cdot 2^k-1$ – Momo Jan 4 '17 at 16:15
• Typo: $\lfloor n/a\rfloor$ should read $\lfloor n/2\rfloor$ – Momo Jan 4 '17 at 16:22
• Okay but how is it usefull to conclude that $a_{\lceil n/2\rceil}\le 3 \cdot k2^k + 4 \cdot 2^k-1$ is true – Nulle Jan 4 '17 at 16:32
• Take a look at $P(k)$ in my answer and replace $n$ by $\lceil n/2 \rceil$ – Momo Jan 4 '17 at 16:41