# Prove by using Mathematical induction (sum of the first $n$ odd numbers is $n^2$)

$$1+3+...+(2n-1) = n^2 for\quad all\quad n∈N$$

Been watching youtube vidoes but still confused.

Step 1: Show that n=1 is true (Initial value) LHS = 2(1)-(1) = 1, RHS = $1^2$=1 therefore LHS=RHS. N=1 is true.

Step 2: Assume n=k is true 1+3...+(2k-1)=$k^2$

Step 3 is showing and proving but i just got stuck. can someone help me with this please.

Thanks

Let $n=k$ for some arbitrary $k\in \mathbb{N}$. That is $1+3+\cdots +(2k-1)=k^2$. Consider $$(1+3+\cdots +(2k-1))+(2(k+1)-1)=(1+3+\cdots +(2k-1))+(2k+1).$$ Now $$(1+3+\cdots +(2k-1))+(2k+1)=k^2+2k+1=(k+1)^2.$$ Thus by The Principle of Mathematical Induction $1+3+\cdots+(2n-1)=n^2$ for all $n\in \mathbb{N}$.

Well...

We've assumed that for $n=k$, $1+3+...+(2k-1)=k^2$ and so for $n=k+1$, $[1+3+...+(2k-1)]+(2(k+1)-1) = k^2 + (2k+2-1) = k^2 + 2k + 1 = (k+1)^2$. So the statement is true for $n=k+1$ as well.

• Might be a stupid question, but i got stuck on the bit where (2(k+1)-1) how did u get that to (2k-1)? Dec 9, 2013 at 22:22
• If you are adding the first $k$ terms, your $k^{th}$ term will be $2k-1$. So by back substituting, setting $l=k+1$, we get the $l^{th}$ term to be $2l-1 = 2(k+1) - 1 = 2k + 1$. Dec 9, 2013 at 22:24
• ahhh i get it now, cheers mate! Dec 9, 2013 at 22:26

For the final step

$$1 + 3 + ... + (2n - 1 ) + (2(n+1) - 1) =_{by \; ind \; hypothesis} n^2 + 2n +2 - 1= n^2 + 2n + 1 = (n+1)^2$$

A Combinatorial Proof:

Let $S:=\big\{(x,y)\in\mathbb{N}\times\mathbb{N}\,|\,x,y \leq n\big\}=\{1,2,\ldots,n\}\times\{1,2,\ldots,n\}$. For each $k=1,2,\ldots,n$, let $S_k$ be the subset $\big\{(x,y)\in S\,|\,\max\{x,y\}=k\big\}$. Clearly, the $S_k$'s are pairwise disjoint and $S=\bigcup_{k=1}^n\,S_k$. Hence, $n^2=|S|=\sum_{k=1}^n\,\left|S_k\right|$. For each $k=1,2,\ldots,n$, $S_k$ consists of $2k-1$ elements: $(1,k)$, $(2,k)$,$\ldots$, $(k-1,k)$, $(k,k)$, $(k,k-1)$, $\ldots$,$(k,2)$, $(k,1)$. Hence, $n^2=\sum_{k=1}^n\,\left|S_k\right|=\sum_{k=1}^n\,(2k-1)$, as required.