Summation Formula for Polygonal Numbers
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$