How do I show that the recursive sequence

$$a_n = a_{\lfloor n/2 \rfloor} + a_{\lceil n/2 \rceil} +3n+1, \quad n\geq 2, \phantom{x} a_1 = 3$$

is an increasing sequence?

1. attempt: If I can show that $a_{n+1}-a_n>0$, I would be able to show it is increasing.

\begin{align*} a_{n+1} - a_n & = a_{\left\lfloor \frac{n+1}{2} \right\rfloor} + a_{\left\lceil \frac{n+1}{2} \right\rceil} +3(n+1)+1 - ( a_{\lfloor n/2 \rfloor} + a_{\lceil n/2 \rceil} +3n+1) \\ & = a_{\left\lfloor \frac{n+1}{2} \right\rfloor} + a_{\left\lceil \frac{n+1}{2} \right\rceil}+3 - a_{\lfloor n/2 \rfloor} - a_{\lceil n/2 \rceil} \end{align*}

I can't put $a$ together because the indexes are different (because of the ceils and floors).

2. attempt: Proof by induction

Base case: $n=2$ then $a_2 = a_1 + a_1 + 3\cdot 2 + 1 = 3+3+7=13$ so $a_1<a_2$.

Testing with more gives: $a_1 < a_2 < a_3 =26 < a_4 = 39<... $

Assume $a_n<a_{n+1}$. Now I want to show that $a_{n+1} < a_{n+2}$

$$ a_{n+2} = a_{\lfloor (n+2)/2 \rfloor} + a_{\lceil (n+2)/2 \rceil} +3(n+2)+1$$

Again I get stuck since I don't know how to handle the ceils and floors.


How do I go about showing the sequence is increasing? Maybe I'm making it harder than it actually is - is there by any chance an easier way?

  • $\begingroup$ Have you tried using strong induction? $\endgroup$ – JimmyK4542 Jan 17 '17 at 20:57

For an even index we have $$a_{2n}=2a_n+6n+1$$ and for an odd one, $$a_{2n+1}=a_n+a_{n+1}+6n+4$$ so if we assume (using induction) that $a_{n+1}\ge a_n$ then $$a_{2n+2}=2a_{n+1}+3(2n+2)+1=2a_{n+1}+6n+7>a_n+a_{n+1}+6n+4=a_{2n+1}$$ and $$a_{2n+1}=a_n+a_{n+1}+6n+4>2a_n+6n+1=a_{2n}$$

Remark: Perhaps one of two more base cases are needed.

  • $\begingroup$ Assuming $P(n): a_{n+1} \geq a_n$ then the inductive step would be to show $P(n+1)$ is true, i.e $a_{n+2}\geq a_{n+1}$ - how come you have shown that $a_{2n+2} > a_{2n+1} > a_{2n}$? $\endgroup$ – Stranqer95 Jan 18 '17 at 7:27
  • $\begingroup$ Or does it not make a difference because it's just a factor 2 multiplied? $\endgroup$ – Stranqer95 Jan 18 '17 at 7:34

Suppose for all $m\le n-1$, $a_{m+1}\ge a_m$.

Case 1: $n=2k$. Note that $$ \lfloor \frac{2k+1}2 \rfloor=k,\lceil\frac{2k+1}2 \rceil=k+1. $$ Then \begin{eqnarray} a_{n+1} - a_n & =&a_{2k+1}-a_{2k}\\ &=& a_{\left\lfloor \frac{2k+1}{2} \right\rfloor} + a_{\left\lceil \frac{2k+1}{2} \right\rceil} +3(2k+1)+1 - ( a_{\lfloor 2k/2 \rfloor} + a_{\lceil 2k/2 \rceil} +3\cdot2k+1) \\ & = &a_{k+1} - a_{k}+3\\ &\ge&a_{k+1} - a_{k}\\ &\ge&0 \end{eqnarray} Do the same for $n=2k-1$.


Show $a_{n+1}>a_n$ be induction. Note that $\lceil(n+1)/2\rceil $ is either $\lceil n/2\rceil$ or $\lceil n/2\rceil+1$. Hence by induction hypothesis (which is applicable if $\lceil n/2\rceil<n$, i.e., for $n\ge2$), we may use that $a_{\lceil(n+1)/2\rceil}$ is $>$ or $=$ to $a_{\lceil n/2\rceil}$. The same works for floor. So $$\begin{align}a_{n+1}&=a_{\lfloor (n+1)/2\rfloor}+a_{\lceil (n+1)/2\rceil}+3(n+1)+1\\ &\ge a_{\lfloor n/2\rfloor}+a_{\lceil (n+1)/2\rceil}+3(n+1)+1\\ &\ge a_{\lfloor n/2\rfloor}+a_{\lceil n/2\rceil}+3(n+1)+1\\ &> a_{\lfloor n/2\rfloor}+a_{\lceil n/2\rceil}+3n+1\\ &=a_n. \end{align}$$ But recall that this induction step works only for $n\ge 2$. Hence we need to show manually that $a_3>a_2>a_1$. We compute $a_1=3$, $a_2=10$, $a_3=26$, so all is fine.


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.