The induction hypothesis says: k = bq + r for positive integers, q,b,and r AND 0 <= r < b
Prove: k+1 = bQ + R for integers Q and R, possibly different from q and r, and 0 <= R < b
k = bq + r and 0 <= r < b is GIVEN by induction hypothesis
k+1 = bq + r + 1 <---- adds 1 to both sides; please label this equation ALPHA
Since 0 <= r < b is given, then 0 <=r <= b-1 MUST follow, since they are all integers.
In that case, 0 <= (r+1) < b and the statement still holds for the same choice of q, but
with valid remainder r+1.
Note that If by chance, r = b-1, then r+1 = b and the equation ALPHA becomes:
k+1 = bq + b = b(q+1) + 0
so the statement hold with remainder zero, which is valid.
In this case, k+1 divides EVENLY by b with quotient q+1 and remainder 0.
Ex. 43/5 = 8 r 3
44/5 =8 r 4
45/5 = 9 r 0
If the statement holds for k, then it holds for k+1, and the inductive proof is complete.