I was working on this question for an exercise to improve my skills in induction and recursion. At least I tried the exercise but I got stuck after the base case part. The exercises is to prove that the following claim holds for all integers n ≥ 1: F(n) ≤ n^2
where:
$$F(i) = \left\{ \begin{array}{cc} i & \textrm{if } i \leqslant 2 \\ i + \frac{F(i − 1) + F(i − 2)}{2} & \textrm{ if } i > 2 \end{array} \right.$$
I tried to prove it with induction and base case n = 3, but I have no clue how to prove with the n + 1 case, is there something that I am missing?
As suggested in the comments, all you need to do is to make a stronger inductive hypothesis (in blue below).
The initial conditions $F(1) = 1 \leqslant 1^2$ and $F(2) = 2 \leqslant 2^2$ are clear.
Let $n\geqslant 3$, assume $\color{blue}{\forall 1\leqslant i <n, \, F(i) \leqslant i^2}$.
By induction hypothesis, we get $$ F(n) = n + \frac{F(n-1) + F(n-2)}{2} \leqslant n + \frac{(n-1)^2 + (n-2)^2}{2} $$
Expanding the last expression gives $F(n) \leqslant n^2 - 2n + 5$. But since $n\geqslant 3$, $-2n + 5 < 0$, we get $F(n) \leqslant n^2$, which concludes the proof.