Exercise 1: Inductive Proof That the Sum of the First n Odd Numbers Is n^2 — Possible Solution
====================================================================

THE CLAIM
------------------------------
1 + 3 + 5 + ... + (2n - 1) = n^2, for all n >= 1.

BASE CASE (n = 1)
------------------------------
The left side has just one term: 2(1) - 1 = 1. The right side is
1^2 = 1. Both sides equal 1. Base case holds.

INDUCTIVE STEP
------------------------------
Inductive hypothesis: assume, for an arbitrary k, that

  1 + 3 + 5 + ... + (2k - 1) = k^2

Goal: show that the formula then also holds for k + 1, i.e., that

  1 + 3 + 5 + ... + (2k - 1) + (2(k+1) - 1) = (k+1)^2

Starting from the left side, and using the inductive hypothesis to
replace the sum of the first k odd numbers with k^2:

  [1 + 3 + ... + (2k - 1)] + (2(k+1) - 1)
  = k^2 + (2k + 2 - 1)
  = k^2 + 2k + 1
  = (k + 1)^2

This matches the right side exactly - the formula with n replaced by
k+1. The inductive step is complete.

CONCLUSION
------------------------------
By the base case and the inductive step together, the formula
1 + 3 + 5 + ... + (2n - 1) = n^2 holds for all n >= 1. QED.

WHY THE INDUCTIVE HYPOTHESIS DOES REAL WORK HERE
------------------------------
The entire point of substituting k^2 in for "1 + 3 + ... + (2k-1)" is
that this substitution is only valid because it was assumed as the
inductive hypothesis - without it, there'd be no way to simplify the
left side algebraically. This is exactly how induction lets a proof
for k+1 "borrow" the already-assumed truth of the statement at k,
rather than proving each case completely from scratch.

WHY THIS WORKS AS AN ANSWER
------------------------------
It states the base case and confirms it numerically, states the
inductive hypothesis explicitly for an arbitrary k (not a specific
number), and performs the algebraic substitution and simplification
needed to reach exactly the k+1 version of the formula.