How can you prove that $1+ 5+ 9 + \cdots +(4n-3) = 2n^{2} - n$ without using induction?

Question

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$

Answer 1

Follow the rainbow!

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

Answer 2

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.

Answer 3

$$\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$$

Answer 4

Hint:

Let $$\begin{alignat}{10}S_n&=&1+&&5+&&9+&\cdots+&(4n-3)\\&=&(4n-3)+&&(4n-7)+&&(4n-11)+&\cdots+&1.\end{alignat}$$ Thus $$2S_n=(4n-2)+(4n-2)+(4n-2)+\cdots+(4n-2).$$

---

Additional:

As pointed out in the comments, the proof above relies on mathematical induction. So I want to explain what role induction plays in the proof.

For a given number $n$, say $10000$, the proof is valid, though it involves ellipsis, since one can write down all numbers omitted.
Now we claim that the proposition is true for all natural numbers. This would be difficult to prove without using mathematical induction, although I have no idea whether this is possible. Intuitively, we can see that this proof is valid for all natural numbers, but how do we prove that $$\mathbb{Z}_+=\{n\in\mathbb{N}:S_n=2n^2-n\}?$$

One can start from Peano axioms or axiom of infinity, or other equivalent assumptions, and prove that the set on the right-handed side is $\mathbb{Z}_+$ easily.

I don't think that there exists any proposition we can prove without mathematical induction that it is true for every natural numbers, since when we talk about natural numbers, we are using mathematical induction.

Answer 5

You can use the “trick” attributed to Gauss for finding the sum of the first $n$ integers. Call your sum $S_n$, and consider this.

$$\begin{align} &\quad S_n=+1&+ 5 +& \quad\cdots&+(4n-7)&+(4n-3)\\ +&\quad S_n=+(4n-3)&+(4n-7)+&\quad\cdots&+5&+1 \\ &\hline\\ \quad&2S_n\quad =+\underbrace{(4n-2)}_{1^{st}} &+\underbrace{(4n-2)}_{2^{nd} }+&\quad\underbrace{\cdots}_{3^{rd}\mbox{ to }{(n-2)}^{nd}}&+\underbrace{(4n-2)}_{(n-1)^{st}}&+\underbrace{(4n-2)}_{n^{th}}\\\end{align}$$ Thus $2S_n$ equals $n(4n-2)$, and $S_n=2n^2-n$.

Answer 6

A geometrical proof. A rectangle formed by a sum of gnomons.

Answer 7

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.

Answer 8

My favorite proof makes use of a telescoping sum. Let's recall how that works: given a sequence $a_k$ then: $$ \sum_{k=1}^n (a_{k+1}-a_k)=a_{n+1}-a_1, $$ because intermediate terms cancel out pairwise.

Just take now $a_k=k^2$ and you have: $$ \sum_{k=1}^n [(k+1)^2-k^2]=(n+1)^2-1=n^2+2n. $$ But, on the other hand: $$ \sum_{k=1}^n [(k+1)^2-k^2]=\sum_{k=1}^n (2k+1)= \sum_{k=1}^n 2k+\sum_{k=1}^n 1=\sum_{k=1}^n 2k+n. $$ By equating you get then $$ \sum_{k=1}^n 2k+n=n^2+2n, \quad\hbox{that is}\quad \sum_{k=1}^n 2k=n^2+n \quad\hbox{and}\quad \sum_{k=1}^n 4k=2n^2+2n, $$ so that: $$ \sum_{k=1}^n (4k-3)=2n^2+2n-3n=2n^2-n $$

Answer 9

If you know the expression for the sum of an arithmetic sequence (or can prove it, it's not too hard, see below) then that's another way. For an arithmetic series with first term $a$ and common difference $d$, the sum to $n$ terms, $S_n$ is given by: $$S_n = \frac{n}{2}\left(2a+(n-1)d\right)$$ or alternatively, if the last term is $l$ then $$S_n = \frac{n(a+l)}{2}$$

For your question, we have $a=1$ and $d=4$ so $$S_n = \frac{n}{2}\left(2+4(n-1)\right) = n(2n-1) = 2n^2-n$$

---

To get the first expression for $S_n$, write the sum out twice, in opposite orders, and then take their sum:

$$S_n = a + (a+d) + (a+2d) + ... + [a+(n-2)d] + [a+(n-1)d]$$ $$S_n = [a+(n-1)d] + [a+(n-2)d] + ... + (a+2d) + (a+d) + a$$

$\implies$ $$2S_n = [2a+(n-1)d] + [2a+(n-1)d] + ...+[2a+(n-1)d] + [2a+(n-1)d]$$ where there are $n$ terms, so that

$$2S_n = n [2a+(n-1)d] $$

i.e.

$$S_n = \frac{n}{2}\left(2a+(n-1)d\right)$$

Answer 10

Let

$$a_k := 4 k - 3 \qquad \qquad \qquad b_k := k - 1$$

Using summation by parts,

$$\begin{array}{rl} \displaystyle\sum_{k=1}^n a_k &= \displaystyle\sum_{k=1}^n a_k (b_{k+1} - b_k)\\ &= \left(a_k \, b_k \,\bigg|_1^{n+1}\right) - \displaystyle\sum_{k=1}^n (a_{k+1} - a_k) \, b_{k+1}\\ &= a_{n+1} \, b_{n+1} - a_1 \, b_1 - \displaystyle\sum_{k=1}^n 4 k\\ &= a_{n+1} \, b_{n+1} - \left(\displaystyle\sum_{k=1}^n (4 k - 3)\right) - 3n\\ &= (4 n + 1) n - 3 n - \displaystyle\sum_{k=1}^n a_k\\ &= 4 n^2 - 2n - \displaystyle\sum_{k=1}^n a_k\end{array}$$

Hence,

$$\displaystyle\sum_{k=1}^n a_k = 2 n^2 - n$$

Answer 11

The most straightforward way is of course

$$\frac n2(a+\ell))=\frac n2 \big(1+(4n-3)\big)=\color{red}{2n^2-n}\qquad\blacksquare$$

