Neighboring non coprime

Let $n > 1$. A sequence $A_n$ of integers greater than 1 having length $n$ is called nice if any two elements are not coprime. That is, $$\gcd(A_i, A_{i+1}) > 1 \forall i, 1 \leq i \leq n-1$$

Find the smallest real number $t$ such that, given any sequence of integers $A_n$ of integers greater than 1 having length $n$, there exists a sequence of positive integers $B_n$ of length $n$ such that:

1. $\max{B_i} \leq n \max {A_i}$

2. $B_n$ differs from $A_n$ in at most $\lceil tn \rceil$ elements.

Solution

Note that for $t=1$ we can just change every single element to a small number like 2. We can try to do better. Satisfying condition 2 is easy, because for $t = 1/2$ we can just change every other element to the the LCM of it's neighboring elements, but this would make it failr condition 1. For example, suppose the sequence consists of very large primes, then this strategy would cause every other element to be the product of the two large primes, failing condition 1.

We propose that $t = 2/3$ satisfies the condition. That is, if $$A_n = a_1, a_2, a_3,a_4,a_5,a_6,\dots,a_n$$ $$B_n = 2a_2, a_2, 2a_2, 2a_5, a_5, 2a_5, \dots$$

We can see that every two neighboring elements are not coprime, and that the maximum of $B_i$ is at most twice that of $A_i$. We show that there is no smaller $t$ that can satisfy, using a series of counter examples.

For $n=3$, consider the sequence $p_1,p_2,p_3$ of very large primes. There is no way to only change one element to be nice, while keeping the maximum element manageable. The only way to change one element to be nice is to change $p_2 \to p_1p_3$, which then would fail condition 1. So we must change at least 2 elements, which means $\lceil 3t \rceil \geq 2$, so $t > \frac{1}{3}$

For $n=5$ consider the sequence $p_1,p_2,p_3,p_4,p_5$. If we were to change only 2 elements, either we change $p_2,p_4$, or we leave two neighboring primes intact. But if we change $p_2,p_4$, this could mean we have to change $p_2$ to LCM of $p_1,p_3$ and so on, violating condition 1. So we must change at least 3 elements, which means $\lceil 5t \rceil \geq 3$ so $t \frac{2}{5}$

ODE discrete version

If $f$ is a function that is defined over natural numbers ($f:N \to R$), let $f^*$ denote the function $f^*(n) = f(n) - f(n-1)$. Find all functions such that $$n(f^*)^*(n) + (n-1)f^*(n) = f(n)$$ for all $n > 2$

Solution We can check that $f(n) = A(n-1) + B/2^n$ for any constant $A,B$ satisfies the given equation. Now we show that there's nothing else.

Define $g = f^*+f$. The equation is identical to: $$n(f^*+f)^*(n) =(f^*+f)(n)$$ $$ n(g(n) - g(n-1)) = ng^*(n) = g(n)$$ $$\frac{g(n)}{n} = \frac{g(n-1)}{n-1}$$ for all $n>2$, therefore $g(n)/n$ must be a constant. Remember that $g(1)$ is not defined because $f$ is only defined for $n \geq 1$ thus $g$ is only defined for $n \geq 2$. Furthermore, the value $g(2)$ depends on $f(1)$ and $f(2)$.

Case 1: $g(2) = 0$ In this case then $g(n) = 0 \forall n$. $$(f^*+f)(n) = 0$$ $$f(n) = f(n-1)/2$$ so we easily get $f(n) = k/2^n$ for some constant $k$.

Case 1: $g(2) \neq 0$ Note that if $f$ is a solution to the problem then $kf$ is also a solution to the problem, for all $k$ real numbers. If we replace $f$ by $kf$, then $g$ is also replaced by $kg$. So WLOG, we may assume that $g(2) = 2$

Because $g(n) / n$ is a constant then $$g(n) / n = g(2) / 2 = 1$$ so $g(n) = n \forall n >2$ $$f(n) = \frac{f(n-1) + n}{2}$$ for all $n > 2$.

Because $g(2) = 2 = 2f(2) - f(1)$ then $f(2) = 1+ f(1)/2$ Now notice this pattern: $$f(3) = \frac{f(2) + 3}{2} = 2 + f(1)/4$$ $$f(4) = \frac{f(3) + 4}{2} = 3 + f(1)/8$$ Easy to prove by induction that $f(n) = n-1 + f(1)2^{1-n}$.

