I'm new to induction so please bear with me. How can I prove using induction that, for each positive integer $n$, the sum of the first $n$ odd positive integers is $n^2$?
I think $9$ can be an example since the sum of the first $9$ positive odd numbers is $1,3,5,7,9,11,13,15,17 = 81 = 9^2$, but where do I go from here.
Best Answer
Induction is done by demonstrating that if the condition is true for some $n$ then it must also be true for $n+1$. If you then show that the condition is true for $n=0$ then it must be true for all $n>0$. For this problem:
Step $1$: $n=1$
The sum of the first $1$ odd numbers is $1$. $1^2=1$. Therefore the condition holds for $n=1$.
Step $2$: induction
If the sum of the first $n$ odd numbers is $n^2$ then the sum of the first $n+1$ integers is $n^2 + (2n + 1) = (n+1)(n+1)=(n+1)^2$
So the condition is also true for $n+1$.
Step $3$: conclusion
Since the we have shown that the condition is true for $n=1$ and we have shown that if it is true for $n$ then it is also true for $n+1$ then it follows by induction that it is true for all $n\geq 1$.