---

Another method:

The well-known result of the sum of the first $n$ integers: $$1+2+3+4+\cdots+n=\frac{n(n+1)}2$$ Subtract $1$ from each term ($n$ in total): $$0+1+2+3+\cdots+(n-1)=\frac{n(n-1)}2$$ Multiply by $4$: $$0+4+8+12+\cdots+4(n-1)=2n(n-1)$$ Add $1$ to each term ($n$ in total): $$1+5+9+13+\cdots+(4n-3)=\color{red}{2n^2-n}\quad\blacksquare$$

Answer 12

By counting dots (of Hexagonal number) in two ways.

On the left: there are four "outer" sides of each hexagon $j = 2, \dots, n$, where each side has $j$ dots but 3 of them are shared, in addition the trivial hexagon $j=1$ is one dot. Therefore, in total there are $\sum_{j=1}^n4j-3$ dots.

On the right: there are $2n-1$ rows (since a hexagon has both top and bottom sides, except the trivial case), and each row adds $n$ dots. Hence $n(2n-1) = 2n^2-n$ dots.

*Despite being geometric, induction may well be needed to justify the counting arguments, as Bill Dubuque noted.

Answer 13

There are some very clever answers here, but what if you don't spot the clever trick? It would be nice to be able to mechanically grind out the answer, and in order to do that, you can use the discrete calculus.

So here the problem is to evaluate $ \sum_{1\le i\le n}{4i-3} $. First, expand all powers of the summation variable (here, $i$) into sums of falling powers (by inspection in simple cases, or using Stirling cycle numbers). This is trivial here, since $i = i^{\underline 1}$, so $$ \sum_{1\le i\le n}{4i-3} = \sum_{1\le i\le n}{4i^{\underline 1}-3}. $$ Now, summation of falling powers is just like integration of ordinary powers, except for the upper evaluation limit: $$ \sum_{1\le i\le n}{4i^{\underline 1}-3} = \bigg({4\over2}i^{\underline 2}-3i^{\underline 1}\bigg)\bigg\rvert^{n+1}_1. $$ Expand the falling powers and apply the evaluation limits, getting $$ \bigg({4 \over 2}(n+1)(n) - 3(n+1)\bigg) - \bigg({4 \over 2}(1)(0) - 3(1)\bigg) $$ which can be simplified to $ 2n^2 - n $.

No insight required, just turn the handle and compute!

Answer 14

Induction is fundamental to the structure of mathematics. The $``\cdots"$ in the expression $1+ 5+ 9 + \cdots +(4n-3)$ cannot be explained rigorously without using some form of induction. All of the picture proofs here have an implied $``\cdots"$ in them. Similarly, $\text{$\Sigma$-notation}$ and telescoping sums cannot be defined without some form of induction.

Putting that aside, I have always been curious about the process of converting sums to integrals, so I offer the following flawed solution.

Note that $\int_\limits k^{k+1}(4x-5)\,dx = \left. (2x^2-5x) \right|_k^{k+1} = (2k^2+4k+2-5k-5)-(2k^2-5k) = 4k-3$.

So \begin{align} \sum\limits_{k = 1}^n (4k - 3) &= \sum\limits_{k = 1}^n \left( \int_\limits k^{k+1}(4x-5)\,dx \right) \\ &= \int_\limits 1^{n+1}(4x-5)\,dx &\text{(This step requires induction.)} \\ &= \left. (2x^2-5x) \right|_1^{n+1} \\ &= (2n^2 + 4n+2 -5n - 5) - (2 - 5) \\ &= 2n^2-n \end{align}

Addendum

I got the integrand by solving $4k - 3 = \int_\limits k^{k+1}(2ax+b)\,dx = 2ak + (a+b)$

The implication is that

\begin{align} 1 &= u_2 - u_1 \\ 5 &= u_3 - u_2 \\ 9 &= u_4 - u_3 \\ &\vdots \\ 4k-3 &= u_{k+1} - u_k \\ &\vdots \end{align}

where $u_k = 2k^2 - 5k$.

Which converts the sum to the sum of a collapsing series.

This implies Lynn's graphical proof shown below and, though it still requires induction, I thought it shows an interesting way to compute sums.