Proving an inequality for a sequence by induction

I'm having some trouble with the following problem:

Let $a_n$ be a sequence defined iteratively for $n \geq 0$ as follows:

$a_n = a_{m+1} + 2a_m + a_{n-m-1} + 2$ where $m$ is defined as $\left\lfloor\frac{n}{2}\right\rfloor -1$, where $\lfloor. \rfloor$ denotes the standard floor function.

The inequality I'm trying to show is:

$a_n \leq \left\lfloor\frac{n^2}{2}\right\rfloor + n$

I've shown the result for the the cases $n = 0, 1$ ($a_0 = 0$ and $a_1 = 1$ by definition, by the way) so I just need to prove the inductive step for $n \geq 2$.

Edit - I should add that all the terms of the sequence are non-negative, so in particular if $k_1 \geq k_2$ then we have $a_{k_1} \geq a_{k_2}$

Here's roughly what I've tried so far:

Unless I've made a mistake, I can assume that $n$ is even (since if n is odd just replace $n$ by $n+1$ which is $\geq n$).

So $\left\lfloor\frac{n}{2}\right\rfloor = \frac{n}{2}$ and hence $a_n = a_{\frac{n}{2}} + 2a_{\frac{n}{2} - 1} + a_{n-\frac{n}{2}} + 2 = 2\left(a_{\frac{n}{2}} + a_{\frac{n}{2} - 1} + 1\right)$

which is $\leq 2\left(\left\lfloor\frac{\left(\frac{n}{2}\right)^2}{2}\right\rfloor+\left\lfloor\frac{\left(\frac{n}{2}-1\right)^2}{2}\right\rfloor + \frac{n}{2} + \frac{n}{2} - 1 + 1\right) = 2\left(\left\lfloor\frac{\left(\frac{n}{2}\right)^2}{2}\right\rfloor+\left\lfloor\frac{\left(\frac{n}{2}-1\right)^2}{2}\right\rfloor + n \right)$ by the inductive hypothesis.

However, nothing I try from this point seems to make much progress.

I'm not exactly sure what the best way to manipulate the two floor functions above is, to get the required result.

Any help or hints would be greatly appreciated.

Thanks in advance.

Answer

$$a_n = a_{m+1} + 2a_m + a_{n-m-1} + 2 = a_{\left\lfloor\frac{n}{2}\right\rfloor -1+1} + 2a_{\left\lfloor\frac{n}{2}\right\rfloor -1} + a_{n-\left\lfloor\frac{n}{2}\right\rfloor +1-1} + 2$$
$$= a_{\left\lfloor\frac{n}{2}\right\rfloor} + 2a_{\left\lfloor\frac{n}{2}\right\rfloor-1} + a_{n-\left\lfloor\frac{n}{2}\right\rfloor} + 2$$ Let's try by $induction$: suppose $a_n \leq \left\lfloor\frac{n^2}{2}\right\rfloor + n$ for all $k \leq n$ ($inductive$ $hypothesis$), let's prove it's valid also for $n+1$.

• If $n$ is even ($n = 2k$):
  $$a_n = a_{2k} = 2(a_{k}+a_{k-1}+1)$$
  
  and
  $$a_{n+1} = a_{2k+1} = 2(a_{k}+a_{k-1}+1) = a_n \leq \left\lfloor\frac{n^2}{2}\right\rfloor + n \leq \left\lfloor\frac{(n+1)^2}{2}\right\rfloor + n+1$$


• If $n$ is odd ($n = 2k+1$):
  $$a_n = a_{2k+1} = 2(a_{k}+a_{k-1}+1) \leq \left\lfloor\frac{(2k+1)^2}{2}\right\rfloor + 2k+1 = \left\lfloor\frac{4k^2+4k+1}{2}\right\rfloor + 2k+1 = 2k^2+2k + 2k+1=2k^2+4k+1$$
  and $$a_{n+1} = a_{2k+2} = a_{2(k+1)} = 2(a_{k+1}+a_{k}+1)$$
  but for the $inductive$ $hypothesis$, $$a_{k+1} \leq \left\lfloor\frac{(k+1)^2}{2}\right\rfloor + k+1$$ and $$a_{k} \leq \left\lfloor\frac{(k)^2}{2}\right\rfloor + k$$ which means that $$a_{n+1} = 2(a_{k+1}+a_{k}+1) \leq 2(\left\lfloor\frac{(k+1)^2}{2}\right\rfloor + k+1 \left\lfloor\frac{(k)^2}{2}\right\rfloor + k+1)$$
  Now,


• if $k = 2x$ $$a_{n+1} = a_{2k+2} = a_{4x+2} \leq 2(\left\lfloor\frac{(k+1)^2}{2}\right\rfloor + k+1 \left\lfloor\frac{(k)^2}{2}\right\rfloor + k+1) = 8x^2+12x +4\leq \left\lfloor\frac{(4x+2)^2}{2}\right\rfloor + 4x+2 = 8x^2+8x+2+4x+2 = 8x^2+12x+4$$


• instead if $k = 2x+1$ $$a_{n+1} = a_{2k+2} = a_{4x+4} \leq 2(\left\lfloor\frac{(2x+2)^2}{2}\right\rfloor + 2x+2+ \left\lfloor\frac{(2x+1)^2}{2}\right\rfloor + 2x+2) = 8x^2+20x+12 \leq \left\lfloor\frac{(4x+4)^2}{2}\right\rfloor + 4x+4$$ so the proof is finally concluded, because it's been proved that if $a_n \leq \left\lfloor\frac{n^2}{2}\right\rfloor + n$, so does $a_{n+1}$, and since $a_0 \leq 0$ it follows that $a_n \leq \left\lfloor\frac{n^2}{2}\right\rfloor + n$ for every $n ∈ \Bbb{N}$

$Q.E.D$