From the two cases above, it's clear that any solution of the equation must be in the form of $f(n) = A(n-1) + B/2^n$ for any constant $A,B$

Call applicants to front

Let $n$ be a natural number, and we are given a sequence $a_1, a_2, \dots, a_{2n}$ whose elements are integers from 1 to $n$ inclusive, such that each element in $(1, \dots, n)$ appears at least once.

Now, suppose there are $n$ job applicants $J_1, \dots, J_n$ waiting on a line, in any order. We call them in for interviews using $a_i$ as our "call list." More formally, for $i = 1, \dots, 2n$, we call $J_{a_i}$ one by one.

If a particular job applicant $J_x$ is called for an interview, he has to pay a fee of $y-1$ where $y$ is his position in the line. For example, if he was the second person when called, he pays a fee of 1. If he was the front person, he doesn't pay. After the interview, he returns to the front of the line, and the interviewer proceeds with the next one on the call list.

For a given call list and initial ordering of applicants, we define income as the total fees paid by the applicants. For a given call list, its potential income is the sum of all income over all possible initial ordering of applicants. Now, to make things more interesting, before the interview day, the call list itself was shuffled, such that any $(2n)!$ permutation is equally likely to appear.

If you are tasked with putting together a call list, knowing that it will eventually be shuffled, how should you structure it so that the expected potential income is maximized?

Random walk sequences

Let $n$ be a natural number. Suppose $a_1, a_2, \dots$ are sequences of +1s and -1s. Also define $s_k = a_1 + a_2 + \dots + a_k$, and define $s_0 = 0$. Such sequence is called "complete" if for each $i \in {0, \dots, n-1}$ there exists $k$ such that $s_k \equiv i \mod n$.
What is the largest number $S$ such that the following statement is true: For every complete sequence, there exists $j,k \geq 0$ such that $|s_j - s_k| = S$.

Answer:

$n-1$

We can construct $a_i$ as follows: $n-1$ +1s, followed by $n-1$ -1s, and followed by $n-1$ +1s again, alternatingly. It's easy to see that this sequence is complete. Moreover, the sum of any contiguous block ranges from $-(n-1)$ to $(n-1)$. So clearly for this particular sequence, $S \leq n-1$ fulfills the statement, and $S > n-1$ is not satisfied by this sequence.

Now we have to prove that for $S=n-1$ and any given complete sequence, the problem statement is fulfilled.

First Solution

The sequence is infinite, but suppose we can truncate it to the smallest sequence so that it's still complete. In other words, suppose the sequence $a_1, \dots, a_N$ is complete but $a_1, \dots, a_{N-1}$ is not. Let $s_N = x$. Because $N$ is the smallest index such that it's still complete, that means $s_i \equiv x \mod n$ does not happen before $N$. Consider $a_N$. It can be either +1 or -1. Suppose it's +1 (the case of -1 is similar). So that means $s_{N-1} = x-1$.

Let $p$ be the an index such that $s_p \equiv x+1 \mod n$. We know $p$ exists because the sequence is still complete. Also that $p < N-1$. That means $s_{N-1} - s_p \equiv (x-1) - (x+1) \equiv -2 \mod n$. But from $i = p$ to $i = N-1$ we can't have $s_i = x$, so that means $s_{N-1} - s_p = tn - 2$ for some $ t > 0$. This means that $s_N - s_p = tn-1$.

But if $t > 1$, then we must have some $r$ such that $p < r < N$ and $s_N - s_r = n, s_r - s_p = (t-1)n-1$. But this yields a contradiction, because then $s_r \equiv s_N \equiv x \mod n$ and thus $a_1, \dot, a_r$ is complete, violating our condition that $N$ is the smallest complete sequence. Thus we must have that $t=1$ and consequently $s_N - s_p = n-1$

Second Solution

Suppose that there is no contiguous block whose sum is $\pm(n-1)$. Each contiguous block must have sum of at most $(n-2)$ and at least $-(n-2)$. Now, if there is $k$ such that $s_k = n-1$ then we are done, because it would imply a contiguous block from $0$ to $k$ with sum $n-1$. So let $x$ be the maximum value of $s_i$, where $x \leq n-2$. Likewise, let $y$ be the minimum value of $s_i$ where $y \geq -(n-2)$.

