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.

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!

share|improve this question
    
you only need one induction, on $d$. Write $n$ in the form $dk+m$ –  user51427 Dec 7 '12 at 22:02

7 Answers 7

up vote 2 down vote accepted

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 ... ?

share|improve this answer

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

share|improve this answer
    
Typo: there are two factors $(n+1)$ in each term. –  WimC Dec 7 '12 at 22:09
    
@WimC Thank you, fixed. –  N. S. Dec 7 '12 at 22:27

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

share|improve this answer

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)!$.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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