How can you prove that $1+ 5+ 9 + \cdots +(4n-3) = 2n^{2} - n$ without using induction? Using mathematical induction, I have proved that  
$$1+ 5+ 9 + \cdots +(4n-3) = 2n^{2} - n$$
for every integer $n > 0$. 
I would like to know if there is another way of proving this result without using PMI. Is there any geometric solution to prove this problem? Also, are there examples of problems where only PMI is our only option?
Here is the way I have solved this using PMI. 
Base Case: since $1 = 2 · 1^2 − 1$, the formula holds for $n = 1$.
Assuming that the
formula holds for some integer $k ≥ 1$, that is,
$$1 + 5 + 9 + \dots + (4k − 3) = 2k^2 − k$$
I show that
$$1 + 5 + 9 + \dots + [4(k + 1) − 3] = 2(k + 1)^2 − (k + 1).$$
Now if I use hypothesis I observe.
$$
\begin{align}
1 + 5 + 9 + \dots + [4(k + 1) − 3]
& = [1 + 5 + 9 + \dots + (4k − 3)] + 4(k + 1) −3 \\
& = (2k^2 − k) + (4k + 1) \\
& = 2k^2 + 3k + 1 \\
& = 2(k + 1)^2 − (k + 1)
\end{align}
$$
$\diamond$

Here is a method based upon formal power series. We encode thereby sequences  $\left(a_n\right)_{n\geq 0}$ by formal power series $\sum_{n=0}^\infty a_nx^n$ and show equality of sequences by showing equality of corresponding power series.
Using the summation symbol $\sum$ we claim

The following is valid
  \begin{align*}
\sum_{j=1}^{n}\left(4j-3\right)=2n^2-n\qquad\qquad    n\geq 1
\end{align*}

We encode the sequence
\begin{align*}
\left(\sum_{j=1}^{n}\left(4j-3\right)\right)_{n\geq 1}=\left(1,6,15,\cdots\right)\quad\rightarrow\quad
\sum_{n=1}^\infty\left(\sum_{j=1}^n\left(4j-3\right)\right)x^n=\color{blue}{1}x+\color{blue}{6}x^2+\color{blue}{15}x^3+\cdots
\end{align*}
by the   power series and in the same way we encode 
\begin{align*}
\left(2n^2-n\right)_{n\geq 1}=\left(1,6,15,\cdots\right) \quad\rightarrow\quad\sum_{n=1}^{\infty}\left(2n^2-n\right)x^n=\color{blue}{1}x+\color{blue}{6}x^2+\color{blue}{15}x^3+\cdots
\end{align*}
and show the equality of the corresponding power series.

We obtain
  \begin{align*}
\sum_{n=1}^\infty\left(\sum_{j=1}^n\left(4j-3\right)\right)x^n
&=\sum_{n=1}^\infty\left(\sum_{j=0}^{n-1}\left(4j+1\right)\right)x^n\tag{1} \\
&=\sum_{n=0}^\infty\left(\sum_{j=0}^n\left(4j+1\right)\right)x^{n+1} \tag{2}\\
&=\frac{x}{1-x}\sum_{n=0}^\infty\left(4n+1\right)x^n\tag{3}\\
&=\frac{x}{1-x}\left(4\sum_{n=0}^\infty nx^n+\sum_{n=0}^\infty x^n\right)\tag{4}\\
&=\frac{x}{1-x}\left(4(xD_x)\sum_{n=0}^\infty x^n+\frac{1}{1-x}\right)\tag{5}\\
&=\frac{4x^2}{1-x}D_x\left(\frac{1}{1-x}\right)+\frac{x}{(1-x)^2}\tag{6}\\
&=\frac{x(3x+1)}{(1-x)^3}\tag{7}\\
\end{align*}

Comment:


*

*In (1) we shift the index $j$ by one to start with $j=0$

*In (2) we shift the index $n$ by one to start with $n=0$

*In (3) we use the nice fact that summing up elements is encoded in formal power series by multiplication with $\frac{1}{1-x}$. This is due to the Cauchy product formula.

*In (4) we do some rearrangement to be prepared for further steps

*In (5) we use the formula for the geometric power series and also that differentiating a power series and multiplication with $x$ results in
\begin{align*}
xD_x \sum_{n=0}^\infty a_n x^n = \sum_{n=0}^\infty na_nx^n
\end{align*}
Here we denote with  $D_x:=\frac{d}{dx}$ the differential operator. 

*In (6) we use the formula for the geometric power series again and multiply out

*In (7) we perform the differentiation and simplify the expression

on the other hand we obtain with similar reasoning
  \begin{align*}
\sum_{n=1}^\infty\left(2n^2-n\right)x^n
&=2\sum_{n=1}^\infty n^2x^n-\sum_{n=1}^\infty nx^n\\
&=2(xD_x)^2\sum_{n=1}^\infty x^n-(xD_x)\sum_{n=1}^\infty x^n\\
&=2(xD_x)^2\frac{x}{1-x}-(xD_x)\frac{x}{1-x}\\
&=\frac{2x(1+x)}{(1-x)^3}-\frac{x}{(1-x)^2}\\
&=\frac{x(3x+1)}{(1-x)^3}\\
\end{align*}
  and the claim follows.


Note: Of course applying this method here is to take a sledgehammer to crack a nut. But these techniques are useful also in more difficult context. See e.g. this answer.
