# Prove that $(a+1)(a+2)…(a+b)$ is divisible by $b!$ [duplicate]

The problem is following, prove that:

$$(a+1)(a+2)...(a+b)\text{ is divisible by } b!\text{ for every positive integer a,b}$$

I've tried solving this problem using mathematical induction, but I don't think that i did it correctly. Here's what i've done

$1.\ b=1\ (Basis)$

$$b!| (a+1)(a+2)...(a+b)$$ $$1 | a+1 \text{, which is true}$$

$2.\ b=k\ (Induction\ Hypothesis)$

$$k! | (a+1)(a+2)...(a+k)\text{, we assume it's true}$$ $$k!*n = (a+1)(a+2)...(a+k)\text{, n is some positive integer}$$

$3.\ b=k+1\ (Inductive\ Step)$

In order to prove I should get:

$$(k+1)!*m = (a+1)(a+2)...(a+k)(a+k+1)\text{, where m is some positive integer}$$ $$(a+1)(a+2)...(a+k)(a+k+1) = k!*n*(a+k+1)$$ $$(a+1)(a+2)...(a+k)(a+k+1) = (k+1)!*n + k!*n*a$$ $$(a+1)(a+2)...(a+k)(a+k+1) - a(a+1)(a+2)...(a+k) = (k+1)!*n$$ $$(a+1)(a+2)...(a+k)(k+1) = (k+1)!*n$$

And as you can see I'm returning at the beginning.

Also I've tried to use the fact that in b consecutive numbers, there must be at least one that divides b, but since i eliminate that number (because I couldn't be sure that the quotient is divisible with (b-1) or (b-2) or ... or 2. And after this i can't continue with (b-1) using this method, because it's not necessary for the other (b-1) to be consecutive.

-

## marked as duplicate by Stahl, vadim123, TMM, Henry T. Horton, Peter SmithMay 10 '13 at 0:14

Induction seems like a bad way to prove this. –  Ethan May 9 '13 at 22:55
See here or perhaps here. –  Stahl May 9 '13 at 22:59
As i have said Pigeon hole principle fails after hte first try, because if the b numbers are not consecutive, doesn't mean some of them is divisible by b. And i can't use the quotent because i don't know is it divisible by any other of the b numbers –  Stefan4024 May 9 '13 at 23:00
As answers note, you have a binomial coefficient. There are elegant combinatorial reasons why a binomial coefficient will always work out to be an integer. If you are interested in something more arithmetic-based, see this post. –  alex.jordan May 9 '13 at 23:28
I suggest 2-D induction. –  ᴊ ᴀ s ᴏ ɴ May 9 '13 at 23:28

$$\frac{(a+b)(a+b-1)(a+b-2)\cdots(a+1)}{b(b-1)(b-2)\cdots3\cdot2\cdot1}=\binom{a+b}{b}$$ Since binomial coefficients are listed in Pascal's Triangle, they are integers.

-
Would the downvoter care to comment? –  robjohn May 9 '13 at 23:55
Don't worry I've compensated it –  user171358 Oct 23 '14 at 8:03

$${a+b \choose b} \text{ is always an integer, so therefore b! divides your expression}$$

-

You can do induction simultaneously on $a$ and $b$.

Basis. If $a=0$ the statement is clearly true. If $b=0$ it is also true (an empty product is equal to one).

Inductive hypothesis. Assume that the statement is true if we decrease $a$ or $b$ by one. More precisely, let $L(a,b)$ denote the statement for given $a$ and $b$. We assume that $L(a-1,b)$ and $L(a,b-1)$ are true.

Inductive step. Write: \begin{align} & (a+1) \ldots (a+b-1) (a+b) \\ = \, a & (a+1) \ldots (a+b-1) \\ + \quad & (a+1) \ldots (a+b-1) b \\ \end{align} The first term divides $b!$ because $L(a-1,b)$ is true. The second term divides $b!$ because $L(a,b-1)$ is true.

-