Daniel's symmetric sum

Full Solution

Note that:

$\displaystyle \sum_{k=1}^{101} S_{k} = (1+1)(2+1)(3+1) \ldots (100+1)(101+1)-1$

$\equiv 0-1 \pmod{101} \equiv 100 \pmod{101}$

Therefore $\boxed{100}$ is the answer.

Motivation and thought process

Since this is a huge expression, I immediately thought of factorising the expression. Instead of having numbers in set $S$ , I decided to replace them with $S=\left\{a_{1},a_{2}, \ldots ,a_{101}\right\}$ .

At first I wasn't sure how to begin factorising, so I decided to try simpler versions of the summation:

$S= \left\{a_{1},a_{2}\right\}, \displaystyle \sum_{k=1}^{2} S_{k} = a_{1}+a_{2}+a_{1}a_{2}=(a_{1}+1)(a_{2}+1)-1$

$S= \left\{a_{1},a_{2},a_{3}\right\}, \displaystyle \sum_{k=1}^{3} S_{k} = a_{1}+a_{2}+a_{3}+a_{1}a_{2}+a_{2}a_{3}+a_{3}a_{1}+a_{1}a_{2}a_{3}$

$=(a_{1}+1)(a_{2}+1)(a_{3}+1)-1$

Why can it be factorised in such a way? This question can be answered using the degrees of the terms. For example, if we wanted the sum of all the terms with degree $2$ ( $S_{2}$ ), we simply choose two $a$ values, let's say $a_{1}$ and $a_{2}$ , and choose $1$ s for all other terms, obtaining a degree 2 term. Repeating for every single pair of $a$ values and taking the sum, we end up with $S_{2}$ . This can be repeated for every degree. Since the summation does not have $1$ , we put a $-1$ at the end of the product.

Thus, returning back to the question, it is now clear that the summation can be factorised into

$(a_{1}+1)(a_{2}+1)(a_{3}+1)...(a_{101}+1)-1$

Subbing $a_{1} = 1$ , $a_{2} = 2$ , etc., we get

$(1+1)(2+1)(3+1) \ldots (100+1)(101+1)-1$ .

Generalisation

For set $S=\left\{a_{1}, a_{2}, \ldots ,a_{n} \right\}$ , $\displaystyle \sum_{k={a_1}}^{a_n} S_{k} = (a_{1}+1)(a_{2}+1)(a_{3}+1)...(a_{n}+1)-1$

Motivation: We see all possible $k$ products in the problem, which reminds us of Vieta's formulae . So let us try to think in terms of polynomial.

Now consider a monic polynomial $p(x)$ of degree $101$ whose roots are ${1,2,3,...,101}$ . Clearly,

$p(x)=\prod_{i=1}^{i=101} (x-i)$

We also see that in the expanded form, we can write $p(x)$ as:

$p(x)=\sum_{k=0}^{101}a_{k}x^{101-k}$

and $a_{0}=1$

Using Vieta's relations for $p(x)$ , we get,

$a_{k}=(-1)^{k}S_{k}$

Also, using expanded form of $p(x)$ , we get,

$p(-1)=-1-\sum_{k=1}^{101}S_{k}$

$\therefore \sum_{k=1}^{101}S_{k}=-1-p(-1)$

Using product form of $p(x)$ , we find that,

$p(-1)=(-2)\times(-3)\times...\times(-102)=-102!$

Hence, we get,

$\sum_{k=1}^{101}S_{k}=102!-1$

This shows that we need to subtract $100$ from $\sum_{k=1}^{101}S_{k}$ so that resulting number would be divisible by $101$ .

Hence the required remainder is: $\boxed{100}$

