Show the recursive sequence is increasing

Question

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.

$\phantom{x}$

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?

Answer 1

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.

Answer 2

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

Answer 3

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.