Jasper's sum of subset products

Looking at the first few cases, we note that $S_1=1, S_2=2, S_3=3$ .

So it remains to prove the case in general, (ie $S_{2013}=2013$ )

We show this by induction:

We take a base case of n = 1, $S_1=1$ is trivial.

Now suppose $S_n=n$

Then note that $S_{n+1}$ contains all the fractions in $S_n$ , and to catch all the new subsets we add $\frac{1}{n+1}S_n$

(Since the new subsets are just all the old ones with the addition of n+1)

We add a $\frac{1}{n+1}$ to account for the set of just n+1, giving:

$S_{n+1}=S_n+\frac{S_n}{n+1}+\frac{1}{n+1}=n+1, QED$

So we now have that $S_{2013}=2013$ , which has sum of digits $\fbox{6}$

Firstly, we will prove that $S_n=n$ . From the given sum, adding 1 to each side, we will have $S_n+1=(1+1)(1+\dfrac{1}{2})(1+\dfrac13)(1+\dfrac14)...(1+\dfrac1n)$ $S_n+1=2.\dfrac32.\dfrac43...\dfrac{n+1}{n}$ $S_n+1=n+1$ $S_n=n$ So $S_{2013}=2013$ , and its sum digits is $6$

We begin by testing cases with small $n$ . For $n = 1$ , $S_1 = \frac{1}{1} = 1$ . For $n = 2$ , $S_2 = \frac{1}{1} + \frac{1}{2} + \frac{1}{1 \cdot 2} = 1.$ For $n = 3$ , $S_3 = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{1 \cdot 2} + \frac{1}{1 \cdot 3} + \frac{1}{2 \cdot 3} + \frac{1}{1 \cdot 2 \cdot 3} = 3.$ We thus conjecture that $S_n = n$ . We notice that $S_n - S_{n - 1} = \frac{1}{n} + \frac{S_{n - 1}}{n}$ . Through induction, we see that $S_n = S_{n - 1} + \frac{1}{n} + \frac{S_{n - 1}}{n} = \left(n - 1\right) + \frac{1}{n} + \frac{n - 1}{n} = n.$ We note that $S_1 = 1$ , so $S_{2013} = 2013$ and its digit sum is $2 + 0 + 1 + 3 = 6$ .

$\frac{1}{1}$ + $\frac{1}{2}$ + $\frac{1}{3}$ + $\frac{1}{1\times 2}$ + $\frac{1}{1\times3}$ + $\frac{1}{2\times3}$ + $\frac{1}{1\times2\times3}$

=( $\frac{1}{1}$ + $\frac{1}{2}$ + $\frac{1}{3}$ + $\frac{1}{1\times 2}$ + $\frac{1}{1\times3}$ + $\frac{1}{2\times3}$ + $\frac{1}{1\times2\times3}$ +1)-1

=(1+ $\frac{1}{1}$ )(1+ $\frac{1}{2}$ )(1+ $\frac{1}{3}$ )-1

= $\frac{2}{1}\times\frac{3}{2}\times\frac{4}{3}$ -1

=4-1

=3

WLOG

Answer=2+0+1+3

If we put S 2013 under a common denominator, the numerator becomes (1+1)(2+1)...(2013+1)-2013! and the denominator is 2013!. But then S 2013 = 2014!/2013! - 2013!/2013! = 2014-1=2013. It follows the answer is 2+0+1+3=6.

We can recursively determine the values of $S_n$ and regroup these to notice that $S_n = S_{n-1}+\frac{1}{n}S_{n-1}+\frac{1}{n}$ . For instance, $S_3 = \frac{1}{1}+\frac{1}{2}+\frac{1}{1\cdot 2} + \frac{1}{3}(\frac{1}{1}+\frac{1}{2}+\frac{1}{1\cdot 2}) + \frac{1}{3}$ .

Assuming $S_{n-1}=n-1$ , this gives $S_n = \frac{n+1}{n}(n-1)+\frac{1}{n} = \frac{n^2}{n}=n$ and so, inductively, we notice $S_n=n$ . The sum of digits of $2013$ of course is 6.

Let $A={1,2,3,..,n}$ and lets look at non-empty subsets of A. When n=1 They are $(1)$ . The non-empty subsets of A when n=1 are also valid when n=2. The non-empty subsets when n=2 that are not in case n=1 can be obtained by adding 2 to every non-empty subset when n=1 and also adding $(2)$ to the list. Hence the non-empty subsets of A when n=2 are $(1),(2),(1,2)$ . Generally in case n the non-empty subsets of A are the non-empty subsets of A in case n-1, the non-empty subsets of A in case n-1 with n added to them and $(n)$ .

Lets now look at the sum given in the problem. By the exercise above it can easily be found that $S_{2}=\frac{1}{1}+\frac{1}{1\times2}+\frac{1}{2}$ . To find $S_{3}$ we use the procedure above and find that $S_{3}=\frac{1}{1}+\frac{1}{1\times2}+\frac{1}{2}+\frac{1}{3}(\frac{1}{1}+\frac{1}{1\times2}+\frac{1}{2})+\frac{1}{3}=S_{2}+\frac{1}{3}S_{2}+\frac{1}{3}$ . Using this procedure we find that in general $S_{n}=S_{n-1}+\frac{1}{n}S_{n-1}+\frac{1}{n}$ (we "add" n to a subset by multiplying with $\frac{1}{n}$ ). Now we use induction to show that $S_{n}=n$ . It is trivial that $S_{1}=1$ so we assume for $n \geq 1$ that $S_{n}=n$ . Then we have:

$S_{n+1}=S_{n}+\frac{1}{n+1}S_{n}+\frac{1}{n+1}$

$=n+\frac{1}{n+1}n+\frac{1}{n+1}=n+\frac{n+1}{n+1}=n+1.$

Therefore for every $n \geq 1$ , $S_{n}=n$ . So $S_{2013}=2013$ , hence the answer $2+0+1+3=6$ .

Take 1 / ( n ! ) We get the following as the numerator

Summation of single terms + Summation of ( product of two ) terms + Summation of ( product of three ) terms + ..............+ Summation of ( product of n - 1 ) terms

Consider the numerator as a quadratic expression in x :

[ ( x + 1 )( x + 2 )( x + 3 )( x + 4 )................( x + n ) ] - n!

The above expression is valid for x = 1 : So putting x = 1

we get Numerator = ( n + 1 ) ! - n !

We had taken common n ! in the beginning ; so dividing the above with n !

We get Sn = [ ( n + 1 ) ! - n ! ] / ( n ! )

or Sn = n ...........

Answer is 2 + 0 + 1 + 3 = 6

S2013 is 2013.The question here is sum of digits of S2013 which is 6

/{S_{3}/}=3

Therefore, /{S_{2013}/}=2013

The sum of the digits is 2+0+1+3=6

6 is the answer