I have to prove that $F(n) \le n^2 $ for n $\ge$ 1
with $i\le 2: F(i)= i$
and for $i>2, F(i) = i + 0.5*F(i-1) +0.5*F(i-2) $
After doing some research, I am pretty confident that I have to use induction, I know how to prove my base cases and what IH to use but I get stuck at the last part of the proof. This is how far I've gotten:
$\text{Base case: }\; F(1) = 1 $ and $1 \le 1^2$
$\text{Base case: }\; F(2) = 2 $ and $2 \le 2^2$
$IH: F(i)\le i^2$ holds and $F(i-1)\le (i-1)^2$ holds for $n\ge1$
To show: $F(i+1)\le(i+1)^2$
$F(i+1) = (i+1) + 0.5*F(i) + 0.5*F(i-1)$
By IH: $0.5*F(i) + 0.5*F(i-1) \le 0.5*(i^2 + (i-1)^2)$
My question now is, what do I do with the i+1 since I have no assumptions about this and I also do not know where to get them. And how do I get to what I have now on the right hand side to $(i+1)^2$
You are almost done.
Inductive step. Suppose the claim holds for $n$ and $n-1$. Let us prove it for $n+1$.
You have
$$F(n+1)=n+1+\frac12(F(n)+F(n-1))\le n+1+\frac12(n^2+(n-1)^2)$$
by inductive hypotesis. A few calculations yield: $$F(n-1)\le n^2+\frac32<n^2+2n+1=(n+1)^2$$