Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question already has an answer here:

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.

share|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1  
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

3 Answers 3

up vote 3 down vote accepted

$$ \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.

share|improve this answer
4  
Would the downvoter care to comment? –  robjohn May 9 '13 at 23:55

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

share|improve this answer

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.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.