We denote $N_{2010}=\{1,2,\cdots,2010\}$ (a)How many non empty subsets does this set have? (b)For every non empty subset of the set $N_{2010}$ we take the product of the elements of the subset. What is the sum of these products? (c)Same question as the (b) part for the set $-N_{2010}=\{-1,-2,\cdots,-2010\}$. Albanian National Mathematical Olympiad 2010---12 GRADE Question 2.
Problem
Source:
Tags: induction, algebra unsolved, algebra
02.03.2011 11:50
Let us rather work with the set $\{1,2,\ldots,n\}$. (a) The answer trivially is $2^n - 1$. (b) The answer is $\prod_{k=1}^n (1+k) - 1 = (n+1)! - 1$. (c) The answer is $\prod_{k=1}^n (1-k) - 1 = - 1$.
02.03.2011 12:09
ridgers wrote: We denote $N_{2010}=\{1,2,\cdots,2010\}$ (a)How many non empty subsets does this set have? (b)For every non empty subset of the set $N_{2010}$ we take the product of the elements of the subset. What is the sum of these products? (c)Same question as the (b) part for the set $-N_{2010}=\{-1,-2,\cdots,-2010\}$. Albanian National Mathematical Olympiad 2010---12 GRADE Question 2. (a)$2^{2010}-1$ (b) ${(x+1)(x+2)\cdots(x+n)=x^n+(1+2+\cdots+n)x^{n-1}+(1\cdot2+1\cdot3+\cdots)x^{n-1}+\cdots+1\cdot 2\cdots n}$ for $x=1$ Required Sum $=(n+1)!-1$ For $n=2010$ Answer$=2011!-1$ (C) ${(x-1)(x-2)\cdots(x-n)=x^n-(1+2+\cdots+n)x^{n-1}+(1\cdot2+1\cdot3+\cdots)x^{n-1}-\cdots+(-1)^n1\cdot 2\cdots n}$ for $x=1$ Required Sum $= -1$ Edit: beaten
09.05.2012 17:26
We solve the problem for general $N_n=[1, n] \cap \mathbb N$. (a) In building a subset we can choose for every element to include it or not, and this gives every subset exactly once. Removing the empty set from the counting, we get the answer $2^n-1$. (b) Given every product of our sum, in adding the $n+1$-th term we can choose for every addend $P$ to include it (multiplying by $n+1$) or not (multiplying by $1$); the first case gives $nP$ and the second just $P$. We include the term $+n$ alone left out and deduce that $N_{n+1}=(n+1)N_n+n$, from which a straight-forward induction shows that $N_n=(n+1)!-1$. (c) With the same reasoning of (b), we get the recurrence $N_{n+1}=(1-n)N_n-n$, from which $N_n=-1$. In particular, for $n=2010$ this gives the answers $2^{2010}-1$, $2011!-1$ and $-1$ respectively.