prove that if m and n are any positive integers and m is odd, then $ m \mid \sum \limits_{i=0}^{m-1} (n ~+~ i)$ is divisible by m.

Question

Trying to figure out the induction prof on this theorem: $$ \forall m,n \in \mathbb{Z}, ~ m,n \geq 1 ~\land~ m \equiv 1(\mod 2) ~\rightarrow~ m \mid \sum \limits_{i=0}^{m-1} (n ~+~ i) $$ I got the base:

$ m=3 \wedge n=5$

$ 3 | (5+0)+(5+1)+(5+2)$

$ 3 | 18$

Induction Proof: $$ m \mid \sum \limits_{i=0}^{m-1} (n ~+~ i) ~\rightarrow~ m+1 \mid \sum \limits_{i=0}^{m} (n ~+~ i) $$

$$ m+1 \mid \sum \limits_{i=0}^{m} (n ~+~ i) = \sum \limits_{i=0}^{m-1} (n ~+~ i) + (n+m) = (???)$$ And that is where i get confused. Can some one help me?

Answer 1

If $m|\sum_{i=0}^{m-1}(n+i)$ holds true for $\displaystyle n=r,m|\sum_{i=0}^{m-1}(r+i)$

For $\displaystyle n=r+1,\sum_{i=0}^{m-1}\{(r+1)+i\}=\sum_{i=0}^{m-1}(r+i)+\sum_{i=0}^{m-1}1$

$$\implies\sum_{i=0}^{m-1}(r+1+i)=\sum_{i=0}^{m-1}(r+i)+m$$

For the base case set $n=0$

Answer 2

So from the theorem the sum of the First n integers $$\sum_{i=0}^n i = \frac{(n)(n+1)}{2}$$ then when we add the constant k $$\sum_{i=0}^{m-1} i+k = \frac{(m-1)(m)}{2}+{k*m}$$ then we can factor the m

$${((m-1)(m)}/{2})+{k*m}$$= $$m{(((m-1)}/{2})+{k)}$$ which means that $${((m-1)}/{2})+{k}$$ is divisible by m

so we know that m is odd so m =2r+1 for some integer which will cancel the (-1) over the (2) in the in the last equation.