AI Tutor
Every programmer and mathematician knows exponential growth eventually destroys polynomial growth, but checking numbers one by one on a computer will never constitute a proof. How do we establish that 2n>n22^n > n^2 or that 32n−13^{2n} - 1 is always a multiple of 88 for every infinite integer without leaving any gaps?
To prove statements across all positive integers, we use mathematical induction, a two-step proof method where we establish a starting anchor and prove that any true case automatically triggers the next. In 1654, French mathematician Blaise Pascal formalized mathematical induction in his Traité du triangle arithmétique to analyze patterns in combinatorial numbers.
Before applying induction to number theory, we must establish what divisibility means in formal algebra. An integer aa divides an integer bb (written a∣ba \mid b) if and only if there exists an integer mm such that b=a⋅mb = a \cdot m.
How do we algebraically bridge the gap between step kk and step k+1k+1 when exponents are involved?

Divisibility Proofs by Induction

Let us prove that 32n−13^{2n} - 1 is divisible by 88 for all integers n≥1n \ge 1. For the base step, we test n=1n = 1: 32(1)−1=9−1=83^{2(1)} - 1 = 9 - 1 = 8, and 8=8(1)8 = 8(1), which is clearly divisible by 88.
For the inductive hypothesis, we assume the statement holds for an arbitrary integer k≥1k \ge 1, meaning 32k−1=8m3^{2k} - 1 = 8m for some integer mm, or rewritten: 32k=8m+13^{2k} = 8m + 1.
In the inductive step, we analyze the expression at n=k+1n = k + 1 and substitute our hypothesis to isolate a factor of 88.
A common mistake in divisibility induction is writing 32(k+1)−1=8M3^{2(k+1)} - 1 = 8M at the start of your inductive step and manipulating both sides. You cannot assume the (k+1)(k+1) claim is true; you must start strictly with the algebraic expression 32(k+1)−13^{2(k+1)} - 1 and rewrite it until 88 factors out cleanly.
Equalities allow direct algebraic substitutions, but what happens when we must preserve an inequality direction where terms cannot simply be set equal?

Inequality Proofs and Base Shifting