Let $f(x) = (x + 1)(x + 2)...(x + 101)$ . We note that $f(1)$ is the sum of coefficient of the polynomial. Also, note that the required sum is equal to the sum of coefficients of $f(x)$ minus $1$ . (Indeed, it is easy to see this by expanding the polynomial or Vieta's formula.) Let $S$ be the required sum. Then, $S = f(1) - 1 = 102! - 1 \equiv -1 \equiv \boxed{100} \pmod{101}$ .

We know the order of 2 must divide 100. We can check by hand that none of $2, 2^2, 2^5, 2^{10}, 2^{20}, 2^{50}$ are congruent to 1. Therefore 2 is a primitive root and $2^k \ncong \ 1$ for $1 \le k \lt 100$

Now note that $2^k S_k \equiv \ S_k$ since multiplying by 2 is a permutation.
So $S^k ( 2^k - 1) \equiv 0$ and when $k \lt 100$ then $2^k \ncong 1$ hence $S_k \equiv 0$ for $k \lt 100$

Then $S_{100} = -1$ by Wilson's theorem, and the result follows.

At first the notations are really scary, so it is good to work with smaller cases first. Suppose we have a smaller set called $N=\{1,2,3,4\}$ If so by defination we get that;

$N_1=1+2+3+4$

$N_2=1*2+1*3+1*4+2*3+2*4+3*4$

$N_3=1*2*3+1*2*4+1*3*4+2*3*4$

$N_4=1*2*3*4$

So looking at this, we see that $N_k$ somehow relates to Vieta's theorem. At which $N_k$ repersents the $x^{n-k}$ coefficient of the monic polynomial with roots $1$ to $n$ .

More generally if the set is $X=\{a_1,a_2,...,a_{n-1},a_n\}$ Then;

$X_1=a_1+a_2+...+a_{n-1}+a_n$

$X_2=a_1*a_2+a_1+a_3+...+a_{n-2}*a_{n-1}+a_{n-1}*a_{n}$

$...$

$X_k=a_1*a_2*...*a_{k}+a_1*a_2*...*a_{k+1}+...+a_{n-k+1}*...*a_n$

$...$

$X_n=a_1*a_2...*a_n$

So we can conclude that,

$(x-a_1)(x-a_2)...(x-a_n)=x^n+(-1)^1X_1x^{n-1}+(-1)^2X_2x^{n-2}+....+(-1)^{n-1}X_{n-1}x+(-1)^{n}X_n$

by Vieta's theorem.

So we have the set $S=\{1,2,3...,101\}$ , applying this to the polynomial we just found,

$(x-1)(x-2)...(x-101)=x^{101}-S_1x^{100}+...+S_{100}x-S_{101}$

So to find $\displaystyle \sum_{k=1}^{101} S_k$ we let $x=-1$

$(-1-1)(-1-2)...(-1-101)=(-1)^{101}-S_1(-1)^{100}+...S_{100}(-1)-S_{101}$

$\Rightarrow -102!=-1-S_1-S_2-...-S_{100}-S_{101}$

$\Rightarrow 102!=1+S_1+S_2+...+S_{100}+S_{101}$

$\Rightarrow \displaystyle \sum_{k=1}^{101} S_k =102!-1$

If so, we know that $102! \equiv 0 \mod 101$

Therefore,

$102!-1 \equiv -1 \mod 101$

or $102!-1 \equiv 100 \mod 101$

Hence $\displaystyle \sum_{k=1}^{101} S_k \equiv \boxed{100} \mod101$

We use the fact that symmetric sums are very close to polynomials. For example to solve a quadratic equation, one might use that $(x-a)(x-b) = x^2 - (a+b)x + ab$ to relate the roots with the coefficients of the equation. Here $a+b$ is the first symmetric sum and $ab$ the second symmetric sum. Let's move one dimension up to see the pattern $(x + x_1) (x + x_2) (x + x_3) = x^3 + x^2 \cdot S_1 + x \cdot S_2 + S_3$ where $S_1 = x_1 + x_2 + x_3$ $S_2 = x_1 x_2 + x_2 x_3 + x_3 x_1$ and $S_3 = x_1 x_2 x_3$ . It's straightforward to generalize this to any dimension as $\prod_{i=1}^n (x + x_i) = \sum_{i=0}^n x^{n-i}\cdot S_i$ where we used $S_0 = 1$ for convenience.

To get back to the original problem, notice that when we put $n = 101$ , $x = 1$ and $x_i = i$ we get almost the sum in the question. $\sum_{k=1}^{101} S_k = \prod_{k=1}^{101} (1 + k) - 1.$ But the product collapses because it also contains $k = 100$ and $1 + 100 \equiv 0 \pmod{101}$ and so the answer is $-1$ or, more neatly, $\bf 100$ .

Consider the polynomial $P(X) = (X + 1)(X + 2) \cdots (X + 101) = X^{101} + S_1 X^{100} + \cdots + S_{101}$ Pluggin in $P(1)$ , we get $1 + S_1 + \cdots + S_{101} = 102! \equiv 0 \pmod{101}$ , so the answer is $100$

The fact that 101 is prime is irrelevant. If we add 1 to the sum, we get the sum of all products of all subsets of S, which factors cleanly into $\prod_{x \in S} ( 1 + x)$ (we see easily that each subset's product occurs exactly once when this is expanded). This is divisible by 101 since 100 is in S. Therefore the original sum is congruent to -1 mod 101, i.e. 100.

Symmetric sums remind me of Vieta's formulas, which express the symmetric sums in terms of the coefficients of a polynomial. So, let

$\qquad f(x) = (x-1)(x-2)\ldots(x-101). \qquad \textbf{(1)}$

Expanding, we get $\begin{aligned} f(x) &= x^{101} - (1+2+\ldots + 101) x^{100} + \ldots - 1\cdot2\cdots101 \\ &= x^{101} - S_1 x^{100} + S_2 x^{99} - \ldots + S_{100} x - S_{101}. \end{aligned}$

Great! We have an expression containing every symmetric sum. Now, we want to set $x$ equal to some number, to get the summation we want. The only problem, however, is that the signs of the sums are alternating. Luckily, we can fix this by setting $x = -1$ :

$\begin{aligned} f(-1) &= (-1)^{101} - S_1 (-1)^{100} + S_2 (-1)^{99} - \ldots + S_{100} (-1) - S_{101} \\ &= -1 - S_1 - S_2 - \ldots - S_{100} - S_{101} \\ &= -1 - \sum_{k = 1}^{101} S_k. \end{aligned}$

(It is a well-known fact that for positive integers $n,$ $(-1)^n = 1$ if $n$ is even, and $(-1)^n = -1$ if $n$ is odd. So, the powers of $-1$ also alternate, which motivated this step.)

But we also know that

$f(-1) \equiv 0 \pmod{101},$

since in equation $(1),$ $f(-1)$ is a product of integers which contains the term $-101.$ Thus $-1 - \sum_{k = 1}^{101} S_k \equiv 0 \pmod{101}$ so $\sum_{k = 1}^{101} S_k \equiv \boxed{100} \pmod{101}.$

Remark: Note that we never used the fact that $101$ is prime; we can easily generalize this solution for any positive integer $n,$ instead of $101.$

We can prove that, $(x-1)(x-2) \ldots (x-101)=x^{101}-S_1x^{100}+S_2x^{99}-S_3x^{98}+\ldots+S_{100}x-S_{101}$ . Now put $x=-1$ in the above identity we get, $S_1+S_2+\ldots+S_{101}=2*3*\ldots*102-1$ . Now $\sum_{k=1}^{101}S_k (\mod 101)=-1(\mod 101)=100$

Consider the polynomial $f(x)$ with the elements of $S$ as roots. This polynomial is $f(x)=(x-1)(x-2)\cdots(x-101)=x^{101}+a_1x^{100}+\cdots+a_{101}$ where the $a_1,a_2,\cdots,a_{101}$ are constants.

By Vieta's formulas, the answer is $-a_1+a_2-a_3+\cdots-a_{101}$ However, notice that $f(-1)=-1+a_1-a_2+a_3-\cdots+a_{101}$ so the answer is $-f(-1)-1=-(-1-1)(-1-2)\cdots(-1-101)-1=102!-1$ Finally, $102!-1\equiv -1\equiv \boxed{100}\pmod{101}$

Motivation: Symmetric sums reminds me of Vieta's, and $f(-1$ being alternating signs on the coefficients is a handy trick to know.

We have that $S_1+S_2+...+S_{101} = (1+1)(1+2)(1+3)...(1+101)-1=$ $=102! - 1\equiv -1\equiv 100\bmod 101.$

If we observe S1 ≡ 0(mod 101) , similarly S2 ≡ 0(mod 101) but only S100≡ -1(mod 101) since the product of the subset {1,2,3,4,…100} is ≡ -1(mod 101)

On careful observation we see that the values of Sk are the coefficients of the equation::

(x+1)(x+2)(x+3)........(x+101)

so to get the value of the summation part we put 1 (one) in the above expression and subtract 1(as the first term contains only x^101)

So we get (102! - 1) % 101

101 divides 102! but not 1 so we get the modulus as -1 (or the +ve mod as 100 (ANSWER ==100))