Proving $a_n=\frac 1 2 \max\{a_{n-k},a_{n-k+1},...,a_{n-1}\}+1$ is monotone and finding its limit 
Let $(a_n)^{\infty}_{n=1}$ defined like so: let $2\le k\in \mathbb N$ and $a_1,a_2...a_k\in \mathbb R$, $a_j\le 2, \ j=1,2,...,k$. 
Let $\forall n\ge k+1 : a_n=\frac 1 2 \max\{a_{n-k},a_{n-k+1},...,a_{n-1}\}+1$
  
  
*
  
*show that $(a_n)^{\infty}_{n=k+1}$ is monotone. 
  
*Prove that the sequence id converging and find it's limit.



*

*Suppose WLOG that $a_{n-1}$ is the maximum, then we'll need to show that: $\frac{a_n}{a_{n-1}}\ge 1$ so take: $\frac{a_{n-1}}{a_{n-2}}=\frac{\frac 1 2 a_{n-1} +1}{\frac 1 2 a_{n-2}+1}=\frac{a_{n-1} +2}{a_{n-2}+2}$ and I know from the supposition that $a_{n-1}\ge a_{n-2}$ so we have: $\frac{a_{n-1} +2}{a_{n-2}+2}\ge1$

*If I try to sketch $a_n$ I see that every element is $\le 2$, so trying to prove this by induction: 
for $n=1$ we have $a_n=\frac 1 2 \max\{a_{n-1}\}+1$ and from the given info we know that: $a_{n-1}=a_k\le 2$ so $a_n\le 2$. 
Suppose the assertion is true for $m$ and prove for $m+1$: 
$a_{m+1}=\frac 1 2 max\{a_{m-k-1},a_{m-k},a_{m-k+1},...,a_{m-1}\}+1$ and from the induction hypothesis: $a_{m-k-1},a_{m-k},a_{m-k+1},...,a_{m-2}\le 2$ so it must be that $a_{m-1}\le 2$. 
Now if every elemt is bounded by $2$ then the sequence is bounded and monotone so it must converge and since it's monotone increasing it must converge to it's supermum which is $2$.
 A: (1) First, we show by induction that
$$\forall\,n\geq 1,\qquad a_{n}\leq 2.\tag{1}$$
Indeed, this is the hypothesis, if $k\leq n$ and for if we have  proved that $a_n\leq 2$ for $n<m$, then
$$a_{m}= \frac{1}{2}\max(a_{m-1},\ldots,a_{m-k})+1\leq 1+1=2.$$
and the $(1)$ follows.
(2) Next, we show by that
$$\forall\,n> k,\qquad a_{n}\leq a_{n+1}.\tag{2}$$
Indeed,
$$a_{n+1}=\frac{1}{2}\max(a_{n},\ldots,a_{n-k+1})+1
\geq \frac{a_n}{2}+1\geq \frac{a_n}{2}+\frac{a_n}{2}=a_n.$$
and the sequence is increasing.
(3) Note that, for $n\geq k$,
$$2-a_{n+1}=\frac{1}{2}\min(2-a_n,2-a_{n-1},\ldots,2-a_{n-k+1})\leq \frac{1}{2}(2-a_n)$$
hence
$$\forall\,n\geq k,\qquad 0\leq 2-a_n\leq \frac{1}{2^{n-k}}(2-a_k).$$
So, $\lim\limits_{n\to\infty}a_n=2$.
A: (1) Monotone
If you want to use induction, for $i > 2k$, you have to prove 2 things with induction:
$$(\forall a \in A)\, 0 < a < 2 \tag{a}$$
$$(\forall i \in \mathbb{N})\, A_i > A_{i-1} \tag{b}$$
Try proving either by itself and you'll see they are codependent (each implies the other), so these have to be proven simultaneously.
$$A_i = {1 \over 2} \max\{\underbrace{A_{i-1}}_x , \underbrace{A_{i-2}, A_{i-3}, \dots }_Y\} + 1$$
Inductive assumption (b) allow you to infer that $(\forall y \in Y)\, x > y$ (by strong inductive assumption) and thus $$\max\{A_{i-1}, A_{i-2}, A_{i-3}, \dots \} = A_{i-1} \tag{c}$$
Inductive assumption (a) is that $0 < A_{i-1} < 2$ and by (c) you get that $0 < A_i < 2$ and $A_{i-1} < A_i$.
If you wish to be pedantic for the $i \le 2k$, I think the easiest way is just to consider a sequence $$B_i = \begin{cases} A_i &\text{ for } i > k \\ \text{sorted}(A_{1 \cdots k})_i &\text{ for } i \le k\end{cases}$$ and the same argument as above holds.
(2) Steady state
(c) allows us to infer that for $i > 2k$, $A_i = {1 \over 2} \max\{A_{i-1}, \dots\} + 1 = {1 \over 2} A_{i - 1} + 1$.  Steady state assumption (because we know it's not periodic) is that $A_{\infty} = A_{\infty - 1}$, so
$$A_{\infty} = {1 \over 2} A_{\infty - 1} + 1$$
$$A_{\infty} = {1 \over 2} A_{\infty} + 1$$
$$A_{\infty} = 2$$
The problem with the approach in the question is that $A_i < L$ and $A$ being monotone isn't enough to assume that $A$ increases to $L$.  You can just as well prove $A_i < \text{anything larger than 2}$.  That is why I recommend steady state, but there may be other valid approaches someone else could suggest.
