in Combinatory recategorized by
609 views
4 votes
4 votes

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

  1. $\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$
  2. $n!$ divides the product of any $n$ consecutive integers
  3. $\Sigma_{i=0}^n \begin{pmatrix} n \\ i \end{pmatrix} = 2^n$
  4. $n$ divides $\begin{pmatrix} n \\ i \end{pmatrix}$, for all $ i \in \{1, 2, \dots , n-1\}$
  5. If $n$ is an odd prime, then $n$ divides $2^{n-1} -1$
in Combinatory recategorized by
609 views

4 Comments

all true how ??
0
0
@kunal , u can write b as C(n+k,k).
0
0
B is a standard theorem.

D is also standard theorem.

ALL right
0
0

3 Answers

1 vote
1 vote

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.

edited by

3 Comments

Yes all are true
1
1
$\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.
1
1
$(D)$ will be true when $n$ is prime.
0
0
0 votes
0 votes
$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
0 votes
0 votes

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

Answer:

Related questions