Exercise 3: Proving T(n) = 2n + 5 by Induction — Possible Solution
====================================================================

GIVEN
------------------------------
T(n) = T(n-1) + 2, T(0) = 5
Claim: T(n) = 2n + 5 for all n >= 0

STEP 1: THE BASE CASE
------------------------------
Checking the claim at n=0:

  Claim: T(0) = 2(0) + 5 = 5

This matches the definition's own stated value, T(0) = 5, exactly.
Base case holds.

STEP 2: THE INDUCTIVE HYPOTHESIS
------------------------------
Assume the claim holds for some arbitrary k >= 0:

  T(k) = 2k + 5

STEP 3: THE INDUCTIVE STEP
------------------------------
Using the recurrence's own definition to compute T(k+1):

  T(k+1) = T(k) + 2

Substituting the inductive hypothesis, T(k) = 2k + 5:

  T(k+1) = (2k + 5) + 2 = 2k + 7

Checking this matches the claim's own formula evaluated at n = k+1:

  Claim at n=k+1: 2(k+1) + 5 = 2k + 2 + 5 = 2k + 7

Both expressions equal 2k + 7 - they match exactly.

CONCLUSION
------------------------------
Since the base case holds and the inductive step correctly derives the
claim for k+1 from the assumption that it holds for k, per this
chapter's own induction method, T(n) = 2n + 5 is proven true for all
n >= 0.

WHY THIS WORKS AS AN ANSWER
------------------------------
The proof follows this chapter's own exact three-part induction
structure - base case, inductive hypothesis, inductive step - with
each step's algebra shown explicitly and the final result of the
inductive step compared directly against the claim's own formula
rather than merely asserting they match.