InterviewSolution
Saved Bookmarks
InterviewSolution
| 1. |
Prove that `2^k(n,0)(n,k)-2^(k-1)(n,1)(n-1,k-1)+2^(k-2)(n,2)(n-2,k-2)-.....+(-1)^k(n,k)(n-k,0)=(n,k)`. |
|
Answer» To show that `2^(k).""^(n)C_(0).""^(n)C_(k)-2^(k-1).""^(n)C_(1).""^(n-1)C_(k-1)+2^(k-2).""^(n)C_(2).""^(n)C_(k-2)-...+(-1)^(k)""^(n)C_(k)""^(n-k)C_(0)=""^(n)C_(k)` Taking LHS `2^(k).""^(n)C_(0).""^(n)C_(k)-2^(k-1).""^(n)C_(1).""^(n-1)C_(k-1) +... +(-1)^(k)""^(n)C_(k).""^(n-k)C_(0)` `=sum_(r=0)^(k)(-1)^(r).2^(k-r).""^(n)C_(r)""^(n-r)C_(k-r)` `= sum _(r=0)^(k)(-1)^(r)2^(k-r).(n!)/(r!(n-r)!).((n-r)!)/((k-r)!(n-k)!)` `= sum _(r=0)^(k)(-1)^(r).2^(k-r).(n!)/(r!(n-r)!k!).(k!)/(r!(k-r)!)` `= sum _(r=0)^(k)(-1)^(r).2^(k-r). ""^(n)C_(k).""^(n)C_(r)=2^(k).""^(n)C_(k){sum _(r=0)^(k)(-1)^(r).(1)/(2^(r))""^(k)C_(r)}` `=2^(k).""^(n)C_(k)(1-(1)/(2))^(k)=""^(n)C_(k)=RHS ` |
|