Exercise 3: Why the "3^n - 1" Proof Is Invalid, and How to Fix It — Possible Solution
====================================================================

WHAT THE FLAWED "PROOF" ACTUALLY DID
------------------------------
The base case (checking n=1) was legitimate. But the so-called
"inductive step" only checked one specific, concrete transition -
verifying that the claim holds at the specific number n=2 - and then
declared victory. Per this chapter's own warning, "verifying that
P(1) -> P(2) holds, and stopping there, is not a valid inductive step
- it's just one more base case in disguise."

WHY CHECKING n=2 SPECIFICALLY DOESN'T PROVE ANYTHING ABOUT n=3, n=4,
OR BEYOND
------------------------------
A genuine inductive step has to establish the general implication
P(k) -> P(k+1) for an ARBITRARY k - meaning it has to work no matter
which specific integer k turns out to be. Confirming the claim holds
at n=1 and separately at n=2 only tells you two individual facts about
two individual numbers - it says absolutely nothing about whether the
pattern would continue to hold going from n=2 to n=3, or from n=99 to
n=100. Without a general argument, there's no mechanism guaranteeing
the "next domino" keeps falling indefinitely - only that these two
specific dominoes happen to have fallen.

A CORRECTED, GENUINE INDUCTIVE STEP
------------------------------
Inductive hypothesis: assume, for an arbitrary k >= 1, that 3^k - 1 is
divisible by 2 - meaning 3^k can be written as 2m + 1 for some integer
m (i.e., 3^k is odd).

Goal: show 3^(k+1) - 1 is also divisible by 2.

  3^(k+1) = 3 * 3^k
          = 3 * (2m + 1)          [using the inductive hypothesis]
          = 6m + 3
          = 6m + 2 + 1
          = 2(3m + 1) + 1

This shows 3^(k+1) is itself of the form 2 x (some integer) + 1 - in
other words, odd. Therefore 3^(k+1) - 1 = 2(3m + 1), which is
divisible by 2. This argument works for any k whatsoever, since k was
never fixed to a specific number anywhere in the reasoning.

WHY THE ORIGINAL CLAIM HAPPENING TO BE TRUE DOESN'T EXCUSE THE FLAWED
PROOF
------------------------------
3^n - 1 genuinely is divisible by 2 for every n >= 1 - the claim
itself is correct. But per this chapter's own reasoning, a "proof"
that reaches a true conclusion through invalid logical steps is still
not a proof - it's a coincidence that the answer happened to be right,
not a demonstration that it had to be.

WHY THIS WORKS AS AN ANSWER
------------------------------
It identifies precisely what the flawed step did (checking one
specific numeric transition) and explains why that fails to
generalize, then supplies a properly general inductive step - phrased
for an arbitrary k throughout, using algebra rather than a specific
number - that actually proves the claim per this chapter's own
standard.