4

Let $n$ be any natural number. Consider all nonempty subsets of the set {$1,2,...,n$}, which do not contain any neighboring elements. Prove that the sum of the squares of the products of all numbers in these subsets is $$(n + 1)! - 1.$$ For example, if $n = 3$, then such subsets of {$1,2,3$} are {$1$}, {$2$}, {$3$}, and {$1,3$}, and $$1^2 + 2^2 + 3^2 + (1\cdot3)^2 = 23 = 4! -1.$$

Is there a way I can write the sum of the squares of the products of all numbers in these subsets is $(n + 1)! - 1$? I'm actually stuck in this problem. This is all I have for this problem but I'm not sure if I'm doing the problem right.

For the Basis step I let $ n= 2$ and the subsets of {$1,2$} are just {$1$} and {$2$}. Thus, $$1^2+2^2 = 5 = 6-1 = 3! -1$$ So, it's true for n=2.

Inductive step: I assume that the statement holds for $n = k$ where $k$ is a natural number. Then the sum of the squares of the products of all numbers in these subsets is $(k+1)!-1$

We have to show that the statement holds for for $n = k+1$. That is to say that the sum of the squares of the products of all numbers in these subsets is $(k+2)! -1$

Please let me know if I'm actually doing the proof right if not correct me. Thanks

Gerry Myerson
  • 179,216
Candy Pelagio
  • 273
  • 2
  • 4
  • 10

1 Answers1

5

Hint:

I would do this with what is called "strong induction" rather than standard induction: instead of assuming the statement holds for $n=k$, assume the statement holds for all $n\leq k$.

Suppose that you have a set $A\subset\{1,2,\ldots,k+1\}$ which does not contain any adjacent elements. What must such a set look like?

If $k+1\in A$, then $A=A'\ \cup\{k+1\}$, where $A'\subseteq\{1,2,\ldots,k-1\}$ does not contain any adjacent elements. You can sum over all $A$ of this type by summing over all such $A'$ (using the inductive hypothesis), noting that inserting the $k+1$ simply multiplies the whole sum by $(k+1)^2$.

If $k+1\notin A$, then we actually have that $A\subseteq\{1,2,\ldots,k\}$ and that $A$ does not contain any adjacent elements. We already know how to sum over these (using the inductive hypothesis).

From here, it should be a matter of adding up the contributions by these two different types of sets, and simplifying.

Nick Peterson
  • 32,430
  • Why do we have to apply strong induction? sorry, I have never done a proof using strong induction. – Candy Pelagio Sep 13 '13 at 14:40
  • @CandyPelagio My apologies for the slow response. If you notice here, our proof of the inductive step (the case $n=k+1$) did not only rely on the assumption that we had proved it for $n=k$... we also needed that we had already proved it for $n=k-1$, in the third paragraph. That's where strong induction comes in to play. It turns out that strong induction is actually just induction... it's just that your inductive assumption is "I have proved this for all $n\leq k$" rather than "I have proved this for $n=k$". – Nick Peterson Sep 16 '13 at 01:31