The natural number $m\geq 2$ is given.Sequence of natural numbers $(b_0,b_1,\ldots,b_m)$ is called concave if $b_k+b_{k-2}\le2b_{k-1}$ for all $2\le k\le m.$ Prove that there exist not greater than $2^m$ concave sequences starting with $b_0 =1$ or $b_0 =2$
It follows from the condition that $$ b_m-b_ {m-1} \le b_ {m-1} -b_ {m-2} \le \ldots \le b_1-b_0 = 1. $$Each concave sequence then has the form $$ 1,2, \ldots, n, n, \ldots, n, b_ {n + k}, \ldots, b_m, $$where $ 2 \le n \le m + 1, $ the number $ n $ is written $ ( k + 1) $ times, $ 0 \le k \le m + 1-n $ and $ n> b_ {n + k}> \ldots> b_m. $ The number of sequences $ b_ {n + k}, \ldots, b_m $ not more than $ C_ {n-1} ^ {m + 1-nk} $ (since $ b_ {n + k}, \ldots, b_m $ are distinct positive integers less than $ n $). For $ n = m + 1 $ such sequences are exactly 1. For $ 2 \le n \le m $ such sequences are at most $$ C_ {n-1} ^ {m + 1-n} + C_ {n-1 } {mn} + \ldots + C_ {n-1} ^ {0} \ le C_ {n-1} ^ {0} + C_ {n-1} ^ {1} + \ldots + C_ {n- 1} ^ {n-1} = 2 ^ {n-1} $$(we summed over all $ (k = 0,1, \ldots, m + 1-n).$ Hence the total number of concave sequences is at most $$ 2 ^ 1 + 2 ^ 2 + \ldots + 2 ^ {m-1} + 1 = 2 ^ m-1 <2 ^ m. $$