# Seeking a combinatorial proof of the identity$1+3+\cdots+(2n-1)=n^2$

I would appreciate if somebody could help me with the following problem

Q: Seeking a combinatorial proof

$$1+3+\cdots+(2n-1)=n^2$$

-
What do you consider to be a combinatorial proof? – Gerry Myerson Oct 6 '13 at 2:07
Related - if not dup: math.stackexchange.com/questions/136237/… – leonbloy Oct 6 '13 at 2:13

Consider a bag with balls numbered from $1$ to $n$. Number of ways of choosing $2$ balls with replacement is $n^2$.

We can also count the same in a different way. The pair of balls can be represented as $(i,j)$. Let us now look at the number of ways such that $\max\{i,j\} = k$, where $k \in \{1,2,\ldots,n\}$. If $C_k$ denotes the number of ways such that $\max\{i,j\} = k$, we then have $$C_k = 2k-1$$ This is because if $\max\{i,j\} = k$, then either $j<i=k$ or $i<j=k$ or $i=j=k$.

• Number of ways such that $j<i=k$ is $k-1$.
• Number of ways such that $i<j=k$ is $k-1$.
• Number of ways such that $i=j=k$ is $1$.

Hence, we have $C_k=2k-1$. Hence, the total number of ways of choosing a pair of balls from $n$ balls with replacement is $$\sum_{k=1}^n C_k$$

-
This is what I’d call a combinatorial proof. @Gerry’s familiar proof without words is elegant and non-computational, and I don’t have a really strong objection to calling it combinatorial, but I don’t think of it in those terms. (+1) – Brian M. Scott Oct 6 '13 at 2:28

$$\matrix{a&b&c&d&e&\dots\cr b&b&c&d&e&\dots\cr c&c&c&d&e&\dots\cr d&d&d&d&e&\dots\cr e&e&e&e&e&\dots\cr\vdots&\vdots&\vdots&\vdots&\vdots&\dots\cr}$$

-