Because the sequence is complete, then we must have that $x-y \geq n-1$, otherwise some values won't be "reached" by $s_i$ at all. But this means that there is a contiguous block from the maximum to the minimum or vice versa, and their sum is $\pm(n-1)$

Flea on a regular polygon

We are given a regular $N$-gon. A flea originally sits on one vertex. At each turn, the flea decides to either jump to the left or to the right to the next (closest) vertex. The flea continues this movement until it has visited all vertices. Let $a_i$ be a sequence that records the flea's movement. If at $i$-th turn $(i \geq 1)$ the flea moves to the left then $a_i = -1$, and if it moves to the right then $a_i = 1$. We are told that this sequence is finite (i.e. the flea does visit all vertices and therefore stops). Show that there exists $j,k$ such that: $$| \sum_{i=j}^k a_i | = N-1$$

Monotonically increasing sequences with sums

Let $a_1, \dots, a_{1007}$ and $b_1, \dots, b_{1007}$ be monotonically increasing sequences such that:

For all $i$, $0 \leq a_i \leq 2013$ and $0 \leq b_i \leq 2013$.

For $i \neq j$, $a_i + a_j \neq 2013$ and $b_i + b_j \neq 2013$

$a_0 = b_0$

There exists a real number S such that for all $i$, $a_i + b_{1008-i} = S$.

What are the possible values of $S$?

Solution

Note that for $a_i$ and $b_i$, we need to choose 1007 numbers from 2014 numbers (0,1,...,2013) and no two of those chosen ones may add up to 2013. Thus, from each of the following pairs of numbers $(0,2013), (1,2012), \dots, (1006,1007)$ we must choose exactly one number. Thus, at most one of 0 or 2013 may be chosen. For now, let's assume that $a_1 = b_1 = 0$, which means 2013 is not chosen in both $a_i$ and $b_i$. We'll deal with the other cases later.

Let $k$ be the first number that is not chosen in $a_i$. That means $0, \dots, k-1$ are all chosen, so we have $a_1 = 0, a_2 = 1, \dots, a_k = k-1$.

This also means that $2013, \dots, 2013-(k-1)$ are not chosen but $2013-k$ is chosen. In other words, $2013-k$ is the largest chosen number in $a_i$, so $a_{1007} = 2013-k$. Because $b_1 = 0$ then $S = 2013-k$. That means $b_{1007}=2013-k - a_0 = 2013-k$

Because $2013-k$ is the largest chosen number in $b_i$, then $2013-k+1,\dots,2013$ are not chosen in $b_i$, therefore $0,\dots,k-1$ are chosen in $b_i$ and $k$ is not chosen in $b_i$.

Because $0,\dots,k-1$ are chosen in $b_i$, and $S = 2013-k$, that means $2013-k, 2013-k-1, \dots, 2013-(2k-1)$ are chosen in $a_i$, which means $k,k+1,\dots,2k-1$ are not chosen in $a_i$. Likewise, because $0,\dots,k-1$ are chosen in $a_i$, and $S = 2013-k$, that means $2013-k, 2013-k-1, \dots, 2013-(2k-1)$ are chosen in $b_i$, which means $k,k+1,\dots,2k-1$ are not chosen in $b_i$.

At this point, we have established the following fact:

• The first $k$ numbers in $a_i$ and $b_i$ are chosen, and the next $k$ numbers are not chosen.
• The last $k$ numbers in $a_i$ and $b_i$ are not chosen, and the previous $k$ numbers are chosen.

We would like then to claim that this pattern would have to continue itself all the way to the "middle" of the sequences, which finally means that $2k$ divides 2014. Formally, we claim that for each $m \geq 0$, we have the following:

• $2km, \dots, (2m+1)k-1$ are chosen in $a_i$ and $b_i$.
• $(2m+1)k, \dots, (2m+2)k-1$ are not chosen in $a_i$ and $b_i$.
• $2013-((2m+1)k-1), \dots, 2013-2km$ are not chosen in $a_i$ and $b_i$.
• $2013-((2m+2)k-1), \dots, 2013-(2m+1)k$ are chosen in $a_i$ and $b_i$.

The case of $m=0$ has been proven above. Now suppose it holds for $m$.

Because $(2m+1)k, \dots, (2m+2)k-1$ are not chosen in $a_i$ and $S = 2013-k$ then $2013-k-((2m+2)k-1), \dots, 2013-k-(2m+1)k$ are not chosen in $b_i$. In other words, $2013-((2m+3)k-1), \dots, 2013-(2m+2)k$ are not chosen in $b_i$. Similarly, they're not chosen in $a_i$ as well.

