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$

Follow the rainbow!

$$ \Large \color{PaleVioletRed}1 + \color{DarkViolet}5 + \color{DodgerBlue}9 + \dots + \color{LightCoral}{(4n-3)} = n(2n-1) = 2n^2-n$$

$$\sum\limits_{k = 1}^n {\left( {4k - 3} \right)} = 4\sum\limits_{k = 1}^n k - 3 \cdot \sum\limits_{k = 1}^n 1 = 4\frac{{n\left( {n + 1} \right)}}{2} - 3 \cdot n = 2n^2 - n$$

Below we show how to give a rigorous interpretation of some of the other "proof by picture" answers. Namely, we describe how a $2$-dimensional form of telescopy allows us to view a sequence of rectangles as being built-up layer-by-layer from successive differences of prior rectangles - as if built by a $2$-D printer. Further, applying a simple product rule for differences allows us to simplify these differences into a form more amenable to geometric visualization. This yields a simple and purely mechanical way to generate such pictorial proofs. Moreover, it provides a rigorous interpretation of such proofs using standard techniques for telescopic sums. Finally we mention an analogy with calculus: such telescopic summation is a discrete analog of the Fundamental Theorem of Calculus (but you don't need to know any calculus to understand the much simpler discrete analog that we describe below).

Let $\,f_n,\, g_n\,$ be sequences of naturals and $\bar R_n$ a sequence of $f_n\times g_n$ rectangles of area $ R_n = f_n g_n.$ Below we recall the product rule for the difference operator $\,\Delta h_n := h_{n+1} - h_n$ then we apply the rule to the special case $\,f_n = n,\ g_n = 2n\!-\!1\,$ in Lynn's picture below.

$$ \large \color{PaleVioletRed}1 + \color{DarkViolet}5 + \color{DodgerBlue}9 + \dots + \color{LightCoral}{(4n-3)}\, =\, n(2n-1) = 2n^2-n$$

Note: below we give related objects the same color (not related to the coloring above).

$ \begin{eqnarray}{\bf Product\ Rule}\qquad\ \: &&\Delta(f_n g_n ) &=&\ f_{n+1}\ \ \ \Delta g_n &+&\qquad\ \Delta f_n\cdot g_n\\[.3em] {\bf Proof}\quad\ \ \,f_{n+1}\ g_{n+1}\ \ &-&\ \ f_n\ g_n &=&\ f_{n+1}(g_{n+1}\!-g_n) &+&\, (f_{n+1}\!-f_n)\, g_n \\[.5em] {\rm e.g.}\quad\, \smash[b]{\underbrace{(n\!+\!1)(2n\!+\!1)}_{\large R_{\,\Large{n+1}}}}&-&\smash[b]{\underbrace{n(2n\!-\!1)}_{\large R_{\,\Large{n}}}} &=&\ \smash[b]{\underbrace{(\color{#c00}{n\!+\!1})\cdot 2}_{\large \rm arch\ \color{#c00}{sides}}} &+&\quad\ \smash[b]{\underbrace{1\,\cdot\, (\color{#0a0}{2n\!-\!1})}_{\large\rm arch\ \color{#0a0}{top}}}\ \ \ {\rm in\ picture}\\[.2em] \phantom{} \end{eqnarray}$

So to increment an $\,n\!\times\! (2n\!-\!1)$ rectangle $\bar R_n$ to its successor $\bar R_{n+1}$ of size $\,(n\!+\!1)\!\times\!(2n\!+\!1)$ we can add $\,\color{#c00}{n\!+\!1}$ squares on each $\rm\color{#c00}{side}$ of $\bar R_n$ and $\,\color{#0a0}{2n\!-\!1}\,$ on $\rm\color{#0a0}{top}$ of $\bar R_n.\,$ For example, let $\,n=3.\,$ In the picture, to increment the $3\times 5$ blue $\bar R_3$ to the $4\times7$ green $\bar R_4$ rectangle, the rule says we can append $\,\color{#c00}{n\!+\!1} = 4$ green squares to each side of blue $\bar R_3,\,$ plus $\color{#0a0}{2n\!-\!1} = 5$ green squares on top of blue $\bar R_3$ yielding the $\,7\times 4$ green arch - which constitutes the (area) difference between the green $4\times7\ (\bar R_4)$ and blue $3\times 5\ (\bar R_3)$ rectangles. Thus the $\rm\color{#c00}{sides}$ and $\rm\color{#0a0}{top}$ of the arch are precisely the summands in the product rule, so the rule shows how to construct successive differences of $2$-D rectangles $f_n\times g_n$ via differences $\,\Delta f_n,\, \Delta g_n$ of their $1$-D sides.

Thus we can view each rectangle as being built-up layer-by-layer from the differences (= arches) of successive prior rectangles (the separately colorered arches in the picture). Dynamically, we can think of a $2$-D printer building the rectangle arch-layer-by-layer (similar to a $3$-D printer).

The sought equality follows by computing the $n(2n\!-\!1)$ area of rectangle $\bar R_n$ a second way, using said layer-by-layer inductive construction of $\bar R_n.$ By the rule, the difference arches have area $\,R_{k+1}\!-R_k = 2(\color{#c00}{k\!+\!1)} + \color{#0a0}{2k\!-\!1} = 4k\!+\!1.\,$ Adding these to initial area $= 1_{\phantom{\frac{i}i}}\!\!\!$ of $\,1\!\times\! 1$ $\,\bar R_1$

$\qquad\qquad\qquad\begin{eqnarray} {\underbrace{1}_{\color{#c0f}{\large R_{\Large1}}} +\!\!\! \underbrace{5}_{\large{\color{#48f}{R_{\Large 2}}-\color{#c0f}{R_{\Large 1}}}}\!\! +\! \underbrace{9}_{\large{R_{\Large 3}-\color{#48f}{R_{\Large 2}}}}\!\! +\, \cdots + \!\!\underbrace{4n\!-\!3}_{\large{R_{\Large n}-R_{\Large{n-1}}}} \!=\, \smash{\sum_{\large k\,=\,0}^{\large{{n-1}}}\,(4k\!+\!1)}}\\[-.2em] \end{eqnarray}$

is an equal value for the area of $\,n\!\times\!(2n\!-\!1)\,$ rectangle $\,\bar R_n$. This is the sought equality.

The above LHS sums to $ R_n$ since it is a telescoping sum so $\rm\color{#c0f}{successive}\ \color{#48f}{terms}$ cancel out, which becomes clearer if we reorder the sum by rewriting $\,R_{k+1}-R_k\,$ as $\ {-}R_k\! + R_{k+1}$ yielding

$\qquad \begin{eqnarray}{\underbrace{\color{#c0f}{R_1}\! + (\color{#c0f}{-R_1}}_{\large =\ 0}\! + \underbrace{\color{#48f}{R_2}) + (\color{#48f}{-R_2}}_{\large =\ 0}\! +\underbrace{ R_3) + (-R_3}_{\large =\ 0}\! +\cdots +\underbrace{R_{n-1}) +(-R_{n-1}}_{\large =\ 0}\! + R_n)\, =\, R_n}\\[-.1em] \end{eqnarray} $

Here lies the hidden use of induction. Though such telescopic cancellation may seem "obvious", it does require rigorous proof. But the inductive step is easy: adding $\, -R_n\! + R_{n+1}$ to both sides of the above statement $P(n)\,$ yields $P(n\!+\!1)\ $ so $\:P(n)\,\Rightarrow\,P(n\!+\!1)\,$ [to be completely rigorous we should also eliminate the ellipses, replacing them by a more precise summation operator].

Many inductive proofs have a very natural telescopic form, and expressing them in this format often leads to great simplification. You can find many examples of telescopy in my prior answers (both in additive and multiplicative form).

Finally we briefly mention that analogy with calculus. The above remarks on telescopic sums show that $\,f(n)\,$ is the sum of its differences. This is the difference analog of the Fundamental Theorem of Differential Calculus, i.e. we have the analogous theorems

$$\begin{eqnarray} \sum_{k=0}^{n-1}\ \Delta_k f(k)\ \, &=&\ f(n)-f(0)\\[.2em] \int_0^x\! D_t f(t)\, dt &=&\ f(x) - f(0) \end{eqnarray}$$

This is but one small part of the calculus of finite differences, a discrete analog of differential calculus. Many things familiar from calculus have discrete difference analogs, and their proofs are often much simpler (such as the difference product rule above). For example, to verify that $F(n) = \sum_{k=0}^{n-1} f(k)$ it suffices to show that they have the same difference and same initial condition, i.e $\,F(n\!+\!1)-F(n) = f(n)\,$ and $F(0) = 0$. When, as in the OP, both $F$ and $f$ are polynomials this reduces to simply checking the equality of two polynomials, which can be done purely mechanically (so no intuition or visual analogies are needed). E.g. for the OP we have $\,F(n) = n(2n\!-\!1)$ so the proof reduces to verifying $\,F(n\!+\!1)-F(n) = 4n\!+1,\,$ and $\,F(n)= 0,\,$ which is trivial polynomial arithmetic - so trivial we can program calculators to perform all such proofs. In fact there are general summation algorithms due to Karr, Gosper and others that are discrete analogs of the Risch-Bronstein integration algorithms implemented in computer algebra systems such as Macsyma, Maple and Mathematica.

Therefore such difference calculus proofs remain completely mechanical even for higher degree polynomials, but generalizing the geometrical picture-based proofs to higher dimensions will prove much more difficult because we typically lack (real-world) intuition for high dimensional spaces. So difference calculus serves to algebraicize these geometrical proofs in a "calculus" that is so mechanical that it can be performed by a computer - freeing our intuition to work on less trivial matters.