Proving a Stronger Claim

$\newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\Q}{\mathbb Q} \newcommand{\R}{\mathbb R} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \definecolor{fillinmathshade}{gray}{0.9} \newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}} $

Subsection 8.11.1 Proving a Stronger Claim

Sometimes the easiest way to prove a claim is to prove a stronger one.

Consider the claim: for n  0, (Prime(3n + 1)). If we examine its truth for several values of n, we observe that, for all n, (3n + 1) is more than just not prime. It is always divisible by 2 (i.e., it is even). It’s quite easy to prove this more general claim. So let’s do it. Notice, as we do so, that in our proof of the stronger claim we get to exploit a stronger induction hypothesis. Prove: for n  0, (3n + 1 is even). The proof is by induction on n. Base case: n = 0: 30 + 1 = 2. Induction step: The induction hypothesis is that 3n + 1 is even and thus is equal to 2k for some integer k. 3n+1 + 1 = 3(3n) + 1 = 3(3n + 1) – 2 = 3(2k) – 2 For some integer k. Induction hypothesis = 2(3k – 1) So 3n+1 + 1 is divisible by 2 (so it’s even).