Proving by strong induction that $\forall n \ge 2, \;\forall d \ge 2 : d \mid n(n+1)(n+2)...(n+d-1) $ I'm trying to prove by induction the following statement without success:
$$\forall n \ge 2, \;\forall d \ge 2 : d \mid n(n+1)(n+2)...(n+d-1) $$
For the base case: $n = 2$, $d = 2$
$2\mid 2(2+1)$ which is true.
Now, the confusion begins! I assume I would need to use the second induction principle to proof this because $P(n)$ and $P(n+1)$ are not related at all. It is also the first time I am dealing with more than one variable so it makes it harder for me.
I tried the following:
- Trying to prove by simple induction. I did not go very far.
- Trying to split my induction step in 2 parts: If $d\mid n$, I'm done. 
If $d$ does not divide $n$, then I would need to do a second proof and this is where I'm blocked.
Anyone could tell me what's wrong in the approach I take to solve this problem?
Any help would be appreciated!
 A: Hint $\ $ Any sequence of $\rm\,d\,$ consecutive naturals has an element divisible by $\rm\,d.\,$ This has a very simple proof by induction:  shifting such a sequence  by one does not change its set of remainders mod $\rm\,d,\,$ since it simply replaces the old least element $\rm\:\color{#C00}n\:$ by the new greatest element $\rm\,\color{#C00}{n+d}$
$$\begin{array}{}\rm \:\color{#C00}n &\rm n+1 &\rm n+2 &\rm\! \cdots\! &\rm n+d-1  & \\
                    \to  &\rm n+1 &\rm n+2\rm &\! \cdots\! &\rm n+d-1 &\rm \color{#C00}{n+d} \end{array}$$
Since $\rm\: \color{#C00}n\equiv \color{#C00}{n+d} \pmod{\! d},\,$ the shift does not change the remainders in the sequence. Thus the remainders are the same as the base case $\rm\ 0,1,2,\ldots,d-1\ =\: $ all possible remainders mod $\rm\,d.\,$ Therefore the sequence has an element with remainder $\,0,\,$ i.e. an element divisible by $\rm\,d.$
A: Hint
$$ (n+1)(n+2)...(n+d-1)(n+d)= \left[(n+1)(n+2)(n+3)...(n+d-1)\right]n + \left[(n+1)(n+2)(n+3)...(n+d-1) \right]d$$
$P(n)$ tells you that the first term on RHS is divisible by $d$, while the second one is clearly divisible by $d$...
A: Note that $n(n+1)\dots(n+d-1)$ is the product of $d$ consecutive integers. Thus, it suffices to prove that if $n,n+1,\dots,n+d-1$ are any $d$ consecutive integers, then $d$ divides one of these integers. I would prove this by induction on $n$, simultaneously for all $d$.
First, it’s clearly true for $n=1$, since in that case the $d$ integers are $1,2,\dots,d$. Suppose now that it’s true for some $n$, and consider the $d$ consecutive integers $n+1,n+2,\dots,n+d$. By the induction hypothesis one of the integers $n,n+1,\dots,n+d-1$ is a multiple of $d$. If it’s one of the integers $n+1,n+2\dots,n+d-1$, you’re done (why?), and if $n$ is a multiple of $d$, then so is ... ?
A: Fixed $d$, it is easy to show that the statement holds for every $n$, by induction. The inductive step is as follows:
suppose $d|n(n+1)\cdots(n+d-1)$, then put $m=gcd(d,n)$ and observe that $gcd(d,n+d)=m$ as well, therefore, by assumption
$$\frac{d}{m}\vert (n+1)\cdots(n+d-1)$$
so
$$d=\frac{d}{m}m\vert (n+1)\cdots(n+d-1)(n+d)\;.$$
Now you just have to show that the statement is true for $n=2$ and every $d$, but this is easy: $2\leq d\leq d+2-1=d+1$, therefore $d$ divides $2\cdot3\cdots(d+1)=(d+1)!$.
A: This is one that iterates on the relative values between n & d for the inductive steps-- 
not on values n, n+1, n+k, n+k+1 as the usual case. 
The proof is by looking at the values of n and d. 
Say n=dt+x whenever n>d. 
For the base case, check whether x=0 satisfies-- which it does. 
For the inductive step, assume k=x satisfies. Then, so does k=x+1 since the multipliers are the same. 
A: As abbreviation, define $f(n,d)=n\cdot (n+1)\cdot\ldots\cdot (n+d-1)$.
Base case $n=2$:
$$\forall d\ge 2\colon d|f(2,d) = 2\cdot 3\cdot\ldots \cdot d$$
This is true because $d$ occurs among the factors on the rihght.
$n\to n+1$:
Assume that we know about $n$ that 
$$\tag1\forall d\ge 2\colon d|f(n,d)$$
Claim: then also 
$$\tag2\forall d\ge 2\colon d|f(n+1,d)$$
Indeed, let $d\ge 2$ be arbitrary. 
Then by$(1)$ we know that $d|f(n,d)$, say $f(n,d)=d a$.
Note that $$n\cdot f(n+1,d) = f(n,d)\cdot (n+d)=n\cdot f(n,d)+d\cdot f(n,d)$$
Since $n$ divides $f(n,d)$ (as first factor), write $f(n,d)=n b$.
Then we obtain
$$f(n+1,d) = \frac1n(n\cdot f(n,d)+d\cdot f(n,d))=d (a+b).$$
SInce $d\ge 2$ was arbitrary, this shows $(2)$ and thus our induction step $n\to n+1$.
A: Consider the numbers $n \mod d,(n+1)\mod d,...,(n+d-1)\mod d$ these numbers are all equal and form a subset of {$0,1,...,d-1$}. Since both sets are equal on size, therefore both sets are equal. Therefore one of the numbers $n,n+1,...,n+d$ is divisible by $d$. Thus, $d|n(n+1)...(n+d-1)$
