I found this odd relationship, $x^2 = \sum_\limits{k = 0}^{x-1} (2k + 1)$. I stumbled across this relationship while I was messing around. What's the proof, and how do I understand it intuitively? It doesn't really make sense to me that the sum of odd numbers up to $2x + 1$ should equal $x^2$.
 A: 
How do I understand it intuitively? It doesn't really make sense to me that the sum of odd numbers up to $2x+1$ should equal $x^2$


Hope this picture will provide you with the visual aid you need. :-)
A: We prove this via induction.
Base case ($x = 1$): $$1^2 = \sum_{k=0}^{1-1} (2k+1) = \sum_{k=0}^0 (2k+1) = 2\cdot 0+1 = 1$$
Inductive step: Suppose it is true for some $x$. Now, we note that $$(x+1)^2 = x^2 + 2x + 1$$
and that
$$\sum_{k=0}^{x+1-1} (2k+1) = \sum_{k=0}^{x-1} (2k+1) + 2x+1$$
A: Notice : $$\begin{align}(x + 1)^2 - x^2 &= x^2 + 2x + 1 - x^2 \\&= 2x + 1\end{align}$$
We take a summation on both sides and see that a lot of cancellation occurs on the LHS: 
$$\sum_{k = 0}^{x-1}\left((x+1)^2 - x^2\right) = \sum_{k = 0}^{x-1}(2x+1)\\
(x -1 + 1)^2 - 0^2 = \sum_{k = 0}^{x-1}(2x+1)\\
x^2 = \sum_{k = 0}^{x-1}(2x+1)$$
A: The standard proof without words is as follows:
1   12    123    1234    ...
    22    223    2234
          333    3334
                 4444

A: $\sum_{k=0}^{x-1}2k=\left(0+\left(x-1\right)\right)+\left(1+\left(x-2\right)\right)+\cdots+\left(\left(x-1\right)+0\right)=x\left(x-1\right)=x^{2}-x$
hence:
$\sum_{k=0}^{x-1}(2k+1)=\sum_{k=0}^{x-1}2k+x=x^2$
A: Yet another picture for illustration:

A: Recall that:
$$\sum_{k=0}^{x}k = \frac{x(x+1)}{2}$$
Then 
$$\sum_{k=0}^x(2k + 1) = 2\sum_{k=0}^x k + \sum_{k=0}^x1 = x(x+1) + (x+1) = x^2 + 2x + 1 \neq x^2$$
Instead, since $x^2 + 2x + 1= (x+1)^2$, then
$$\sum_{k=0}^x(2k + 1) = (x+1)^2$$
Using $x-1$ in place of $x$, then you have:
$$\sum_{k=0}^{x-1}(2k + 1) = x^2$$
A: I noticed this a few days ago and verified the first 1,000,000,000 with a program. If you FOIL it, it makes sense. For example:
(4+1)(4+1) = 4x4 + 4x1 + 4x1 + 1 = 25 

Obviously this is equal to 5x5.  Notice that the last three terms are odd when added because
2x + 1

is consecutive odd numbers, and the first term is the previous square.  If we generalize:
(X+1)(X+1) = X*X + X*1 + X*1 + 1 = X^2 + 2X + 1

Does this help?
