Skip to main content

Contradiction: 3n+2 odd implies n odd

Short answer

Assume 3n+2 odd but n even. Then n = 2k, so 3n+2 = 6k+2 = 2(3k+1), which is even, contradicting oddness. Hence n must be odd.

Show that if 3n + 2 is odd then n is odd by using the proof by contradiction technique.

Claim. If 3n + 2 is odd, then n is odd (n an integer).

Proof by contradiction. Let p: "3n + 2 is odd" and q: "n is odd". We assume p is true and q is false, and look for a contradiction.

  1. Assume 3n + 2 is odd, and suppose n is not odd, i.e. n is even.
  2. Then n = 2k for some integer k.
  3. So 3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1).
  4. 3k + 1 is an integer, so 3n + 2 is a multiple of 2, i.e. even.
  5. This contradicts the assumption that 3n + 2 is odd.

Hence our supposition (n is even) is false. Therefore n is odd. ∎

(The same argument shows the contrapositive: n even implies 3n + 2 even.)

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 1 questions →