# True or Flawed proof

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?

• for your base case you nned to show that if n=1 then $n^2 + 3n$ is odd. – David Cardozo Oct 28 '14 at 1:35
• For (c) one flaw is in the induction step: it's that $x-1$ and $y-1$ are not always natural numbers. But mostly, witness when $x=n$ that $\max(n, y)=n \implies n\geq y$. So the premise is not always true. – Graham Kemp Oct 28 '14 at 2:32
• Since (a) is false, any proof of it must be flawed – MJD Oct 28 '14 at 13:39

(a) Your base case is wrong: you're supposed to prove that $n^2 + 3n$ is odd for $n=1$, which it clearly isn't. Actually, $n^2 + 3n = n^2 +n + 2n = 2\binom{n+1}{2}+2n$ is always even.