Proof with using combination proof (no algerbic methods) that $n^2=\sum_{i=1}^n (2i-1)$

Question

I have the following problem :

Proof using combination : $$n^2=\sum_{i=1}^n (2i-1)$$

I used the following problem :

Problem : Number of vectors of length $2$, with letters $\{1,2,..,n\}$

Left : choose the first letter $n$ possibilities then choose the second letter $n$ possibilities.

Right : I can't figure it out, what $(2i-1)$ has to do?

Any ideas?

Thanks!

Answer 1

$2i-1$ is the number of vectors of length $2$ with letters $1,\cdots ,n$ for which the maximum entry is exactly $i$

Answer 2

You can draw square $n\times n$ and inside this square another squares $(n-1)\times(n-1)$,... with the same vertex and use $n^2-(n-1)^2=2n-1.$