# Induction proof with summation

For this question, I'm stuck on the inductive step for this proof. Here is what I have so far. Can anyone please help me out? Thanks

$$\sum_{i=0}^n i = \frac{n(n+1)}{2}$$.Use this result to prove that if m and n are any positive integers and m is odd, then $$\sum_{i=0}^{m-1} (n+k)$$ is divisible by m. Does the conclusion hold if m is even? Justify your answer

Base Case: m = 3, n = 0

$$\frac{3}{(0+1+2)}$$

$$\frac{3}{3}$$

Let r be an odd integer such that m = 2r+1

Inductive Step:

2r+1|$$\sum_{i=0}^{2r} (n+k)$$ -> 2r+2|$$\sum_{i=0}^{2r} (n+k)$$

• Welcome to Math SE. What is $k$ in $\sum_{i=0}^{m-1} (n+k)$? As it's current stated, the result would just be $m(n+k)$. However, I assume you meant either $\sum_{k=0}^{m-1} (n+k)$ or $\sum_{i=0}^{m-1} (n+i)$. Please clarify this. Jan 20 '20 at 4:32

I will assume that you want to show that $$\sum_{k=0}^{m-1} (n+k)$$ is divisible by $$m$$.

Then

$$\begin{array}\\ s(m, n) &=\sum_{k=0}^{m-1} (n+k)\\ &=\sum_{k=0}^{m-1} n+\sum_{k=0}^{m-1} k\\ &=mn+\dfrac{(m-1)m}{2}\\ \end{array}$$

If $$m$$ is odd then $$m=2j+1$$ for some integer $$j$$ so

$$\begin{array}\\ s(m, n) &=mn+\dfrac{(2j+1-1)m}{2}\\ &=mn+\dfrac{(2j)m}{2}\\ &=mn+jm\\ &=m(n+j)\\ \end{array}$$

is divisible by $$m$$.

• Wait why didn't you sub m = 2j+1 into mn? Jan 20 '20 at 19:24
• It wasn't needed. Only needed to show that m+1 was even. The other term was already divisible by m. Jan 21 '20 at 23:55