I’m working on enhancing my skills, expanding my knowledge and increasing my chances to pass technical interviews. Mathematics plays an important role in problem-solving. Hence, this notes! This blog post is about **Sum Formulas**.

Each sum of the form: $$ \sum_{x=1}^{n} x^{k} = 1^{k} + 2^{k} + 3^{k} + .. + n^{k} $$ where k is a positive integer, has a closed-form formula that is a polynomial of degree (k + 1).

**Triangular number**

**Square pyramidal number**

There is a general formula for such sums, called Faulhaber’s Formula.

In the next lines, I’ll use mathematical induction to proof the Triangular number and the Square pyramidal number formulas.

## Triangular number.

$$ \sum_{x=1}^{n} x = 1 + 2 + 3 + ... + n = \frac{n (n + 1)}{2} $$

**Base step:** Base case, for n = 1

**Inductive hypothesis Step**
The equation is true for an arbitrary integer `k`

**Induction Step**

Based on the **inductive hypothesis**, let’s proof the equation if true for `n = k + 1`

For `n = k + 1`

## Square pyramidal number

$$ \sum_{x=1}^{n} x^{2} = 1^{2} + 2^{2} + 3^{2} + ... + n^{2} = \frac{n (n + 1) (2n + 1)}{6} $$

**Base step:** Base case, for n = 1

**Inductive hypothesis Step**
The equation is true for an arbitrary integer `k`

**Induction Step**

Based on the **inductive hypothesis**, let’s proof the equation if true for `n = k + 1`

Given the R.H.S:

\[R.H.S = \frac{n(n+1)(2n+1)}{6} = \frac{(k+1)(k+2)(2k+3)}{6}\]So, we can ignore the `6`

in the denominator from both sides for now:

\[{R.H.S}\times{6} = (k+1)(k+2)(2k+3)\] \[= (k^2 + 3k + 2)(2k+3)\] \[= 2k^3 + 6k^2 + 3k^2 + 4k + 9k + 6\] \[{R.H.S}\times{6} = 2k^3 + 9k^2 + 13k + 6\]

\[L.H.S = \frac{2k^3 + 9k^2 + 13k + 6}{6}\] \[R.H.S = \frac{2k^3 + 9k^2 + 13k + 6}{6}\] \[R.H.S = L.H.S \#\]

## Number Progressions

A progression, which is also known as a sequence, is nothing but a pattern of numbers. For example, `3, 6, 9, 12`

is a progression because there is a pattern observed where every number here is obtained by adding 3 to its previous number.

There are four types of the most common progressions.

### Arithmetic Progression

Arithmetic Progression (AP) is a sequence of numbers where the difference between any two consecutive numbers is constant.

For Example: `3, 7, 11, 15`

, is an AP where the common difference is `4`

.

For an AP:

`a`

is the first term.`l`

is the last term.`d`

is the common difference.- The
`n`

term could be found as follows: \(a_{n} = a + (n - 1) d\) - We can find the
**sum**as follows: \(S = \frac{n(a + l)}{2}\)

Let’s proof this formula:

The sum of an arithmetic is $$ S = \frac{n(a + l)}{2} $$

Suppose \(a_{1}, a_{2}, a_{3}, ..., a_{n}\) be an arithmetic progression whose first term is `a`

and the common difference is `d`

.

Then:

\[a_{1} = a\] \[a_{2} = a + d\] \[a_{3} = a + 2d\] \[a_{n} = a + (n - 1) d\]\[S_{n} = a + (a + d) + (a + 2d) + ... + \{a + (n - 3)d\} + \{a + (n - 2)d\} + \{a + (n - 1)d\} \;\;\;\;\;\;\;\; (i)\]

And with a simple trick of reversing the order:

\[S_{n} = \{a + (n - 1)d\} + \{a + (n - 2)d\} + \{a + (n - 3)d\} + ... + (a + 2d) + (a + d) + a \;\;\;\;\;\;\;\; (ii)\]by adding \((i)\) and \((ii)\)

Term (i) | Term (ii) | Sum |
---|---|---|

a | \(a + (n - 1)d\) | \(2a + (n-1)d\) |

a + d | \(a + (n - 2)d\) | \(2a + (n-1)d\) |

a + 2d | \(a + (n - 3)d\) | \(2a + (n-1)d\) |

… | … | … |

\(2S_{n} = n\{2a + (n-1)d\}\) |

\[2S_{n} = n\{2a + (n-1)d\}\] \[2S_{n} = n\{a + a + (n-1)d\}\] \[2S_{n} = n(a + l)\] \[S_{n} = \frac{n(a+l)}{2} \#\]

### Geometric Progression

Geometric Progression (GP) is a sequence of numbers where the ratio between any two consecutive numbers is constant.

\[S = \frac{l\times k - a}{k - 1}\]### Harmonic Progression

A series of numbers is said to be in harmonic sequence if the reciprocals (the inverse) of all the elements of the sequence form an arithmetic sequence.

For example: \(\sum_{x=1}^{n}{\frac{1}{x}} = 1 + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{n}\)

### Fibonacci Progression

Fibonacci numbers form an interesting sequence of numbers in which each element is obtained by adding two preceding elements and the sequence starts with `0`

and `1`

.

Sequence is defined as, \(F_{0} = 0\) and \(F_{1} = 1\) and \(F_{n} = F_{n-1} + F_{n-2}\)