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?


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

  • $\begingroup$ 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? $\endgroup$
    – Nulle
    Jan 4, 2017 at 16:06
  • $\begingroup$ 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$ $\endgroup$
    – Momo
    Jan 4, 2017 at 16:15
  • $\begingroup$ Typo: $\lfloor n/a\rfloor$ should read $\lfloor n/2\rfloor$ $\endgroup$
    – Momo
    Jan 4, 2017 at 16:22
  • $\begingroup$ 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 $\endgroup$
    – Nulle
    Jan 4, 2017 at 16:32
  • $\begingroup$ Take a look at $P(k)$ in my answer and replace $n$ by $\lceil n/2 \rceil$ $\endgroup$
    – Momo
    Jan 4, 2017 at 16:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .