The Gateway to Computer Science Excellence
+3 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 Others by Veteran (105k points)
retagged by | 171 views
A : true  as it is standard PASCAL INDENTITY
E:TRUE take some values eg 3, 5, 7...... etc it will always be true

but i am not able to eliminate option B and D ??
All seems true.
for option b n!=1*2*3* take any n consecutive number say 3.4.5......n(n+1)(n+2) and divide we get (n+1)(n+2)/2(some value)=any two consecutive no is divisibly by 2 so using the fact numerator becomes 2(some value)/2 which is always divisible...B is correct..
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

3 Answers

+1 vote

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


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.

Please tell me where I'm wrong.

by Loyal (6.3k points)
edited by
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.
0 votes

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$,


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

Hence $D$ false.

Even in the answer key,it is the answer
by Boss (16.2k points)
0 votes

a) It's Pascal's Identity Theorem

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.


by Boss (14.6k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,291 answers
104,889 users