---
title: "Contradiction: 3n+2 odd implies n odd"
subject: "Theory of Computation"
chapter: 1
key: "semester_3/theory_of_computation:proof-contradiction-3n2-odd"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/proof-contradiction-3n2-odd
site: BCT Engineering
---

# Contradiction: 3n+2 odd implies n odd

Theory of Computation · Chapter 1: Introduction

- Asked in: 2070 Chaitra
- Video: [Proof by Contradiction: if 3n+2 is odd then n is odd](https://www.youtube.com/watch?v=cLjUBQuJXyg) — Computer Science Notes
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/proof-contradiction-3n2-odd
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-1

## Question

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

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

## Answer

**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.)

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. To prove by contradiction that 3n + 2 odd implies n odd, what do we assume?
   A. 3n + 2 is odd and n is odd
   B. 3n + 2 is even and n is odd
   C. 3n + 2 is even and n is even
   D. 3n + 2 is odd and n is even
   Answer: D. We assume p true and q false: 3n+2 odd and n not odd (even). (Key point: Assumption)

2. If n = 2k, what is 3n + 2?
   A. 6k + 1, which is odd
   B. 6k + 2 = 2(3k + 1), which is even
   C. 5k + 2, which is even only when k is even
   D. 6k + 2, which is odd
   Answer: B. 6k + 2 = 2(3k+1) is a multiple of 2. (Key point: Algebra)

3. Where does the contradiction arise?
   A. 3n + 2 is not an integer
   B. n is even, contradicting n = 2k
   C. 3n + 2 is even, contradicting the assumption that it is odd
   D. k is not an integer
   Answer: C. We derived 3n + 2 even while assuming it odd, so n must be odd. (Key point: Contradiction)

## Related in Theory of Computation

- [Recursive iff language and complement are RE](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Arecursive-iff-complement-re) — Theory of Computation, chapter 4, asked 2×

## Related in other subjects

- [Proof that √2 is irrational](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Aproof-sqrt2-irrational) — Discrete Structure, chapter 1, asked 3×
- [T/F: stability criterion implies thermal criterion](https://www.bctengineer.com/question.md?key=semester_8%2Ftransmission_and_distribution_system_design%3Atf-stability-implies-thermal) — Transmission and Distribution System Design, chapter 4, asked 2×
- [CCI/ACI, reuse ratio proof and channels per cell](https://www.bctengineer.com/question.md?key=semester_7%2Fwireless_communication%3Acci-aci-reuse-duplex-channels) — Wireless Communication, chapter 2
- [Line coding in PCM and the right technique](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Aline-coding-pcm-solution) — Telecommunications, chapter 3