Page 1 of 1
When the solution is easier than the question
Posted: Thu Feb 23, 2017 11:10 pm
by Thanic Nur Samin
Consider all possible subsets of $\{1, 2, . . . ,N\}$ which contain no neighbouring elements. Prove that the sum of the squares of the products of all numbers in these subsets is $(N + 1)! - 1$.
Re: When the solution is easier than the question
Posted: Sat Feb 25, 2017 11:27 pm
by Mallika Prova
True for $ n=2, n=3 $... assume its true for $k \le n$
let $S_n$ denote the sum of the squares of the products of the subsets of $ \{1,2,....,n \} $
now, from the set $\{1,2,....,k+1\}$ the element $k+1$ has each non-neighbouring elements from non-neighbouring subsets of $\{1,2,....,k-1\}$ that,
$S_{k+1}= S_k + ((k+1)^2.S_{k-1})+(k+1)^2$
$=(k+1)!-1+((k+1)^2.(k)!-1)+(k+1)^2 $
$=2(k+1)!+k(k+1)!-1 $
we get $(k+2)!-1$