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.

  • $\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 '17 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 '17 at 16:15
  • $\begingroup$ Typo: $\lfloor n/a\rfloor$ should read $\lfloor n/2\rfloor$ $\endgroup$
    – Momo
    Jan 4 '17 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 '17 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 '17 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.