I'm having trouble trying to solve this problem:
Prove that $\forall n \in \Bbb N,~ 40^n n! \mid (5n)!$
I must be overlooking something simple because I can't go through it with induction.
Base case $P(1)$ works.
I want to see that it holds for $P(n+1)$.
So I'm looking at $40^{n+1} (n+1)! | (5n+5)!$ with the hypothesis that what I want to prove is right.
But operating I end up with: $\dfrac{(5n+5)!}{40^{n+1} (n+1)!}$
If I expand the factorial in the numerator I see my inductive hypothesis but I have an 8 in the denominator and some other factors above that I don't know how to deal with: $$\dfrac{(5n+4)(5n+3)(5n+2)(5n+1)5n!}{40^{n} (n)! \cdot 8}$$
Perhaps this is not the way to do it. I've also tried starting with my hypothesis and then multiplying by $\dfrac{40}{40}$ and $\dfrac{(n+1)}{(n+1)}$ but it's almost the same thing.
I'll be thankful with any suggestion!
You are actually done: $$ \frac{(5n+5)!}{40^{n+1}(n+1)!} = \frac{(5n)!}{40^n (n)!} \times \frac{(5n+5)(5n+4)(5n+3)(5n+2)(5n+1)}{5 \times 8} $$
The first is an integer, by the inductive hypothesis.
To see that the second is an integer, note that $5$ divides $5n+5$. Of the remaining $4$ consecutive numbers $5n+1 ... 5n+4$, at least two are even. Furthermore, one of them is a multiple of $4$ ($4$ consecutive numbers must leave all possible remainders mod $4$, including zero).
Hence, the product of these is a multiple of $4 \times 2 = 8$, so it follows that the other expression is also an integer. Hence, the LHS is an integer, and the induction is complete.
Example : $n=7$, then $5n+1 ... 5n+4 = 36,37,38,39$, where $36$ is a multiple of $4$ and $38$ is a multiple of $2$. Similarly, $n=10$, then $52 = 5n+2$ is a multiple of $4$, and $54$ is a multiple of $2$.