Now because those are not chosen in $b_i$, then $(2m+2)k,\dots,(2m+3k)-1$ are chosen in $b_i$. Similarly, chosen in $a_i$ as well.

Because $S=2013-k$ and $(2m+2)k,\dots,(2m+3k)-1$ are chosen in $b_i$ then $2013-((2m+4)k-1), \dots, 2013-(2m+3)k$ are chosen in $a_i$, and similarly, chosen in $b_i$ as well.

Because the above are chosen, then $(2m+3)k, \dots, (2m+4)k-1$ are not chosen in $a_i, b_i$, and this completes the induction step.

So now that our claim is proven, we note that this pattern must continue for all values of $m$ as long as no index becomes negative. There is no restriction of the value of $m$ in our proof of the claim. That means that towards the end of the sequence, our pattern must "line up" with what we know about $a_{1007}$ and $b_{1007}$, namely, that $2013-k$ is the largest chosen number in the sequence. This means that the sequence of numbers from 0 to 2013 is divided into an even number of groups, each having $k$ elements. Each group would alternate between all being chosen and all being not chosen. It's easy to check that this configuration matches the conditions above.

From there, we know that $2k | 2014$ or $k | 1007$. Because $1007 = 19 \times 53$, then we have four possible values of $k$.

If $k=1$, then both sequences look like this: $0,2,4,\dots, 2012$. Then $S=2012$.

If $k=19$, then both sequences look like this: $0,1,2,\dots,17,18,38,39,\dots,55,56,\dots, 988$. Then $S=1994$.

If $k=53$, then both sequences look like this: $0,1,2,\dots,51,52,106,107,\dots,158,159,\dots, 988$. Then $S=1960$.

If $k=1007$, then both sequences look like this: $0,1,2,\dots,1006$. Then $S=1006.

Now, we have to address the case where 0 is not chosen in $a_i$ and $b_i$. We define new sequences $c_i = 2013-a_{1008-i}$ and $d_i = 2013-b_{1008-i}$. It's easy to see that $c_i,d_i$ satisfy the conditions of the problem, and since $0$ is not chosen in $a_i,b_i$ then 2013 must be chosen in them, which means $0$ is chosen in both $c_i,d_i$. This reduces $c_i,d_i$ to the case above, except $S$ is replaced with $4026-S$.

Because the possible values for $S$ in the first case is $1007,1960, 1994, 2012$ then the possible values for $S$ in this case is $2014,2032,2134,3020$.

Having fun with infinite series

1. Warm-up problem: show that
$$1 + \frac{1}{2} + \frac{1}{3} + \cdots = \infty$$

2. Suppose $a_1, a_2, \cdots$ is a sequence of positive numbers such that
$$a_1 + a_2 + \cdots + a_n \leq n^2$$
for all $n$, show that
$$\frac{1}{a_1} + \frac{1}{a_2} + \cdots = \infty$$

3. Suppose $a_1, a_2, \cdots$ is a sequence of positive numbers such that
$$a_1 + a_2 + \cdots + a_n \leq n^2 \log n$$
for all $n$, show that
$$\frac{1}{a_1} + \frac{1}{a_2} + \cdots = \infty$$

Solution

Problem 1

This is a standard textbook proof of the divergence of harmonic series, but the point here is to prepare the reader for the subsequent proofs $$\frac{1}{3} + \frac{1}{4} > \frac{1}{4} + \frac{1}{4} = \frac{1}{2}$$ $$\frac{1}{5} + \dots + \frac{1}{8} > \frac{1}{8} + \dots + \frac{1}{8} = \frac{1}{2}$$ and so on. So the original series clearly diverges to infinity. The main crux of the proof here is this assertion: $$\frac{1}{2^n+1} + \dots + \frac{1}{2^{n+1}} > \frac{1}{2^{n+1}} + \dots + \frac{1}{2^{n+1}} = \frac{1}{2}$$ for each $n$.

Problem 2

Similar to the proof above, for each $n$ we have: $$a_{2^n+1} + \dots + a_{2^{n+1}} < 4^{n+1}$$ So by AM-HM we have: $$\frac{1}{a_{2^n+1}} + \dots + \frac{1}{a_{2^{n+1}}} > \frac{4^n}{a_{2^n+1} + \dots + a_{2^{n+1}}} > \frac{1}{4}$$ So the original series is greater than $1/4 + 1/4 + \dots = \infty$

