Proving a statement through strong induction

Question

Prove that every integer greater than or equal to $5$ can be written as $7x+3y+5z$ where $x,y,z \ge 0$ and $x,y,z \in \mathbb{Z}$.

$P(n): n = 7x+3y+5z$, $\forall n \ge 5$

Base case:

1. $5 = 1 \cdot 5$
2. $6 = 2 \cdot 3$
3. $7 = 7 \cdot 1$

Inductive step:

1. Assume $P(m)$ for $5 \le m \le n$ where $n \ge 7$
2. $P(n - 2)$ must be true because $n-2 \ge 5$
3. $P(n + 1) = 3 + P(n -2)$ because $n + 1 = n + (3 - 2)$, so $n + 1$ can be written as $3$ plus $n - 2$, which is supported by strong induction

Is this proof correct? If not, what can I do to fix it?

Answer 1

Your induction is correct, but you have made some formal errors. For example, $P(n+1)=3+P(n-2)$ doesn't make sense because $P(n-2)$ is not a number. You could write something like

3. $n+1=3+(n-2)$, so by strong induction there exist $x,y,z\in{\mathbb{Z}}$ s.t. $n-2=7x+3y+5z$. Therefore $n+1=7x+3(y+1)+5z$.