\chapter{Integer sequences} \section{Introduction to numeric sequences} We've studied some general concepts about $\mathbb{Z}$ like primality, divisibility, however perhaps we want to form a set of all integers that satisfy some certain property (for example, the set of all even integers, or the set of all prime numbers). If there is some natural way to order these numbers satisfying our property, one could define an \emph{integer sequence} for them; ordered tuples of integers. This part will consider both integer properties and integer sequences, since the former can often be transformed into the latter. One could argue that number theory is entriely centered on integer sequences (and occasionally rational, real, or complex sets) and their relationships with one another. Just like the natural numbers, integers have a straightforward definition but have extremely deep properties. Sometimes we can identify that a certain group of numbers have some special 'pattern' or 'property', while other numbers don't. A sequence is often used as notation to describe such numbers since integers are countable and well ordered. Let's consider integer properties restricted to $\mathbb{N}$. If $I$ is the set of nonnegative integers with a certain property, the well ordering principle states that we can order them into some integer sequence (not that we can't do this for $\mathbb{Z}$ since WOP doesn't hold). Sometimes Integer sequences such as these have arisen from curiosity about the integers, however many integer sequences have their origins in enumerative combinatorics; a field of math that studies counting problems. Some 'combinatorial' sequences are studied in a number theory setting, and some 'number theory' sequences are borrowed by combinatorics to calculate a quantity; number theory and combinatorics are quite intimately related. Some 'integer sequences' are best interpreted rather as 'arithmetic functions' due to certain behaviours they exhibit when forming arithmetic on them. An entire chapter will be delegated to the study of the integer sequences of number theory (or at least integer sequences that I feel are historically number theoretic) as well as arithmetic functions. Though integer sequences studied in and of themselves find themselves in that chapter, integer sequences will be scattered throughout this book with the concepts they arise from. Above all, there is one integer sequence that has perpetually fascinated and eluded mathematicians for millennia, and they are perhaps the most elegant and enigmatic class of integers in mathematics entirely. They are no other than the \emph{prime numbers}; though we'll have to develop some theory on divisibility before we can discuss them. \section{Parity} An \emph{even number} is a number divisible by 2 \[2n,n\in \mathbb{Z}\] An \emph{odd number} is a number that is not even. \[2n+1,n\in \mathbb{Z}\] \section{Arithmetic progression} -Closed form \section{Geometric progression} -Closed form Therefore this part will also discuss properties of nonnegative integers. \section{$n$-gonal numbers} \begin{definition}[Square number] A \emph{square number} is a number whose square root is an integer. \[ a \text{ is square } \iff \exists n \in \mathbb{N} [a =n^2 ] \] \end{definition} One can prove that a square number $n^2$ is actually the sum of the first $n$ odd numbers. \[n^2 = \sum_{k=1}^{n} (2k-1) \] \[ \forall n \in \mathbb{Z} [ n^2 \equiv 1 \mod 4 ] \] \begin{definition}[Triangular number] A \emph{triangular number} is a number... \[ a \text{ is triangular } \iff \exists n \in \mathbb{N} [a = \sum^{n}_{k=1} k ] \] \end{definition} \[ \sum_{k=1}^{n} k = \frac{n(n+1)}{2}\] 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. \section{Recursive sequences} \subsection{Fibonacci sequence} Fibonacci sequence tends to be highly related to an irrational number called the golden ratio. \begin{definition}[Golden ratio] The \emph{Golden ratio} is the positive real number $\varphi$ that is equal to the ratio of one larger than it to itself. \[\varphi=\frac{\varphi +1}{\varphi}\] Solving the resulting quadratic and taking the positive zero gives the following. \[\varphi=\frac{1+\sqrt{5}}{2}\] \end{definition} This number arises in many biological systems and is used in aesthetics. The Fibonacci recurrence relation is a second orer homogeneous difference equation. This means that it can be solved using methods of functional equations, arriving at Biner's formula. \begin{theorem}[Binet's formula] \[ F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}\] \end{theorem} \begin{theorem} \[ \lim_{n \to \infty} \frac{F_n}{F_{n+1}} = \varphi\] \end{theorem} \subsection{Lucas sequence} \subsection{Pell sequence} \section{$n$-smooth numbers} \chapter{Rational sequences} \section{Bernoulli numbers} \subsection{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}\] \subsection{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. \subsection{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) \] \subsection{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} \begin{definition}[Harmonic number] The \emph{$n$th harmonic number } is defined in the following manner. \[ H_{n} = \sum_{k=1}^{n} \frac{1}{k} \] \end{definition} Generating function \[ \sum^{\infty}_{n=1} H_n z^n = \frac{-\ln (1-z)}{1-z} \] Inductive form \[H_n = H_{n-1} + \frac{1}{n} \] Partial sum of consecutive harmonic numbers \[\sum^{n}_{k=1} H_k = (n+1) H_{n} - n \]