Problem 3

Similar to the proof above, for each $n$ we have: $$a_{2^n+1} + \dots + a_{2^{n+1}} < 4^{n+1} \log (2^n) = n . 4^{n+1}.\log 2$$ So by AM-HM we have: $$\frac{1}{a_{2^n+1}} + \dots + \frac{1}{a_{2^{n+1}}} > \frac{4^n}{a_{2^n+1} + \dots + a_{2^{n+1}}} > \frac{1}{4 \log 2 n}$$ So the original series is greater than $\frac{1}{4 \log2} (1 + \frac{1}{2} + \frac{1}{3} + \dots)$ which is also divergent.

General Recursion

Given a recursive formula with $a_{n+1} = 2a_n -1$ and $a_1 = a$, find a general formula for $a_n$.

Sequence modulo 2011

A sequence of integers $a_1, \dots, a_{2010}$ satisfy the following properties:

$a_1 - 1$ is divisible by 2011
$a_k a_{k-1} - k$ is divisible by 2011 for $k = 2, 3, \dots, 2010$

Show that $a_{2010} + 1$ is divisible by 2011.

Solution

First we prove the following assertion:

For $k$ odd, then $a_k.2.4.6. \cdots.(k-1) - 1.3.5.\cdots.k$ is divisible by 2011.
For $k$ even, then $a_k.1.3.5. \cdots .(k-1) - 2.4.6.\cdots.k$ is divisible by 2011.

Proof by induction. It can easily be seen for $k=1$ it's true. For $k=2$, we have $2011 | a_2a_1 - 2 = a_2(a_1-1) + (a_2-2)$ So $2011 | a_2 - 2$

Suppose it's true for $k-1$ odd, then for $k$ even:
$2011 | a_k a_{k-1} - k$ which means
$$2011 | 2.4.\cdots.(k-2) (a_k a_{k-1} - k) = 2.4.\cdots.(k-2)a_k a_{k-1} - 2.4.\cdots.(k-2).k$$
$$2011 | a_k (2.\cdots.(k-2)a_{k-1} - 1.3.\cdots.(k-1)) + (a_k.1.3.\cdots.(k-1) - 2.\cdots.(k-2).k)$$
And since 2011 divides the first term by induction hypothesis, then it also divides the second term, which completes the induction step. The proof for $k-1$ even and $k$ odd is similar.

Now, that means for $k=2010$, let $X = a_{2010}$ we have:
$$2011 | X.1.3. \cdots .2009 - 2.4.\cdots.2010$$

We now prove the following assertion for $i = 1,2,\dots,1005$
$$2011 | X.1.3. \cdots. (2011-2i) + (-1)^i (2i) (2i+2)\cdots.2010$$

For $i = 1$ it is true by definition. Now suppose it's true for $i-1$, then for $i > 1$:
$$2011 | X.1.3. \cdots. (2011 - 2i).(2011-2i+2) +(-1)^{i-1} (2i-2) (2i)\cdots.2010$$
if $2011 | a(2011+b) + c$ then $2011 | ab+c$
$$2011 | X.1.3. \cdots. (2011 - 2i).(-2i+2) + (-1)^{i-1} (2i-2) (2i)\cdots.2010$$
if $2011 | a$ then $2011 | -a$.
$$2011 | X.1.3. \cdots. (2011 - 2i).(2i-2) + (-1)^{i} (2i-2) (2i)\cdots.2010$$
$$2011 | 2(i-1)(X.1.3. \cdots. (2011 - 2i).+ (-1)^{i} (2i)\cdots.2010)$$
if $2011 | 2(i-1)a$ then $2011 | a$ since 2011 is prime and $i > 1$.

So the assertion holds for $i = 1,\dots, 1005$. Particularly, for $i = 1005$ we have:
$$2011 | X - 2010$$
$$2011 | X + 1 - 2011$$
$$2011 | X + 1$$

Sequence of natural numbers

Suppose $a_1,a_2,\dots, a_n,\dots$ is a sequence of natural numbers that satisfy:

$$a_{a_n} = 6n - a_n$$

for all $n$. Find $a_{2011}$.

Solution

