1

my solution is to re-write the statement into $n(n-1)\cdots(n-k+1)$. Therefore, $[n(n-1)\cdots(n-k+1)]/(k!) = {n \choose k}$ which yields an integer therefore it is a multiple of $k!$.

Or should i do by mathematical induction? If MI , how so?

For MI , i assume $P_m$ is true . I.e : $[m(m+1)\cdots(m+k-1)]$ is a multiple of $k!$.

To prove $P_{m+1}$ is true , i.e : $[(m+1)(m+2)\cdots(m+k)]$.

I expand $[(m+1)(m+2)\cdots(m+k)]$ i arrived at

$$[m(m+1)(m+2)\cdots(m+k-1)] + [k(m+1)(m+2)\cdots(m+k-1)]$$

Therefore the $[m(m+1)(m+2)\cdots(m+k-1)]$ is a multiple of $k!$.

I need to show that $k(m+1)(m+2)\cdots(m+k-1)$ is a multiple of $k!$.

How to? Intuitively is true but how to prove it mathematically? I just said that $(m+1)(m+2)\cdots(m+k-1)$ is a factor of multiple of $k!$ And $k$ is a factor of multiple of $k!$ Therefore $k(m+1)(m+2)\cdots(m+k-1)$ is a multiple of $k!$. Is it alright?

Michael Hardy
  • 1
TBX
  • 51
  • Your first paragraph is enough, I think, but it depends on what you have done in the course. – Empy2 Sep 08 '14 at 02:26

1 Answers1

1

$$\binom{n}{k}=\frac{n(n-1)\cdots(n-k+1)}{k!}$$ is an integer number, because: $$\binom{n}{0}=\binom{n}{n}=1,\qquad \binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}.$$ This gives that $k!$ must be a divisor of $(n)_k =n(n-1)\cdots(n-k+1)$.

Michael Hardy
  • 1
Jack D'Aurizio
  • 353,855
  • I know that n choose k is an integer. But the question ask me to show n(n+1) + ... + (n + k - 1 ) is a multiple of k!. Can i re-write the statement into n(n-1)...(n-k+1) and divide it by k! to get an integer and thus show it is a multiple of k! Or do by mathematical induction? – TBX Sep 08 '14 at 02:44
  • If $\binom{n}{k}=\frac{A}{B}$ is an integer, then $A=rB$, hence $A$ is a multiple of $B$. The "hard" part is so just to show that $\binom{n}{k}$ is an integer. But this is obvious (through induction) from the recurrence relations that the binomial coefficients satisfy. – Jack D'Aurizio Sep 08 '14 at 02:56
  • I guess you meant $\binom {n+k-1}{k}$ – orangeskid Sep 08 '14 at 03:38
  • @orangeskid: the statement in the question title depends on the rising Pochhammer symbol, the question content and my answer rely on the falling Pochhammer symbol, but the two approaches are clearly equivalent up to a translation of $n$. – Jack D'Aurizio Sep 08 '14 at 04:19
  • 1
    @Jack D'Aurizio: Absolutely. The whole point is that the product of $k$ consecutive integers is divisible by $k!$, the order of the factors is not that important. – orangeskid Sep 08 '14 at 07:32