Summation Formula for Polygonal Numbers

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\map P {k, n}$ be the $n$th $k$-gonal number.


Then:

$\ds \map P {k, n} = \sum_{j \mathop = 1}^n \paren {\paren {k - 2} \paren {j - 1} + 1}$


Proof

We have that:

$\map P {k, n} = \begin{cases} 0 & : n = 0 \\ \map P {k, n - 1} + \paren {k - 2} \paren {n - 1} + 1 & : n > 0 \end{cases}$


Proof by induction:

For all $n \in \N_{>0}$, let $\map \Pi n$ be the proposition:

$\ds \map P {k, n} = \sum_{j \mathop = 1}^n \paren {\paren {k - 2} \paren {j - 1} + 1}$


Basis for the Induction

$\map \Pi 1$ is the statement that $\map P {k, 1} = 1$.

This follows directly from:

\(\ds \map P {k, 1}\) \(=\) \(\ds \map P {k, 0} + \paren {k - 2} \paren 0 + 1\)
\(\ds \) \(=\) \(\ds 1\)

This is our basis for the induction.


Induction Hypothesis

Now we need to show that, if $\map \Pi r$ is true, where $r \ge 1$, then it logically follows that $\map \Pi {r + 1}$ is true.


So this is our induction hypothesis:

$\ds \map P {k, r} = \sum_{j \mathop = 1}^r \paren {\paren {k - 2} \paren {j - 1} + 1}$


Then we need to show:

$\ds \map P {k, r + 1} = \sum_{j \mathop = 1}^{r + 1} \paren {\paren {k - 2} \paren {j - 1} + 1}$


Induction Step

This is our induction step:

\(\ds \map P {k, r + 1}\) \(=\) \(\ds \map P {k, r} + \paren {k - 2} r + 1\)
\(\ds \) \(=\) \(\ds \sum_{j \mathop = 1}^r \paren {\paren {k - 2} \paren {j - 1} + 1} + \paren {k - 2} r + 1\) from the induction hypothesis
\(\ds \) \(=\) \(\ds \sum_{j \mathop = 1}^{r + 1} \paren {\paren {k - 2} \paren {j - 1} + 1}\)

So $\map \Pi r \implies \map \Pi {r + 1}$ and the result follows by the Principle of Mathematical Induction.


Therefore:

$\ds \forall n \in \N: \map P {k, n} = \sum_{j \mathop = 1}^n \paren {\paren {k - 2} \paren {j - 1} + 1}$

$\blacksquare$