0

Consider all non-empty subsets of $\{1, 2, \ldots, n\}$ having no consecutive elements. Prove that sum of squares of products of these subsets equals $(n + 1)! − 1$: i.e. if $\mathcal{C}_n$ is the set of all such subsets, $$ \sum_{J\in\mathcal{C}_n}\left(\prod_{i\in J}i\right)^2 = (n+1)!-1. $$ Note that if we were to include the empty set in $\mathcal{C}_n$ and define the product for this to be $1$, the sum would be $(n+1)!$ instead.

N. F. Taussig
  • 76,571
user3078441
  • 147
  • 1
    What do you mean by sum of squares of products of these subsets? $\sum \Pi a_i^2$? – Ma Ming Apr 25 '14 at 13:24
  • I think so ! the original question is in Persian language and I translated it. Can it be interpreted by another mathematics notation ? – user3078441 Apr 25 '14 at 13:34
  • Feel free to edit the question because I've some difficulties with writing them ! maybe it's the time to learn LaTeX !!! – user3078441 Apr 25 '14 at 13:41
  • 1
    @user3078441, to see how a formula is written, right-click on it, hover over "Show Math As," and then click "Tex commands." You'll learn LaTeX pretty quickly this way. Don't forget to enclose your TeX commands in dollar signs so they render correctly. – goblin GONE Apr 25 '14 at 13:44

2 Answers2

4

It follows from induction immediately.

Any such subset of n+1, arises from a subset of n, or a subset of n-1 union the element n+1 or the subset of the element n+1 itself.

We have $(n+1)! -1$ plus $(n+1)^2[n!-1]+(n+1)^2$ Plus $(n+1)^2$ which gives us $(n+2)!-1$

Calvin Lin
  • 68,864
1

Let $\mathcal{C}^*_n=\mathcal{C}_n\cup\{\{\}\}$ consist of all subsets of $\{1,\ldots,n\}$ with no two consecutive elements, including the empty set: i.e. $J\in\mathcal{C}^*_n$ if $J\in\{1,\ldots,n\}$ and there is no $i$ so that $i\in J$ and $i+1\in J$. Now, let $$ S_n=\sum_{J\in\mathcal{C}^*_n}\left(\prod_{i\in J}i\right)^2 $$ where $\prod_{i\in\{\}}i=1$ for the empty set. We wish to prove that $S_n=(n+1)!$. To get the original problem, remove the empty set from the sum which corresponds to subtracting $1$.

For $n=0,1$, it's easy to check that $S_n=(n+1)!$. So next, we do induction on $n$.

Assuming $S_k=(k+1)!$ for $k<n$, we split the sets of $\mathcal{C}^*_n$ into those that contain $n$ and those that do not. The elements that do not contain $n$ are those of $\mathcal{C}^*_{n-1}$; the elements that contain $n$ correspond to $J\cup\{n\}$ where $J\in\mathcal{C}^*_{n-2}$. Thus, we get $$ S_n =\sum_{J\in\mathcal{C}^*_{n-1}}\left(\prod_{j\in J}j\right)^2 +\sum_{J\in\mathcal{C}^*_{n-2}}\left(n\cdot\prod_{j\in J}j\right)^2 $$ which gives us $S_n$ expressed in terms of $S_{n-1}$ and $S_{n-2}$: $$ S_n=S_{n-1}+n^2\cdot S_{n-2}=n!+n^2\cdot(n-1)!=(n+1)! $$ or $(n+1)!-1$ if we remove the empty set and sum over $\mathcal{C}_n$ instead.

Einar Rødland
  • 9,707