Prove or disprove: $\frac{n}{2} < f(n) + 1 < n$, for all $n \in A$ with $n \ge 8$ Define the following function and sets:

*

*$\mathbb{P} := \text{set of positive prime numbers in } \mathbb{Z}^+$

*$A := \{n \in \mathbb{Z}^+ \, \mid \, n \ge 4 \, \wedge \, n \equiv 0 \bmod 2\}$

*Function $f:A \to \mathbb{P}$ such that $f(n) = \max \{p \in \mathbb{P} \, \mid \, p \le n-2\}$
If $n \in A$, then $\frac{n}{2} < f(n) + 1 < n$
I tried the following proof (which may be incorrect):
Proof by Induction:
Denote the boolean true and false as $T$ and $F$, respectively. Let $P(n) = $ "Is $f(n)+1$ between $\frac{n}{2} < f(n) + 1 < n \text{?}$".$.
Base Case for $n=4$: Since $f(4) = 2$, then $2 < 2 + 1 = 3 < 4$. Hence, $P(4) = T$.
Assume holds for $n=k$ (Induction Hypothesis): Let $f(k) = p$ and $f(k+2) = q$. Suppose that $P(k) = T:$ $$\frac{k}{2} < p + 1 < k$$
Show $n = k+2$ holds: That is, $$\frac{k+2}{2} < q + 1 < k+2$$
Note: $q \le (k+2) - 2 = k$. So, $q+1 \le k + 1 < k+2$.
Also, $p \le q$.
Case 1: $p = q$
$$\begin{split}
\frac{k}{2} < p &\Longrightarrow \frac{k}{2} + 1 - 1 < p = q\\
&\Longrightarrow \frac{k+2}{2} < q + 1
\end{split}$$
Case 2: $p < q$
Since $\frac{k}{2} < p$, this implies that $\frac{k}{2} + 1 < p + 1 < q + 1$. Hence, $$ \frac{k+2}{2} < q+1 = f(k+2) + 1$$
Putting this all together, we have that $\frac{k+2}{2} < q + 1 < k + 2$. Thus, $P(k+2) = T$.
Q.E.D.
Question: Is this proof correct?
 A: No, this proof doesn't work. You've done most of the setup correctly, but the tricky part will be Case 1 ($p = q$) and you've made a mistake there which made it seem trivial. In particular, you accidentally started from the assumption $\frac k 2 < p$, but the induction hypothesis actually only lets you assume $\frac k 2 < p+1$.
If you didn't see your mistake right away, one other way you could have known there must be a mistake somewhere is - you haven't used the information about prime numbers at all yet!

By the way, it would be good to include in your question more context on where this problem came from / why you care about it. If it's related to a class, then you could say what the course is about and what material has been covered recently that could be relevant. In fact, this seems to be a pretty well-known problem and there's a whole separate Wikipedia page devoted to a pretty long and messy proof, which makes me suspect that something weird is going on if you're in a situation where it seems reasonable to try to prove this result using a "simple" induction method.
