$$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
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.
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}$.
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.
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 $$
