If you don't have to use induction, an algebraic proof is faster.If is a positive odd integer, show that is divisible by 4
Let for some positive integer .
Therefore: . is divisible by 4.
Use induction to prove: . for all positive integers
. . . yes!
Assume .for some integer
Add to both sides:
Subtract 4 from both sides:
And we have: .
The left side is the left side of
The right side is divisible by 3.
The inductive proof is complete.