When the solution is easier than the question

For discussing Olympiad Level Algebra (and Inequality) problems
User avatar
Thanic Nur Samin
Posts:176
Joined:Sun Dec 01, 2013 11:02 am
When the solution is easier than the question

Unread post by Thanic Nur Samin » Thu Feb 23, 2017 11:10 pm

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.

User avatar
Mallika Prova
Posts:6
Joined:Thu Dec 05, 2013 7:44 pm
Location:Mymensingh,Bangladesh

Re: When the solution is easier than the question

Unread post by Mallika Prova » Sat Feb 25, 2017 11:27 pm

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$

If you do what interests you , atleast one person is pleased.

Post Reply