\part{Integer sequences}


\chapter{Basic sequences}
\section{Arithmetic progression}
-Closed form
\section{Geometric progression}
-Closed form
\section{$n$-gonal numbers}


<h3 class=dred>Square number</h3>
<p>Number with the property that its square root is an integer</p>
<p>\(k^2 = \sum_{n=1}^{k} 2n-1\)</p>


<h4 class=dred>Harmonic number</h4>
<p>\( H_{n} = \sum_{k=1}^{n} \frac{1}{k}\)</p>


<h3 class=dred>Triangle number</h3>
<p>\(T_n = \sum_{k=1}^{n} k = \frac{n(n+1)}{2}\)</p>



I can't go 2 seconds at a university without hearing the legend of Gauss rederiving this formula in his childhood, so I'll save myself the trouble and let your next 99 professors recount the story instead.




\chapter{Bernoulli numbers}
\section{Sums of powers}
-Closed form
\[S_m (n) = \sum^{n}_{k=1} k^m\]

These sums have found use outside the realm of number theory; many engineering and physics problems since antiquity have had crossroads with sums of powers. Notably, these sums occur when calculating the Riemann integral of a polynomial. In this case, an alternative expression that avoids the use of summation would be useful in turning the series into a sequence; which is much easier to analyze for convergence. 
 
Indeed one can show by induction that all sums of powers are representable by polynomials. 

\[S_0 (n) = n \]
\[S_1 (n) = \frac{n(n+1)}{2}\]
\[S_2 (n) = \frac{n(n+1)(2n+1)}{6}\]
\[S_3 (n) = \frac{n^2(n+1)^2}{4}\]



\section{Bernoulli numbers}

Johann Bernoulli and Seki Takakazu were a Swiss and Japanese mathematicians who had both noticed patterns regarding the coefficients of the polynomial representations of the sums of powers. Johann calculated the polynomials for the first 10 sums of powers, and through some algebra heuristically noted the following.
\begin{proposition}[Faulhaber's formula]
	\[ \sum^{n-1}_{k=1} k^m = \frac{1}{m+1} \sum^{m}_{k=0}\binom{m+1}{k} B_k n^{m-k+1}\]
\end{proposition}

$B_n$ was some mystery sequence unknown at the time, however today we have come to call them the \emph{Bernoulli numbers}.
Note that if we take $n=1$ and multiply both sides by $(m+1)$, we have a cleaner way in which we can formally define the Bernoulli numbers.
 \begin{definition}
 The \emph{Bernoulli numbers} are the numbers fored by the sequence $B_n$ such that the following is satisfied.
\[ \sum^{m}_{k=0}\binom{m+1}{k} B_k = 0\] 
 \end{definition}

 I'm not going to lie, this definition isn't very elegant. The fact that we haven't got $B_n$ on its own side of the equation is a little strange; this sequence is rather difficult to work with. We will progressively find nicer ways to define the Bernoulli numbers, the next best definition that we can derive is from the \emph{exponential generation function} of the Bernoulli numbers; this is yet another result from daddy Euler.


For a sequence, its generating function  is the function that sequence generates when they are used as coefficients for terms of a series. Why consider generating functions at all? Many number sequences are difficult to deal with, but if one can find a generating function with a closed form, it provides at least some edge to proving facts about said sequence; in combinatorics this is an extremely common technique. Since Bernoulli numbers are a bit of a tricky beast, a generating function is relatively useful in their study.

\begin{proposition}
\[\sum^{\infty}_{n=1} B_n \frac{z^n}{n!} = \frac{z}{e^z -1} \]
\end{proposition}

Many resources that I have studied use this as their definition of Bernoulli numbers. Although it is definitely better than 'our' definition, I believe it feels a  bit arbitrary present this generating sequence without any elaboration. Euler had to leverage the original definition of Bernoulli numbers to obtain this result; so we too shouldn't put the cart before the horse.

\section{Properties of Bernoulli numbers}


\[ \forall n \in \mathbb{N} ( B_n \in \mathbb{Q}) \]
\[ \forall n \in \mathbb{N}\setminus \{ 0 \} ( B_{2n+1} = 0) \]


\section{Applications of Bernoulli numbers}

As well as their inclusion within the sums of powers formulae, Bernoulli numbers are frequently used in mathematical analysis as coefficients within taylor series

\section{Harmonic numbers}
\[H_n = \sum^{n}_{k=1} \frac{1}{k}\]
\[ \sum^{\infty}_{n=1} H_n z^n = \frac{-\ln (1-z)}{1-z}  \]
\[H_n = H_{n-1} + \frac{1}{n} \]
\[\sum^{n}_{k=1} H_k = (n+1) H_{n} - n \]



\chapter{Recursive sequences}
\section{Fibonacci sequence}
- Golden ratio; number such that it is equal to the ratio of one larger than it to itself.
\[\varphi=\frac{\varphi +1}{\varphi}\]
\[\varphi=\frac{1+\sqrt{5}}{2}\]
- binet's formula
The Fibonacci recurrence relation is a second orer homogeneous difference equation.
\[ F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}} \]
\[\lim_{n \to \infty} \frac{F_n}{F_{n+1}} = \varphi\]
\section{Lucas sequence}
\section{Pell sequence}


