6
$\begingroup$

I stumbled upon the following relationship with small values of $n$. I later verified its correctness with a python script.

$$f([1,2,\cdots,n]) = (n+1)!-1$$

This operation $f$ is defined on a set of integers. I am sure can be expressed using $\sum$ and $\prod$ but I was not able to frame it. I will try to illustrate what this operation is using examples.

If the set was $[a,b]$, then $f([a,b])$ would be $(a+b+ab)$. If the numbers were $[a,b,c]$, it would be $(a+b+c+bc+ab+ac+abc)$. In case of $[a,b,c,d]$, It would be $[(p_1+p_2+p_3+abcd)]$ where $p_1 = (a+b+c+d)$, $p_2 = (ab+ac+ad+bc+bd+cd)$ and $p_3 = (abc+abd+acd+bcd)$.

1) So if the set was $[x_1, x_2, \cdots, x_n]$ what would the closed form representation of $f([x_1, x_2, \cdots, x_n])$ be?

2) For the case that the set is $[1,2,3,\cdots,n]$ , Please prove that $$f([1,2,\cdots,n]) = (n+1)!-1$$


This is my attempt,

$$\sum_{i=1}^nx_i + \sum_{i\neq j}^nx_ix_j + \cdots + \prod_{i=1}^nx_i$$

For the case that the set is $[1,2,3,\cdots,n]$ (which is the case that is of special interest to me) I tried writing it as,

$$n! + n!\left ( \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots \frac{1}{n} \right ) + n!\left ( \frac{1}{1\times2} + \frac{1}{1\times3} + \cdots + \frac{1}{1\times n} + \frac{1}{2\times 3} + \frac{1}{2\times 4} +\cdots \frac{1}{n(n-1)} \right ) + \cdots$$


Here is my implementation of the function $f$,

from random import randint
import math
n = 4

# index -> 0  to 198
s = list(range(1,n+1))

while(len(s)>1 and False):
    indexA = randint(0,len(s)-1)
    a = s[indexA]
    s.remove(a)

    indexB = randint(0,len(s)-1)
    b = s[indexB]
    s.remove(b)

    s.append(a+b+a*b)
    print(s)

# The only element left in the list
ans1 = s[0]
ans2 = math.factorial(n+1)-1
print("Final Answer = "+str(ans1)+"\n")
print("(n+1)! - 1 = "+str(ans2))

In case you are confused about the way I implemented this function, you can check out my motivativation for this question here.

Any suggestions to improve the question, propose tags is appreciated.

$\endgroup$
  • $\begingroup$ Hint. In your last line use partial fractions to make a telescoping sum: $1/n(n+1) = 1/n - 1/(n+1)$. (I haven't read the question carefully, so perhaps this in no use at all.) $\endgroup$ – Ethan Bolker Nov 18 '16 at 13:38
7
$\begingroup$

You have $$ f([a, b]) = a + b + ab = (1+a)(1+b) - 1 \\ f([a, b, c]) = a+b+c+bc+ab+ac+abc = (1+a)(1+b)(1+c) - 1 $$ and in general $$ f([x_1, x_2, \dots, x_n]) = (1+x_1)(1+x_2)\cdots(1+x_n) -1 $$ In particular $$ f([1, 2, \dots, n]) = 2 \cdot 3 \cdots (n+1) -1 = (n+1)! - 1 $$

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

Let

$$g(n)=f\left(\left[1,2,\dots,n\right]\right)+1$$

You can think of this as the same sum, but including the empty product.

Clearly:

$$g(0)=1=(0+1)!$$

Perhaps less obviously:

$$g(n+1)=g(n)+(n+1)g(n)$$

Since $g(n)$ contains exactly all the products that do not include $n+1$, and $(n+1)g(n)$ contain exactly all the products that do include $n+1$.

So it follows by induction that $g(n)=(n+1)!$

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

The different terms that you have in your sum are called the symmetrics polynoms here.

It's a classical way to link the racines of a polynom with its coefficients. Indeed in your big sum, the i-th term is a symmetric polynom that is equal to the i-th coefficient of your polynom (with a $(-1)^{n-i}$ factor).

In your case we can consider the polynom whose racines are 1,2...,n. And this polynom can also be expressed as follow:

$P(X)=(X-1)...(X-n)$,

Let's note $a_i$ the coefficient of $X^i$ in this polynom. We can now notice that

$P(-1) = (-1)^n(n+1)! = (-1)^n(1 + \sum_{i=0}^{n-1}(-1)^{n-k}a_k)$

and the term $\sum_{i=0}^{n-1}(-1)^{n-k}a_k$ is exactly your sum (convince yourself and check wikipedia page for help), and we finally find out that:

Your sum $= \sum_{i=0}^{n-1}(-1)^{n-k}a_k = (n+1)! -1$

Hope it helps.

Cheers,

Adam

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.