0
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 20 '20 at 4:32
1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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