For a fixed $n$, let $x_0 = n$
$$x_1 = a_n$$
$$x_2 = a_{x_1}$$
$$x_3 = a_{x_2}$$
$$\cdots$$
$$x_n = a_{x_{n-1}}$$

Then:
$$x_2 = a_{x_1} = a_{a_n} = 6n - a_n = 6x_0 - x_1$$
$$x_3 = a_{x_2} = a_{a_{x_1}} = 6x_1 - a_{x_1} = 6x_1 - x_2$$
In general:
$$x_{n+2} = a_{x_{n+1}} = a_{a_{x_n}} = 6x_n - a_{x_n} = 6x_n - x_{n+1}$$
$$x_{n+2} + x_{n+1} - 6x_n = 0$$

This is a second order recursion with characteristic equation $t^2 + t - 6 = 0$ with solutions $t = -3, t = 2$.

So the general term for $x_n$ is:
$$x_n = P.2^n + Q.(-3)^n$$.
However, for $x_n$ to be positive for all $n$, then $Q$ must be zero, otherwise with large enough $n$, $x_n$ could eventually be negative. Thus $x_n = P.2^n$ for some $P$.

$a_n = x_1 = 2P = 2.P = 2x_0 = 2n$

After substituting back, we find that $a_n = 2n$ satisfies all the constraints, so we have $a_n = 2n$ for all $n$.

Sequence with prime number

Suppose $p$ is a prime number greater than 2, and $m$ is a natural number. Let $a_n$ be sequences defined by:
$a_1 = 1$
$a_2 = m$
$a_{n+2} = \frac{a_{n+1}^2 +p}{a_n}, n = 1,2,...$

Determine all values of $m$ such that $a_n$ is an integer for all $n$.

Combined Sequence

Let $A,B$ be two distinct positive integers greater than 1, and define the sequences:

$a_m = m + \frac{Bm}{A}, m = 1,2,3,\cdots, A-1$
$b_m = m + \frac{Am}{B}, m = 1,2,3,\cdots, B-1$

And combine those two sequence to form a new sequence $c_1,c_2,\cdots, c_{A+B-2}$ with $c_1 \leq c_2 \leq \cdots \leq c_{A+B-2}$.

Prove that the difference between any two consecutive $c_i$s are less than 2.

Solution

It suffices to prove that for each $a_k$, we can find another $a_i$ or $b_j$ that lies between $a_k$ and $a_k+2$, and vice versa, for each $b_l$, we can find another $a_i$ or $b_j$ that lies between $b_l$ and $b_l + 2$.
Without loss of generality, we may assume that $A > B$.
The distance between two consecutive $b_j$s are $b_{j+1} - b_j = 1 + B/A < 2$, so for each $b_l$, we're guaranteed that $b_l < b_{l+1} < b_l+2$.

Now we're left to consider $a_k$.
Fix $k$, and now take the smallest $l$ such that $b_l > a_k$. This is always possible because:
\[a_k \leq a_{B-1} = (B-1)(1+A/B) < (A-1)(1+B/A) = b_{A-1}\]
(the middle inequality is true because $A > B$.)

If $l$ is the smallest such $l$, that means
\[b_{l-1} \leq a_k \iff (l-1)(1+B/A) \leq k(1+A/B) \iff l/A - k/B \leq 1/A\]

So
\[b_l - a_k = l(1+B/A) - k(1+A/B) = (A+B)(l/A - k/B) \leq (A+B)/A < 2\]
which completes the proof

Drawing letters

A string of alphabets are randomly generated one letter at a time. Each time, one obtains the letter $A,\cdots,Z$ with probability $p(A),\cdots, p(Z)$. Given that the sum of these probabilities is 1, what is the expected number of draws before the string "DHARMATH" appears?

Mean of Means

If $a_i,b_i$ are positive numbers for $i=1,\cdots,n$, and

$! M_r (a,b) = \left( \frac{a^r+b^r}{2} \right)^\frac{1}{r}$

Prove that for $0 < r < s$,

$! \displaystyle \sum M_r(a_i,b_i) \sum M_{-r}(a_i,b_i) \leq \sum M_s(a_i,b_i) \sum M_{-s}(a_i,b_i) \leq \sum a_i \sum b_i$

KBB2 Problem 1

If $S_n = 1 + \frac{1}{2} + \cdots + \frac{1}{n}$ for $n$ natural number, prove that:

$S_1 + S_2 + \cdots + S_n = (n+1)(S_{n+1} - 1)$