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

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

• Thanks very much for the detailed answer steven! I just have a couple of small questions: At the end of the first line after the bullet point "$k = 2x$", should it not be $8x^2 + 12x + 4$ instead of $8x^2 + 8x + 4$? Also, the same for the case $k = 2x + 1$, I make it $8x^2 + 20x + 8$ instead of $8x^2 + 20x + 12$? As far as I can see these are small points that do not affect the proof, though. – Kotov Mar 3 '14 at 23:50
• Also, after the first bullet point (in the case $n = 2k$), I don't understand how $a_{n+1} = a_n$. Surely $a_{n+1} = a_k + 2a_{k-1} + a_{k+1} + 2$? In which case I suppose a similar argument to the odd case is required - namely splitting the cases $k = 2x$ and $k = 2x + 1$ separately? – Kotov Mar 4 '14 at 11:02
• Sure, I must have been absent-minded while writing the answer...as for the second remark notice that if $n$ is even ( $n = 2k$ ), you have $a_n = 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 = a_{k}+2a_{k-1}+2$ and $a_{n+1} = 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 =a_{k}+2a_{k-1}+2 = a_{n}$ – sirfoga Mar 4 '14 at 13:04
• I wonder where am I going wrong with the following argument, then? $a_{n+1} = a_{\left\lfloor\frac{2k+1}{2}\right\rfloor} + 2a_{\left\lfloor\frac{2k+1}{2}\right\rfloor-1} + a_{2k+1-\left\lfloor\frac{2k+1}{2}\right\rfloor} + 2 = a_k + 2a_{k-1} + a_{k+1} + 2$? – Kotov Mar 4 '14 at 19:10
• $a_{n+1} = a_{\left\lfloor\frac{2k+1}{2}\right\rfloor} + 2a_{\left\lfloor\frac{2k+1}{2}\right\rfloor-1} + a_{2k+1-\left\lfloor\frac{2k+1}{2}\right\rfloor} + 2 = a_{n+1} = a_{\left\lfloor k + \frac{1}{2}\right\rfloor} + 2a_{\left\lfloor k + \frac{1}{2}\right\rfloor-1} + a_{2k+1-\left\lfloor k + \frac{1}{2}\right\rfloor} + 2 = a_k+2a_{k-1}+a_{2k+1-k}+2 =a_k+2a_{k-1}+a_{k+1}+2$ – sirfoga Mar 5 '14 at 9:48