Is the following proof correct or flawed?
(a) Claim: For every positive integer $n, n^2 + 3n$ is odd.
Proof: The proof will be by induction on $n$.
Base Case: The number $n = 1$ is odd.
Induction Hypothesis: Assume that $k^2 + 3k$ is odd, for some $k ∈ N$.
Induction Step: We want to prove the claim when $n = k + 1$. Thus $$(k + 1)2 + 3(k + 1) = (k^2 + 2k + 1) + (3k + 3) = (k^2 + 3k) + (2k + 4) = (k^2 + 3k) + 2(k + 2)$$ is the sum of an odd and an even integer. Therefore, $(k + 1)^2 + 3(k + 1)$ is odd. Therefore, by the principle of mathematical induction, $n^2 + 3n$ is odd for all natural numbers $n$.
(b) Claim: For every $n ∈ N$, if $n ≥ 4$, then $2^n < n!$.
Proof: The proof will be by induction on $n$.
Base Case: 24 = 16 and 4! = 24. Since 16 < 24, the statement is true for $n = 4$.
Induction Hypothesis: Assume that the claim is true for some natural number $k ≥ 4$.
Induction Step: We want to show that $2^{k+1} < (k + 1)!$. Since $$2^{k+1} = 2 × 2 k < 2 × k! < (k + 1) × k! = (k + 1)!, $$ $2^{k+1} < (k + 1)!$. By the principle of mathematical induciton, the statement is true for all integers $n ≥ 4$.
(c) Claim: For all $x, y, n ∈ N$, if $\max(x, y) = n$, then $x ≤ y$.
Proof: The proof will be by induction on $n$.
Base Case: When $n = 0$, if $\max(x, y) = 0$ and $x, y ∈ N$, then $x = 0$ and $y = 0$, hence $x ≤ y$.
Induction Hypothesis: Assume that, for some $k ∈ N$, if $\max(x, y) = k$, then $x ≤ y$.
Induction Step: We must prove that if $\max(x, y) = k + 1$, then $x ≤ y$. Suppose x, y are such that $\max(x, y) = k + 1$. Then it follows that $\max(x − 1, y − 1) = k$, so by induction hypothesis, $x − 1 ≤ y − 1$. Thus $x ≤ y$, completing the induction step.
I'd say this proof is flawed, since it fails on the first claim, considering if you make $n = 1$, $1^2 + 3^1 = 4\ldots$ Are the rest just as flawed?
