When the solution is easier than the question
- Thanic Nur Samin
- Posts:176
- Joined:Sun Dec 01, 2013 11:02 am
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$.
Hammer with tact.
Because destroying everything mindlessly isn't cool enough.
Because destroying everything mindlessly isn't cool enough.
- Mallika Prova
- Posts:6
- Joined:Thu Dec 05, 2013 7:44 pm
- Location:Mymensingh,Bangladesh
Re: When the solution is easier than the question
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$
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$
If you do what interests you , atleast one person is pleased.