TIFR CSE 2016 | Part A | Question: 13

Question

Let $n \geq 2$ be any integer. Which of the following statements is not necessarily true?

• A. $\begin{pmatrix} n \\ i \end{pmatrix} = \begin{pmatrix} n-1 \\ i \end{pmatrix} + \begin{pmatrix} n-1 \\ i-1 \end{pmatrix}, \text{ where } 1 \leq i \leq n-1$
• B. $n!$ divides the product of any $n$ consecutive integers
• C. $\Sigma_{i=0}^n \begin{pmatrix} n \\ i \end{pmatrix} = 2^n$
• D. $n$ divides $\begin{pmatrix} n \\ i \end{pmatrix}$, for all $ i \in \{1, 2, \dots , n-1\}$
• E. If $n$ is an odd prime, then $n$ divides $2^{n-1} -1$

Comments

all true how ??

---

@kunal , u can write b as C(n+k,k).

---

B is a standard theorem.

D is also standard theorem.

ALL right

Answer 1

A,B,C are true due to usual reasons.

Now,

Let a = 2 which is not divisible by n, then using Fermat's little theorem

$2^{n-1}\equiv 1(mod n)$

$\Rightarrow$ $2^{n-1} -1\equiv 0(mod n)$

Therefore E is true.

D. But it also seems to be correct within given range.

For n= 1 : n divides $\frac{n(n-1)}{2}$ and so for n-1.

For i = k, k between 1 & n-1. n divides $\frac{n(n-1)(n-2)...(n-k+1)}{k!}$ , Since there is n at numerator always. Therefore True.

Comments

Yes all are true

---

$\binom{4}{2}$ = 6 is not divisible by 4.

Problem is n in your numerator may be consumed by $factorial(k)$ and now you don't have n.

---

$(D)$ will be true when $n$ is prime.

Answer 2

$D$

If $a$ divides $b$$\Rightarrow a\,\,|\,\,b\Rightarrow \,b=a*c$ for some integer $c$

$n$ divides $\begin{pmatrix} n \\ i \end{pmatrix}$, for all $ i \in \{1, 2, \dots , n-1\}$

 

take $n$=even,

say $n=6,i=2$,

$\binom{6}{2}=15$

$15\neq c*6$ for any $c$.

Hence $D$ false.

Even in the answer key,it is the answer

Answer 3

a) It's Pascal's Identity Theorem

https://en.wikipedia.org/wiki/Pascal%27s_rule

b) It's quite tricky. We know $nCr$ is always an integer.

$nCr$= $\frac{n!}{r!*(n-r)!}$ = $\frac {r! * (r+1)(r+2)...n}{(n-r)!*r!}$

NOw observe this carefully $(r+1)(r+2)...(n)$ are product of any consecutive $(n-r)$integers and this would be divisible by $(n-r)!$ because $nCr$ is always an integer.

c) Quite basic. $nC0+nC1+nC2+....nCn$=$2^n$

d) If $n$ and $r$ are relatively prime then certainly $nCr$ is divisible by $n$.When they are not co prime we can't claim anything.

e)https://en.wikipedia.org/wiki/Fermat%27s_little_theorem