equence and Series]

Note 1
[A] Sequence and Series

Sequence and series are one of the common topics in algebraic combinatory and even just algebra problems. In this note, we review some of the foundational topics and intuition on sequence and series, then we discuss more advanced topics from recursion and different type of sums.

1.1 Prerequisites

Problems involving sequence and series appeared a lot in competition style problems. Let’s review some of the topics and gain some intuition on olympiad style sequence and series with Abel transformation.

1.1.1 Telescoping

Telescoping is an essential skill that we learn when we first get started with competition math. Because this content itself is not too difficult, let’s finish our review with an example problem.

Exercise 1.1.1: USAMTS Year 11 Round 4 Problem 3 (\( \bullet \circ \circ \))

Find \(S\) defined as the following. \[ S = \sqrt { 1 + \frac {1}{1^2} + \frac {1}{2^2} } + \sqrt { 1 + \frac {1}{2^2} + \frac {1}{3^2} } + \cdots + \sqrt { 1 + \frac {1}{1999^2} + \frac {1}{2000^2} } \]

Solution.

First, let’s rewrite the sum \(S\) using the sum notation. \[ S = \sum _{i=1}^{1999} \sqrt { 1 + \frac {1}{i^2} + \frac {1}{(i + 1)^2} } \] Now we see the terms \(1 + \frac {1}{i^2} + \frac {1}{(i + 1)^2}\) inside a square root. To get rid of the annoying square root, we can try writing the terms in a perfect square. Consider the following equation. \begin{align*} &\quad \ \left ( 1 + \frac {1}{n} + \frac {1}{n + 1} \right )^2 \\ &= 1 + \frac {1}{n^2} + \frac {1}{(n + 1)^2} + 2 \left ( \frac {1}{n} + \frac {1}{n + 1} + \frac {1}{n(n + 1)} \right ) \end{align*}

Notice that because \(\frac {1}{n} - \frac {1}{n+1} = \frac {1}{n(n+1)}\), it would be much preferable to have \(\frac {1}{n} - \frac {1}{n} - \frac {1}{n(n+1)}\) instead of \(\frac {1}{n} + \frac {1}{n + 1} + \frac {1}{n(n + 1)}\). Therefore, the following equations are obtained. \begin{align*} &\quad \ \left ( 1 + \frac {1}{n} - \frac {1}{n + 1} \right )^2 \\ &= 1 + \frac {1}{n^2} + \frac {1}{(n + 1)^2} + 2 \left ( \frac {1}{n} - \frac {1}{n + 1} - \frac {1}{n(n + 1)} \right ) \\ &= 1 + \frac {1}{n^2} + \frac {1}{(n + 1)^2} \end{align*}

Substituting the equation to the series, we obtain the following equations. \begin{align*} S &= \sum _{i=1}^{1999} \sqrt {1 + \frac {1}{i^2} + \frac {1}{(i + 1)^2}} = \sum _{i=1}^{1999} \sqrt {\left ( \frac {1}{i} - \frac {1}{i + 1} + 1 \right )^2} \\ &= \sum _{i=1}^{1999} \left ( \frac {1}{i} - \frac {1}{i + 1} + 1 \right ) = 1999 + \frac {1}{1} - \frac {1}{2000} \\ &= \frac {2000^2 - 1}{2000} = \frac {3999999}{2000} \end{align*}

Thus, \(S = \frac {3999999}{2000}\).

I think telescoping when paired with inequalities like Cauchy and products becomes much powerful! Continuing, let’s discuss Abel’s transformation.

1.1.2 Abel Transformation

There are many different names of this, and when you search “Abel Transformation” you would probably get different summation concerning integration by parts. But let’s stick with this term because I think it is quite popular.

Definition 1.1.2: Abel Transformation

Given reals \(a_i\) and \(b_i\), the following equation holds where \(a_{n+1} = 0\). \[ \sum _{i=1}^n a_i b_i = \sum _{i=1}^n (a_i - a_{i+1}) \left ( \sum _{k=1}^i b_k \right ) \]

This transformation is quite unique. To derive this, simply expand the right-hand side. Then magically, every residual terms telescope. To see how this can be applied in real life, here is an example problem.

Exercise 1.1.3: Classic Problem

If \((a_1, \ldots , a_n) \succ (b_1, \ldots , b_n)\) with \(a_i \geq a_j \geq 0\) and \(b_i \geq b_j \geq 0\) for \(i > j\), show that \(\sum _{i=1}^n a_i^k \geq \sum _{i=1}^n b_i^k\) for all positive integer \(k\).

Solution.

We could use Karamata to prove this, but that would ruin all the fun! For this problem, notice that we need to show that \(\sum _{i=1}^n (a_i^k - b_i^k) \geq 0\). Because the following equation \[ a_i^k - b_i^k = (a_i - b_i) \left ( a_i^{k-1} + a_i^{k-2} b_i + \cdots + b_i^{k-1} \right ) \] holds, let \(x_i = a_i^{k-1} + a_i^{k-2} b_i + \cdots + b_i^{k-1}\) and \(y_i = a_i - b_i\). Rewriting \(\sum _{i=1}^n (a_i^k - b_i^k)\), it suffices to show that \(\sum _{i=1}^n x_i y_i \geq 0\). By Abel transform, we obtain following the equation. \[ \sum _{i=1}^n x_i y_i = \sum _{i=1}^n (x_i - x_{i+1}) (y_1 + \cdots + y_i) \] Notice that \(x_i - x_{i+1} \geq 0\) since \(a_i \geq a_j \geq 0\) and \(b_i \geq b_j \geq 0\) for \(i > j\). Moreover, because \((a_1, \ldots , a_n) \succ (b_1, \ldots , b_n)\), \(y_1 + \cdots + y_i > 0\). Therefore, the inequality holds.

This is it for this section! In the next section, we will discuss recurrence relation in depth.