0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ for your base case you nned to show that if n=1 then $n^2 + 3n$ is odd. $\endgroup$ – David Cardozo Oct 28 '14 at 1:35
  • $\begingroup$ 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. $\endgroup$ – Graham Kemp Oct 28 '14 at 2:32
  • $\begingroup$ Since (a) is false, any proof of it must be flawed $\endgroup$ – MJD Oct 28 '14 at 13:39
3
$\begingroup$

(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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.