I believe I should solve the following by strong induction since it's discrete mathematics, but I don't know how to do it.
Given this sequence:
$a^{}_{1}=2$
$a^{}_{2}=3$
$a^{}_{n}=2a^{}_{n-1}-a{}_{n-2}$ for $n\gt2$
and given that "$a{}_{n}\leq n+2$" for all "$n$"
1) Explain why the following proof is wrong:
$a^{}_{1}=2\lt 1+2$
$a^{}_{2}=3\lt 2+2$
$a^{}_{n}=2a^{}_{n-1}-a^{}_{n-2}\leq 2[(n-1)+2]-[(n-2)+2]\leq 2n+2-n=n+2$
2) Provide the correct proof by finding the explicit formula for $a^{}_{n}$ and prove the formula is correct
Thank you in advance for your help!
The problem occurs when you subtract $a_{n-2}$ and try to use the upper limit from before. This is because you have
$$a_{n-2} \le (n-2) + 2 = n \implies -a_{n-2} \ge -n \tag{1}\label{eq1A}$$
As such, you can't add the negative of the previous upper bound as it's now a lower bound instead. For example, let $a_{n-1} = n + 1 = (n-1) + 2$ and $a_{n-2} = n - 2 \lt (n - 2) + 2$. Then you get
$$\begin{equation}\begin{aligned} a_n & = 2a_{n-1} - a_{n-2} \\ & = 2(n + 1) - (n - 2) \\ & = 2n + 2 - n + 2 \\ & = n + 4 \end{aligned}\end{equation}\tag{2}\label{eq2A}$$
However, $a_n = n + 4 \gt n + 2$! This shows you can't use induction as you did and, actually, I don't see any way offhand to use only strong induction to prove what you're asked.
I'll leave it to you to do part $2$, i.e., find the explicit formula (e.g., by checking a few values to find a pattern & then proving it (e.g., by using strong induction for that as you're dealing with equalities instead of inequalities), or by using a characteristic equation such as described in Wikipedia's linear difference equation article) and then use it to prove the requested inequality is correct.
Update: Using the recursive formula, you have $a_3 = 2a_2 - a_1 = 2(3) - 2 = 4$, $a_4 = 2a_3 - a_2 = 2(4) - 3 = 5$, $a_5 = 2a_4 - a_3 = 2(5) - 4 = 6$, etc. This indicates the explicit formula is
$$a_n = n + 1 \tag{3}\label{eq3A}$$
which you can easily use strong induction to prove, starting with the $2$ base cases of $a_1$ and $a_2$. This equation shows that $a_n \le n + 2$ for all $n$. Alternatively, using the method of characteristics gives
$$\begin{equation}\begin{aligned} \lambda^2 & = 2\lambda - 1 \\ \lambda^2 - 2\lambda + 1 & = 0 \\ (\lambda - 1)^2 & = 0 \end{aligned}\end{equation}\tag{4}\label{eq4A}$$
Since this is a duplicate root, the general solution is
$$a_n = c_1(n)(1)^n + c_2(1)^n \tag{5}\label{eq5A}$$
From the initial conditions, you have
$$a_1 = 2 = c_1 + c_2 \tag{6}\label{eq6A}$$ $$a_2 = 3 = c_1 + 2c_2 \tag{7}\label{eq7A}$$
Next, \eqref{eq7A} minus \eqref{eq6A} gives $c_2 = 1$, which substituting into \eqref{eq6A} gives $c_1 = 1$ also, thus showing \eqref{eq5A} gives the same formula as in \eqref{eq3A}.